如何实现nth_element？ [英] How is nth_element Implemented?

问题描述

StackOverflow和其他地方有很多主张， nth_element 是 O（n），并且通常是通过Introselect实现的： a href = http://en.cppreference.com/w/cpp/algorithm/nth_element> http://en.cppreference.com/w/cpp/algorithm/nth_element

There are a lot of claims on StackOverflow and elsewhere that nth_element is O(n) and that it is typically implemented with Introselect: http://en.cppreference.com/w/cpp/algorithm/nth_element

我想知道如何实现。我看着维基百科对Introselect的解释，这让我更加困惑。算法如何在QSort和中位数中位数之间切换？

I want to know how this can be achieved. I looked at Wikipedia's explanation of Introselect and that just left me more confused. How can an algorithm switch between QSort and Median-of-Medians?

我在这里找到了Introsort论文： http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep= rep1& type = pdf 但这表示：

I found the Introsort paper here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf But that says:

在本文中，我们集中讨论排序问题并返回到选择问题仅在后面的部分中简要介绍。

In this paper, we concentrate on the sorting problem and return to the selection problem only briefly in a later section.

我试图通读STL本身以了解 nth_element 已实现，但是很快就变得毛茸茸。

I've tried to read through the STL itself to understand how nth_element is implemented, but that gets hairy real fast.

有人可以向我展示如何实现Introselect的伪代码吗？甚至更好的是实际的C ++代码，当然不是STL：）

Could someone show me pseudo-code for how Introselect is implemented? Or even better, actual C++ code other than the STL of course :)

推荐答案

您问了两个问题，名义上的一个

You asked two questions, the titular one

如何实现nth_element？

How is nth_element Implemented?

已经回答：

有很多关于StackOverflow的声明，其他地方说nth_element是O（n），并且通常使用Introselect实现。

There are a lot of claims on StackOverflow and elsewhere that nth_element is O(n) and that it is typically implemented with Introselect.

从我的stdlib实现中我也可以证实这一点。 （稍后会详细介绍。）

Which I also can confirm from looking at my stdlib implementation. (More on this later.)

还有一个您不理解答案的地方：

And the one where you don't understand the answer:

如何在QSort和Median-of-Medians之间切换算法？

How can an algorithm switch between QSort and Median-of-Medians?

让我们看看伪代码我从stdlib中提取的内容：

Lets have a look at pseudo code that I extracted from my stdlib:

nth_element(first, nth, last)
{ 
  if (first == last || nth == last)
    return;

  introselect(first, nth, last, log2(last - first) * 2);
}

introselect(first, nth, last, depth_limit)
{
  while (last - first > 3)
  {
      if (depth_limit == 0)
      {
          // [NOTE by editor] This should be median-of-medians instead.
          // [NOTE by editor] See Azmisov's comment below
          heap_select(first, nth + 1, last);
          // Place the nth largest element in its final position.
          iter_swap(first, nth);
          return;
      }
      --depth_limit;
      cut = unguarded_partition_pivot(first, last);
      if (cut <= nth)
        first = cut;
      else
        last = cut;
  }
  insertion_sort(first, last);
}

无需深入了解所引用函数的详细信息 heap_select 和 unguarded_pa​​rtition_pivot 我们可以清楚地看到， nth_element 给出了introselect 2 * log2（size）细分步骤（在最佳情况下，为quickselect的两倍），直到 heap_select 开始执行并彻底解决问题。

Without getting into details about the referenced functions heap_select and unguarded_partition_pivot we can clearly see, that nth_element gives introselect 2 * log2(size) subdivision steps (twice as much as needed by quickselect in the best case) until heap_select kicks in and solves the problem for good.

这篇关于如何实现nth_element？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！