问题标签 [nth-element]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - 为什么 std::nth_element 返回 N < 33 个元素的输入向量的排序向量?
我std::nth_element
用来获取向量百分位数的(大致正确)值,如下所示:
我注意到对于最多 32 个元素的 vectorIn 长度,向量会完全排序。从 33 个元素开始,它永远不会排序(如预期的那样)。
不确定这是否重要,但该函数位于通过 Matlab 使用“Microsoft Windows SDK 7.1 (C++)”编译的“(Matlab-)mex c++ 代码”中。
编辑:
另请参见传递给函数的 1e5 个向量中最长排序块的长度的以下直方图(向量包含 1e4 个随机元素并计算随机百分位数)。请注意非常小的值处的峰值。
c++ - nth_element 是如何实现的?
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++ 代码 :)
c++ - 使用 std::nth_element 时,第 n 个元素的重复项是否总是连续的?
这是否总是会导致:
或者其他可能的结果是:
我已经在我的机器上尝试了多次,导致第 n 个值始终是连续的。但这不是证据;)。
它的用途:
我想构建一个独特的 Kdtree,但我的向量中有重复项。目前我正在使用 nth_element 来查找中值。问题是选择一个唯一/可重构的中位数,而不必再次遍历向量。如果中值是连续的,我可以选择一个唯一的中值,而无需太多遍历。
c++ - 部分排序:具有保留顺序的第 n 个元素
任务是对具有重复 st 的向量进行部分排序,如果向量已排序,则中值(第 n 个元素)位于它的位置。所有较小的元素都应该在左边,所有较大的元素都应该在右边。与中值相同的所有元素都必须按原始顺序排列 - 但只有这些元素不是其余元素。
你会如何解决这个问题?
我最初的解决方案:
- 使用 std::nth_element() 查找中值元素
- 遍历向量并仅对与其索引具有相同值的元素进行排序。我将如何有效地做到这一点?
c++ - std::nth_element 提供了错误的值
从给定的未排序向量中,我想获得第 n 个最小的元素。我发现标准库中有一个方法。但我不明白以下结果。
我用条目 {3,4,5,2,3} 取向量,并希望有第二个最小的元素。如果我执行下面的代码,我会在第二个位置得到数字 2,实际上它应该是 3。因为 2 是第一个最小的元素,而不是第二个。
我的错误是什么?
c++ - 极其频繁地调用 std::nth_element() 函数
我在任何地方都没有找到这个特定的主题......
我在 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 的人。
c++ - 如何在此类中使用成员函数调用 stl::nth_element?
我想nth_element
在一个类中将该函数与我自己的排序函数(应该可以访问对象的数据)一起使用。目前,我正在执行以下操作:
当然,这不起作用,我得到了错误:“必须调用对非静态成员函数的引用”。之后,我查看了必须调用非静态成员函数的引用,如何std::function
使用成员函数进行初始化?和其他一些问题在这里。我明白为什么这不起作用,但我不确定如何解决这个问题。
有人可以帮助我并告诉我如何解决这个问题吗?
c++ - 就地查找第 n 个最大元素
我需要在数组中找到第 n 个最大的元素,目前我正在按照以下方式进行操作:
但是有没有办法在不使用外部缓冲区的情况下找到数组中的第 n 个最大元素?
python - Python中等效的“nth_element”函数是什么?
我想在 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 是我想要找到的。
prolog - 如何找到列表的第 n 个元素并在 R PROLOG 中有答案
序言很新。我正在尝试创建一个简单的递归规则来查找列表中的第 n 个元素。例如,如果我有一个字符串或数字列表,我希望能够使用查询
我不希望使用内置的 Nth0,也不希望 R 使 R 为 n -1