问题标签 [nth-element]

我std::nth_element用来获取向量百分位数的（大致正确）值，如下所示：

我注意到对于最多 32 个元素的 vectorIn 长度，向量会完全排序。从 33 个元素开始，它永远不会排序（如预期的那样）。

不确定这是否重要，但该函数位于通过 Matlab 使用“Microsoft Windows SDK 7.1 (C++)”编译的“(Matlab-)mex c++ 代码”中。

编辑：

另请参见传递给函数的 1e5 个向量中最长排序块的长度的以下直方图（向量包含 1e4 个随机元素并计算随机百分位数）。请注意非常小的值处的峰值。

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++ 代码 :)

这是否总是会导致：

或者其他可能的结果是：

我已经在我的机器上尝试了多次，导致第 n 个值始终是连续的。但这不是证据；）。

它的用途：

我想构建一个独特的 Kdtree，但我的向量中有重复项。目前我正在使用 nth_element 来查找中值。问题是选择一个唯一/可重构的中位数，而不必再次遍历向量。如果中值是连续的，我可以选择一个唯一的中值，而无需太多遍历。

任务是对具有重复 st 的向量进行部分排序，如果向量已排序，则中值（第 n 个元素）位于它的位置。所有较小的元素都应该在左边，所有较大的元素都应该在右边。与中值相同的所有元素都必须按原始顺序排列 - 但只有这些元素不是其余元素。

你会如何解决这个问题？

我最初的解决方案：

1. 使用 std::nth_element() 查找中值元素
2. 遍历向量并仅对与其索引具有相同值的元素进行排序。我将如何有效地做到这一点？

从给定的未排序向量中，我想获得第 n 个最小的元素。我发现标准库中有一个方法。但我不明白以下结果。

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

我的错误是什么？

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

我在 23 个整数的 std::vector 中调用 nth_element() 算法约 400,000 次，更精确的“无符号短”值。

我想提高计算速度，而这个特定的调用需要很大一部分 CPU 时间。现在我注意到，与 std::sort() 一样，即使在最高优化级别和 NDEBUG 模式（Linux Clang 编译器）下，nth_element 函数在分析器中也是可见的，因此比较是内联的，而不是函数调用本身。好吧，更确切地说：不是 nth_element() 而是 std::__introselect() 是可见的。

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

但是，在这种情况下，这比使用 nth_element 慢。

另外，使用统计方法是不合适的，比 std::nth_element 更快的东西

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

我的问题：有人知道一个简单的解决方案吗？我想我可能不是唯一一个必须经常调用 std::sort 或 nth_element 的人。

我想nth_element在一个类中将该函数与我自己的排序函数（应该可以访问对象的数据）一起使用。目前，我正在执行以下操作：

当然，这不起作用，我得到了错误：“必须调用对非静态成员函数的引用”。之后，我查看了必须调用非静态成员函数的引用，如何std::function使用成员函数进行初始化？和其他一些问题在这里。我明白为什么这不起作用，但我不确定如何解决这个问题。

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

我需要在数组中找到第 n 个最大的元素，目前我正在按照以下方式进行操作：

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

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

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

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

现在向量可能是：

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

而且，nth_element 支持接受一个可以比较两个元素的函数，比如，在下面的as中，vector是一个vector op DataPoint，DistanceComparator函数会用the_v.begin()比较两个点的距离：

编辑：

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

结果：

然后，我将使用 C++ 代码进行更多测试。

但是有一个问题，当使用numpy时，它总是会返回一个新的数组，当我的数组很大时，它会浪费很多内存。我该如何处理。或者我只需要为 python 编写一个 C++ 扩展。

编辑2：

@bhuvan-venkatesh 感谢您推荐分区功能。

我使用如下分区：

并像这样运行探查器：

结果是：

它不会像这样复制整个数组：numpy.partition(a, 3)

结论： numpy.ndarray.partition 是我想要找到的。

序言很新。我正在尝试创建一个简单的递归规则来查找列表中的第 n 个元素。例如，如果我有一个字符串或数字列表，我希望能够使用查询

我不希望使用内置的 Nth0，也不希望 R 使 R 为 n -1