比 std::nth_element 更快的东西
Something faster than std::nth_element
我正在研究 kd-tree 实现,我目前正在使用 std::nth_element 按元素的中值划分元素向量。但是 std::nth_element 占用了 90% 的树构建时间。谁能提出更有效的替代方案?
提前致谢
如果您在 vector
中的查找次数多于插入次数,您可以考虑使用按插入排序的数据结构——例如 std::set
——然后使用 std::advance()
按排序顺序获取第 n 个元素。
你真的需要第n个元素,还是需要中间"near"个元素?
有更快的方法可以将元素 "near" 放在中间。一个例子大致如下:
function rough_middle(container)
divide container into subsequences of length 5
find median of each subsequence of length 5 ~ O(k) * O(n/5)
return rough_middle( { median of each subsequence} ) ~ O(rough_middle(n/5))
结果应该大致在中间。一个真正的第 n 个元素算法可能使用类似上面的东西,然后清理它以找到实际的第 n 个元素。
在 n=5
,你得到了中间。
在n=25
,你得到了短序列的中间部分。这将大于每个短序列的所有较小者,或者至少第 9 个元素但不超过第 16 个元素,或者距边缘 36%。
在n=125
,你得到每个短序列中间的粗略中间。这至少是第 9 个中间,所以比你的粗糙中间少了 8*3+2=26 个元素,或者说离边缘 20.8%。
在n=625
,你得到每个短序列中间的粗略中间。这至少是第 26 个中间,所以比你的粗糙中间少了 77 个元素,或者说离边缘 12%。
在 n=5^k
,你得到了 5^(k-1)
粗中间的粗中间。如果一个5^k
序列的粗中间是r(k)
,那么r(k+1) = r(k)*3-1 ~ 3^k
.
3^k
比 O 表示法中的 5^k 增长得慢。
3^log_5(n)
= e^( ln(3) ln(n)/ln(5) )
= n^(ln(3)/ln(5))
=~ n^0.68
是对 n
元素序列的 rough_middle
下限的粗略估计。
理论上,可能需要大约 n^0.33
次迭代才能达到单个元素,这并不是很好。 (n^0.68 中的位数是 n 中位数的 ~0.68 倍。如果我们从每个粗略的中间削减那么多,我们需要非常粗略地重复 n^0.33
次 n 中的位数来消耗所有位 - 更多,因为当我们从 n
中减去时,下一个 n
会从中减去一个稍小的值。
我见过的第 n 个元素解决方案解决这个问题的方法是在每个级别进行分区和修复:不是递归到 rough_middle
,而是递归到 middle
。然后保证中位数的真正中间非常接近序列的实际中间,并且您可以 "find the real middle" 相对快速地(以 O 表示法)由此。
也许我们可以通过在有更多元素时进行更准确的 rough_middle
迭代来优化这个过程,但不要强迫它成为实际的中间?端n
越大,越接近中间我们需要递归调用到中间以使最终结果合理地接近中间。
但在实践中,您的序列是一个非常糟糕的序列实际上需要 n^0.33 步才能划分为零的概率可能非常低。有点像快速排序问题:3 个元素的中位数通常就足够了。
快速统计分析。
您随机选择 5 个元素,然后选择中间的一个。
The median index of a set of 2m+1
random sample of a uniform distribution follows the beta distribution with parameters of roughly (m+1, m+1)
,对于非 [0,1]
间隔可能有一些比例因子。
中位数的平均值显然是 1/2。方差为:
(3*3)^2 / ( (3+3)^2 (3+3+1) )
= 81 / (36 * 7)
=~ 0.32
弄清楚下一步超出了我的统计数据。我会作弊
如果我们想象从一堆均值为 0.5 且方差为 0.32 的项目中取中值索引元素与平均它们的索引一样好...
现在让 n
成为我们原始集合中的元素数。
那么短序列的中位数指标之和有n次的平均值n/5*0.5 = 0.1 * n^2
。短序列中位数的指标之和的方差是n倍n/5*0.32 = 0.064 * n^2
.
如果我们将这个值除以 n/5,我们得到:
n/2 的均值和 1.6 的方差。
哦,如果那是真的,那就太棒了。不随 n
的大小而增长的方差意味着随着 n
变大,短序列中值的平均指数变得异常紧密地分布。我想这有点道理。可悲的是,我们并没有完全这样做——我们想要短序列中值的伪中值分布。这几乎肯定更糟。
实施细节。我们可以用对数的内存开销做一个就地粗略的中位数。 (我们甚至可以在没有内存开销的情况下做到这一点!)
我们使用 "nothing here" 占位符维护一个包含 5 个索引的向量。
每一层都是连续的层。
在每个元素处,我们推进底部索引。如果满了,我们抓取中位数,往上一层插入,清空底层。
最后,我们完成了。
using target = std::pair<size_t,std::array<size_t, 5>>;
bool push( target& t, size_t i ) {
t.second[t.first]=i;
++t.first;
if (t.first==5)
return true;
}
template<class Container>
size_t extract_median( Container const& c, target& t ) {
Assert(t.first != 0);
std::sort( t.data(), t.data()+t.first, [&c](size_t lhs, size_t rhs){
return c[lhs]<c[rhs];
} );
size_t r = t[(t.first+1)/2];
t.first = 0;
return r;
}
template<class Container>
void advance(Container const& c, std::vector<target>& targets, size_t i) {
size_t height = 0;
while(true) {
if (targets.size() <= height)
targets.push_back({});
if (!push(targets[height], i))
return;
i = extract_median(c, targets[height]);
}
}
template<class Container>
size_t collapse(Container const& c, target* b, target* e) {
if (b==e) return -1;
size_t before = collapse(c, b, e-1);
target& last = (*e-1);
if (before!=-1)
push(before, last);
if (last.first == 0)
return -1;
return extract_median(c, last);
}
template<class Container>
size_t rough_median_index( Container const& c ) {
std::vector<target> targets;
for (auto const& x:c) {
advance(c, targets, &x-c.data());
}
return collapse(c, targets.data(), targets.data()+targets.size());
}
它概述了它如何在随机访问容器上工作。
我正在研究 kd-tree 实现,我目前正在使用 std::nth_element 按元素的中值划分元素向量。但是 std::nth_element 占用了 90% 的树构建时间。谁能提出更有效的替代方案?
提前致谢
如果您在 vector
中的查找次数多于插入次数,您可以考虑使用按插入排序的数据结构——例如 std::set
——然后使用 std::advance()
按排序顺序获取第 n 个元素。
你真的需要第n个元素,还是需要中间"near"个元素?
有更快的方法可以将元素 "near" 放在中间。一个例子大致如下:
function rough_middle(container)
divide container into subsequences of length 5
find median of each subsequence of length 5 ~ O(k) * O(n/5)
return rough_middle( { median of each subsequence} ) ~ O(rough_middle(n/5))
结果应该大致在中间。一个真正的第 n 个元素算法可能使用类似上面的东西,然后清理它以找到实际的第 n 个元素。
在 n=5
,你得到了中间。
在n=25
,你得到了短序列的中间部分。这将大于每个短序列的所有较小者,或者至少第 9 个元素但不超过第 16 个元素,或者距边缘 36%。
在n=125
,你得到每个短序列中间的粗略中间。这至少是第 9 个中间,所以比你的粗糙中间少了 8*3+2=26 个元素,或者说离边缘 20.8%。
在n=625
,你得到每个短序列中间的粗略中间。这至少是第 26 个中间,所以比你的粗糙中间少了 77 个元素,或者说离边缘 12%。
在 n=5^k
,你得到了 5^(k-1)
粗中间的粗中间。如果一个5^k
序列的粗中间是r(k)
,那么r(k+1) = r(k)*3-1 ~ 3^k
.
3^k
比 O 表示法中的 5^k 增长得慢。
3^log_5(n)
= e^( ln(3) ln(n)/ln(5) )
= n^(ln(3)/ln(5))
=~ n^0.68
是对 n
元素序列的 rough_middle
下限的粗略估计。
理论上,可能需要大约 n^0.33
次迭代才能达到单个元素,这并不是很好。 (n^0.68 中的位数是 n 中位数的 ~0.68 倍。如果我们从每个粗略的中间削减那么多,我们需要非常粗略地重复 n^0.33
次 n 中的位数来消耗所有位 - 更多,因为当我们从 n
中减去时,下一个 n
会从中减去一个稍小的值。
我见过的第 n 个元素解决方案解决这个问题的方法是在每个级别进行分区和修复:不是递归到 rough_middle
,而是递归到 middle
。然后保证中位数的真正中间非常接近序列的实际中间,并且您可以 "find the real middle" 相对快速地(以 O 表示法)由此。
也许我们可以通过在有更多元素时进行更准确的 rough_middle
迭代来优化这个过程,但不要强迫它成为实际的中间?端n
越大,越接近中间我们需要递归调用到中间以使最终结果合理地接近中间。
但在实践中,您的序列是一个非常糟糕的序列实际上需要 n^0.33 步才能划分为零的概率可能非常低。有点像快速排序问题:3 个元素的中位数通常就足够了。
快速统计分析。
您随机选择 5 个元素,然后选择中间的一个。
The median index of a set of 2m+1
random sample of a uniform distribution follows the beta distribution with parameters of roughly (m+1, m+1)
,对于非 [0,1]
间隔可能有一些比例因子。
中位数的平均值显然是 1/2。方差为:
(3*3)^2 / ( (3+3)^2 (3+3+1) )
= 81 / (36 * 7)
=~ 0.32
弄清楚下一步超出了我的统计数据。我会作弊
如果我们想象从一堆均值为 0.5 且方差为 0.32 的项目中取中值索引元素与平均它们的索引一样好...
现在让 n
成为我们原始集合中的元素数。
那么短序列的中位数指标之和有n次的平均值n/5*0.5 = 0.1 * n^2
。短序列中位数的指标之和的方差是n倍n/5*0.32 = 0.064 * n^2
.
如果我们将这个值除以 n/5,我们得到:
n/2 的均值和 1.6 的方差。
哦,如果那是真的,那就太棒了。不随 n
的大小而增长的方差意味着随着 n
变大,短序列中值的平均指数变得异常紧密地分布。我想这有点道理。可悲的是,我们并没有完全这样做——我们想要短序列中值的伪中值分布。这几乎肯定更糟。
实施细节。我们可以用对数的内存开销做一个就地粗略的中位数。 (我们甚至可以在没有内存开销的情况下做到这一点!)
我们使用 "nothing here" 占位符维护一个包含 5 个索引的向量。
每一层都是连续的层。
在每个元素处,我们推进底部索引。如果满了,我们抓取中位数,往上一层插入,清空底层。
最后,我们完成了。
using target = std::pair<size_t,std::array<size_t, 5>>;
bool push( target& t, size_t i ) {
t.second[t.first]=i;
++t.first;
if (t.first==5)
return true;
}
template<class Container>
size_t extract_median( Container const& c, target& t ) {
Assert(t.first != 0);
std::sort( t.data(), t.data()+t.first, [&c](size_t lhs, size_t rhs){
return c[lhs]<c[rhs];
} );
size_t r = t[(t.first+1)/2];
t.first = 0;
return r;
}
template<class Container>
void advance(Container const& c, std::vector<target>& targets, size_t i) {
size_t height = 0;
while(true) {
if (targets.size() <= height)
targets.push_back({});
if (!push(targets[height], i))
return;
i = extract_median(c, targets[height]);
}
}
template<class Container>
size_t collapse(Container const& c, target* b, target* e) {
if (b==e) return -1;
size_t before = collapse(c, b, e-1);
target& last = (*e-1);
if (before!=-1)
push(before, last);
if (last.first == 0)
return -1;
return extract_median(c, last);
}
template<class Container>
size_t rough_median_index( Container const& c ) {
std::vector<target> targets;
for (auto const& x:c) {
advance(c, targets, &x-c.data());
}
return collapse(c, targets.data(), targets.data()+targets.size());
}
它概述了它如何在随机访问容器上工作。