c++ - 比std::nth_element更快的东西

Question

我正在研究kd-tree实现，目前正在使用 std::nth_element 来按元素的中位数划分元素 vector 。但是std::nth_element占用了树构建时间的90％。谁能建议一个更有效的选择？

提前致谢

Answer 1

您是否真的需要第n个元素，还是需要在中间“附近”的元素？

有更快的方法可以使元素“靠近”中间。一个例子大致如下:

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

是对 rough_middle元素序列的 n终止位置的下界的非常粗略的估计。

从理论上讲，可能需要多达约 n^0.33的约简迭代才能达到单个元素，但这并不是那么好。 (n ^ 0.68中的位数是n中位数的约0.68倍。如果我们将每个粗糙的中间部分削掉那么多，我们需要将其重复非常大 n^0.33乘以n中的位数，以消耗所有位数- -更多，因为当我们从 n中减去时，下一个 n会从中减去一个较小的值)。

我见过的第n个元素解决方案解决此问题的方式是通过在每个级别进行分区和修复:您不必递归为 rough_middle，而是递归为 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变大，短序列中位数的平均指数变得可笑地紧密分布。我想这很有道理。可悲的是，我们还没有做到这一点-我们想要短序列中值的伪中位数分布。几乎可以肯定，这更糟。

实现细节。我们可以用对数的内存开销来做就位的粗糙中值。 (我们甚至可以在没有内存开销的情况下做到这一点!)

我们使用“此处无内容”占位符维护5个索引的 vector 。

每个都是连续的层。

在每个元素上，我们都会下移底部索引。如果已满，我们将抓取中位数，然后将其插入下一层，然后清除底层。

最后，我们完成了。

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());
}

概述了它如何在随机访问容器上工作。