Что такое эквивалентная функция «nth_element» в Python?

Question

Я хочу внедрить дерево точек Vantage в питоне, но он использует std :: nth_element в C++.

Поэтому я хочу найти эквивалентную функцию «nth_element» в Python или numpy.

Обратите внимание, что 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 

И я не только хочу, чтобы получить п-й элемент, но и хотят, чтобы повторно организовать две части списка, [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())); 

EDIT:

Я использовал ответ на 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.2217168808 
17.0386350155 
281.301710844 

И потом, я буду делать больше теста с использованием C++ код.

Но есть проблема, при использовании numpy он всегда будет возвращать новый массив, он будет тратить много памяти, когда мой массив огромен. Как я могу справиться с этим. Или мне просто нужно написать C++ для python.

EDIT2:

@ Bhuvan-Venkatesh Спасибо за рекомендации статсумму.

Я использую раздел, как ниже:

import numpy 

@profile 
def 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 - это тот, который я хочу найти.

Answer 1

http://docs.scipy.org/doc/numpy/reference/generated/numpy.partition.html

Просто убедитесь, что раздел NumPy создаст две новые массивы, а это означает, что вы будете быстро сделать много новых массивов. Они более эффективны, чем списки python, но не будут делать то же самое, что и в C++.

Если вы хотите точный элемент, то вы можете сделать поиск фильтр, который по-прежнему будет O (п)

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) 

Так что ваш новый код медленнее, но это питон-й способ сделать это.

EDIT:

Так что вам нужно компаратор? Помимо написания небольшой собственной функции, нет никакого способа - в чистом виде numpy как ключевое слово - потому что каждая операция numpy реализована в высоко оптимизированном c-коде, означающем, что передача в функции python или лямбда python заставит numpy переходите на уровень объекта каждый раз и eval.

numpy.vectorize переходит на уровень предмета, но в конце вам придется написать свой собственный код; Rosetta code имеет импульс, если вы хотите создать более «оптимизированный алгоритм». (Я помещаю это в кавычки, потому что с объектами python вы все равно будете намного медленнее, чем c или numpy-код из-за доступа к уровню объекта). Если скорость - ваша истинная забота, но вы хотите, чтобы читаемость на python рассматривала возможность расширения с помощью cython.