标签: nth-element

我最近发现在STL中存在一个名为nth_element的方法.引用描述:

Nth_element类似于partial_sort,因为它部分地对一系列元素进行排序:它排列范围[first,last],使得迭代器nth指向的元素与该位置中的元素相同(如果整个范围[第一个,最后一个]已经排序.另外,[nth,last]范围内的元素都不小于[first,nth]范围内的任何元素.

它声称平均具有O(n)复杂性.算法如何工作？我找不到任何解释.

StackOverflow和其他地方有很多声明nth_element是O(n),它通常用Introselect实现:http://en.cppreference.com/w/cpp/algorithm/nth_element

我想知道如何实现这一目标.我查看了维基百科对Introselect的解释,这让我更加困惑.算法如何在QSort和Median-of-Medians之间切换？

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

在本文中,我们将集中讨论排序问题,并在后面的章节中简要回到选择问题.

我试图通过STL本身来了解如何nth_element实现,但这很快就会变得毛茸茸.

有人能告诉我如何实现Introselect的伪代码吗？或者甚至更好,当然除了STL之外的实际C++代码:)

有没有人知道不同实现的预期运行时间和最坏情况运行时间std::nth_element？我几乎每天都使用这个算法.

我对最近的Microsoft编译器附带的STL版本特别感兴趣,但有关此主题的任何信息都很有帮助.

请注意,这不是此问题的副本.我理解存在哪些算法,但我对哪些实现使用哪种算法感兴趣.

对于背景,有众所周知的算法可以做到这一点.一个是O(n)平均情况和O(n log n)最坏情况,一个是O(n)最坏情况但实际上缓慢(中位数的中位数).还要注意,有一些有趣的实现策略可以让我们在实践中获得最快的O(n)运行时间.该标准表明,这必须是更糟糕的O(n)平均时间.

我没有在任何地方找到这个特定主题......

我在23个整数的std :: vector中的不同数据上调用nth_element()算法,每秒大约400,000次,更精确的"无符号短"值.

我想提高计算速度,这个特定的调用需要很大一部分CPU时间.现在我注意到,与std :: sort()一样,即使具有最高优化级别和NDEBUG模式(Linux Clang编译器),nth_element函数在探查器中也是可见的,因此比较是内联的而不是函数调用本身.好吧,更多的preise:不是nth_element()但是std :: __ introselect()是可见的.

由于数据的大小很小,我尝试使用二次排序函数PIKSORT,当数据大小小于20个元素时,它通常比调用std :: sort更快,可能是因为函数将是内联的.

template <class CONTAINER>
inline void piksort(CONTAINER& arr)  // indeed this is "insertion sort"
{
    typename CONTAINER::value_type a;

    const int n = (int)arr.size();
    for (int j = 1; j<n; ++j) {
        a = arr[j];
        int i = j;
        while (i > 0 && a < arr[i - 1]) {
            arr[i] = arr[i - 1];
            i--;
        }
        arr[i] = a;
    }
}

然而,这比在这种情况下使用nth_element慢.

此外,使用统计方法是不合适的,比std :: nth_element更快

最后,由于值在0到约20000的范围内,因此直方图方法看起来不合适. …

我正在将一些C++代码移植到C#.

C#是否具有相同std::nth_element()或者我需要自己滚动？

我编写了一个程序,用户可以在向量中输入任意数量的值,它应该返回四分位数,但我不断得到"向量下标超出范围"错误:

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <ios>
#include <vector>

