Статистика i-го порядка в Python

Question

Учитывая список n сопоставимых элементов (например, чисел или строк), оптимальный алгоритм для нахождения упорядоченного элемента i занимает O(n) времени.

Выполняет ли Python изначально O(n) Статистика времени для списков, dicts, sets, ...?

Answer 1

Ни одна из упомянутых структур данных Python не реализует алгоритм статистики i-го порядка.

На самом деле, это может не иметь особого смысла для словарей и множеств, учитывая тот факт, что оба не делают никаких предположений о упорядочении его элементов. Для списков не должно быть сложно реализовать selection algorithm, что обеспечивает время работы O (n).

Answer 2

Если я < < п вы можете дать посмотреть на http://docs.python.org/library/heapq.html#heapq.nlargest и http://docs.python.org/library/heapq.html#heapq.nsmallest (не решить вашу проблему, но быстрее, чем сортировка и принимая I-й элемент).

Answer 3

Это не является родным решением, но вы можете использовать NumPy-х partition найти -ю статистики порядка к списка в O (N) времени.

import numpy as np 
x = [2, 4, 0, 3, 1] 
k = 2 
print('The k-th order statistic is:', np.partition(np.asarray(x), k)[k]) 

EDIT: это предполагает нулевую индексацию, то есть «нулевой порядок статистика» выше 0.