什么是Python中等效的’nth_element’函数？

概述我想在 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 我想在 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,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,4,8

而且我不仅希望得到第n个元素,而且还希望重新安排列表的两部分,[3,4]和[6,8].

此外,nth_element支持接受一个可以比较两个元素的函数,例如,在下面,vector是一个向量op DataPoint,而distanceComparator函数将比较两个点距离与_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()+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 = numpy.random.rand(10000000)")print(sort_timer.timeit(10))sorted_timer = timeit.Timer("sorted(a)","import numpy;numpy.random.seed(2);"+    "a = numpy.random.rand(10000000)")print(sorted_timer.timeit(10))

结果：

2.221716880817.0386350155281.301710844

然后,我将使用C代码进行更多测试.

但是有一个问题,当使用numpy时,它总会返回一个新数组,当我的数组很大时会浪费大量内存.
我该怎么办呢
或者我只需为python编写C扩展.

EDIT2：

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

我使用如下的分区：

import numpy@profiledef for_numpy():    numpy.random.seed(2)    a = numpy.random.rand(1e7)    for i in range(100):        a.partition(numpy.random.randint(1e6))if __name__ == '__main__':    for_numpy()

并运行探查器,如：

python -m memory_profiler profiler_test.py

结果是：

line #    Mem usage    Increment   line Contents================================================    25   23.613 MiB    0.000 MiB   @profile    26                             def for_numpy():    27   23.613 MiB    0.000 MiB       numpy.random.seed(2)    28   99.934 MiB   76.320 MiB       a = numpy.random.rand(1e7)    29  100.004 MiB    0.070 MiB       for i in range(100):    30  100.004 MiB    0.000 MiB           a.partition(numpy.random.randint(1e6))

并且它不会复制整个数组,如：
     numpy.partition(a,3)

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

解决方法 http://docs.scipy.org/doc/numpy/reference/generated/numpy.partition.html

只需确保numpy分区将创建两个新数组,这意味着您将快速创建大量新数组.它们比python列表更有效,但不会像c中那样完全相同.

如果你想要确切的元素,那么你可以进行过滤搜索,它仍然是O(n)

array = np.array(...)partition = np.partition(array,5) # O(n)element = np.where(partition==array[5]) # O(n)left,right = partition[:element],partition[element+1:] # O(n)

所以你的新代码速度较慢,但​​这是python-y的方法.

编辑：

所以你需要一个比较器？除了编写自己的小函数之外,没有办法 – 在纯粹的numpy中作为关键字 – 因为每个numpy *** 作都是在高度优化的c代码中实现的,这意味着传入python函数或python lambda会强制numpy每次和eval都转到对象级别.

numpy.vectorize进入对象级别,但最后你必须编写自己的代码;如果你想创建一个更“优化的算法”,Rosetta code就会产生影响. (我把它放在引号中,因为对于python对象,由于对象级访问,你仍然比c或numpy代码慢得多).如果速度是你真正关心的问题,但你希望python可读性考虑使用cython进行扩展.

总结

以上是内存溢出为你收集整理的什么是Python中等效的’nth_element’函数？全部内容，希望文章能够帮你解决什么是Python中等效的’nth_element’函数？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。