int main () {
    using namespace std;

    cout << "Enter a list of numbers: ";

    vector<double> quantile;
    double x;
    //invariant: homework contains all the homework grades so far
    while (cin >> x)
        quantile.push_back(x);

    //check that the student entered some homework grades
    //typedef vector<double>::size_type vec_sz;
    int size = quantile.size();

    if (size == 0) {
        cout << endl << "You must enter your numbers . "
                        "Please …

我std::nth_element用来得到一个(大致正确的)值的向量百分位数,如下所示:

double percentile(std::vector<double> &vectorIn, double percent)
{
    std::nth_element(vectorIn.begin(), vectorIn.begin() + (percent*vectorIn.size())/100, vectorIn.end());

    return vectorIn[(percent*vectorIn.size())/100];
}  

我注意到,对于vectorIn长度最多为32个元素,向量将完全排序.从33个元素开始,它永远不会被排序(如预期的那样).

不确定这是否重要,但功能是在"(Matlab-)mex c ++代码"中,通过Matlab使用"Microsoft Windows SDK 7.1(C++)"编译.

编辑:

还参见传递给函数的1e5向量中最长排序块的长度的以下直方图(包含1e4个随机元素和随机百分位数的向量).注意非常小的峰值.

我想在python中实现Vantage Point Tree，但它在C++中使用std::nth_element。

所以我想在 Python 或 numpy 中找到等效的“nth_element”函数。

请注意，第 nth_element 只会对数组进行部分排序，并且它是 O(N)。

int the_array[10] = {4,5,7,3,6,0,1,2,9,8};
std::vector<int> the_v(the_array,the_array+10);
std::nth_element (the_v.begin()+0, the_v.begin()+5, the_v.begin()+10);

现在向量可能是：

3,0,2,1,4,5,6,7,9,8

而且我不仅想得到第 n 个元素，还想得到重新排列列表的两个部分，[3,0,2,1,4] 和 [6,7,9,8]。

此外，nth_element 支持接受一个可以比较两个元素的函数，例如，在下面，向量是一个向量 op DataPoint，DistanceComparator 函数将使用 the_v.begin() 比较两个点的距离：

vector<DataPoint> the_v;
for(int n = 0; n < N; n++) the_v[n] = DataPoint(D, n, X + n * D);
std::nth_element (the_v.begin()+0, the_v.begin()+5, the_v.begin()+10,
    DistanceComparator(the_v.begin()));

编辑：

我使用了 bhuvan-venkatesh 的答案，并编写了一些代码进行测试。

partition_timer = timeit.Timer("numpy.partition(a, 10000)",
    "import numpy;numpy.random.seed(2);"+
    "a = numpy.random.rand(10000000)")
print(partition_timer.timeit(10))

sort_timer = timeit.Timer("numpy.sort(a)",
    "import numpy;numpy.random.seed(2);"+
    "a …

很多STL算法我都快看懂了，直到到了算法std::nth_element。我被困住了；我不知道它是如何工作的，但它确实有效。

为了教育和理解的目的，有人可以向我解释该算法是如何std::nth_element工作的吗？

std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin() + 2, v.end());

for (auto i : v)
    std::cout << i << " ";
std::cout << '\n';

输出：

1 0 2 3 6 7 8 5 4 9 

• 那么nth这里的元素在哪里呢？
• 该算法如何以及做什么？
• 它是否进行某种部分排序？

以下是 cppreference.com 的一些解释：

nth_element是一种部分排序算法，它重新排列 [first, last) 中的元素，以便：

• 如果对 [first, last) 进行排序，则 nth 指向的元素将更改为该位置中出现的任何元素。
• 这个新的第 n 个元素之前的所有元素都小于或等于新的第 n 个元素之后的元素。更正式地说，nth_element 按升序对范围 [first, last) 进行部分排序，以便满足范围 [first, nth) 中的任何 …

从给定的未分类矢量我想得到第n个最小元素.我发现标准库中有一个方法.但我不明白以下结果.

我使用条目{3,4,5,2,3}来获取向量,并希望拥有第2个最小元素.如果我执行以下代码,我在第二个位置得到数字2,实际上它应该是3.因为2是第一个最小元素而不是第二个.

我的错是什么？

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  std::vector<size_t> temp;
  temp.assign({3,4,5,2,3});
  std::nth_element (temp.begin(), temp.begin()+2, temp.end());
  std::cout << std::endl;
  for(size_t i=0;i<temp.size();i++){ printf("%.2f\n",(double)temp[i]);  }
}

我想nth_element在一个类中使用我自己的排序函数(它应该可以访问对象的数据).目前,我正在做以下事情:

class Foo
{
 public:
   glm::vec3 *points;
   int nmbPoints;

   bool idxPointCompareX(int a, int b);
   void bar();
}

bool Foo::idxPointCompareX(int a, int b)
{return points[a].x < points[b].x;)

void Foo::bar()
{
   stl::vector<int> idxPointList;
   for(int i = 0; i < nmbPoints; i++) idxPointList.push_back(i);  

   stl::nth_element(idxPointList.first(),idxPointList.first()+nmbPoints/2,idxPointList.end(), idxPointCompareX);
}

当然,这不起作用,我得到错误:"必须调用非静态成员函数的引用".之后,我看了一下参考非静态成员函数必须调用,如何std::function用成员函数初始化？以及其他一些问题.我理解为什么这不起作用,但我不确定如何解决这个问题.

有人可以帮助我并告诉我如何解决这个问题吗？

我需要在数组中找到第n个最大的元素,目前我正在按照以下方式执行:

std::vector<double> buffer(sequence); // sequence is const std::vector<double>
std::nth_element(buffer.begin(), buffer.begin() + idx, buffer.end(), std::greater<double>());
nth_element = buffer[idx];

但有没有办法在不使用外部缓冲区的情况下找到数组中的第n个最大元素？