Pythonのi番目の統計量

Question

n相当の要素（数字や文字列など）のリストが与えられた場合、i番目の要素を見つける最適なアルゴリズムはO(n)時間かかります。

PythonはネイティブにO(n)のリスト、ディクテーション、セットの時間順序統計を実装していますか？

Answer 1

Pythonが言及したデータ構造のどれも、i番目の順序統計アルゴリズムをネイティブに実装していません。

実際には、その要素の順序については何も仮定していないことを前提にして、辞書やセットにはあまり意味がないかもしれません。リストについては、O（n）の実行時間を提供するselection algorithmを実装するのは難しいことではありません。

Answer 2

場合、私< < nはあなたが（あなたの問題を解決し、より高速なソートとi番目の要素を取るよりもしていない）http://docs.python.org/library/heapq.html#heapq.nlargestとhttp://docs.python.org/library/heapq.html#heapq.nsmallestを見て与えることができます。

Answer 3

これはネイティブな解決策ではありませんが、NumPyのpartitionを使用すると、O（n）時間のリストのk番目の統計を見つけることができます。

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であると仮定します。