リスト内でランクとパーセンテージのランクを見つけよう

Question

私は働いている非常に大きなリスト（> 1M行）を持っていますが、フロートを指定すると、そのフロートをランク付けしてフロートのリストと比較し、それがリストの範囲と比較してパーセンテージランクであることを発見する。ここに私の試みはあるが、それは非常に遅いです：私はおそらくそれから配布やサンプルをビルドすることができパーセンテージランクについては

X =[0.595068426145485, 
0.613726840488019, 
1.1532608695652, 
1.92952380952385, 
4.44137931034496, 
3.46432160804035, 
2.20331487122673, 
2.54736842105265, 
3.57702702702689, 
1.93202764976956, 
1.34720184204056, 
0.824997304105564, 
0.765782842381996, 
0.615110856990126, 
0.622708022872803, 
1.03211045820975, 
0.997225012974318, 
0.496352327702226, 
0.67103858866700, 
0.452224068868272, 
0.441842124852685, 
0.447584524952608, 
0.4645525042246] 

val = 1.5 
arr = np.array(X) #X is actually a pandas column, hence the conversion 
arr = np.insert(arr,1,val, axis=None) #insert the val into arr, to then be ranked 
st = np.sort(arr) 

RANK  = float([i for i,k in enumerate(st) if k == val][0])+1 #Find position 
PCNT_RANK = (1-(1-round(RANK/len(st),6)))*100 #Find percentage of value compared to range 


print RANK, PCNT_RANK 
>>> 17.0 70.8333 

、かなり確実ではない、まだ、任意の提案を歓迎します...そう頻繁に使用することになるだろうどんなスピードアップが有利であろう。

ありがとうございました。

Answer 1

あなたのコードの2が遅い部分は、以下のとおりです。

• st = np.sort(arr)。リストをソートするには平均O（n log n）時間がかかります。ここで、nはリストのサイズです。

• RANK = float([i for i, k in enumerate(st) if k == val][0]) + 1。リストを反復するには、O（n）時間がかかります。リストをソートする必要がない場合@ChrisMuellerが指摘するように

、そして、あなただけのO（n）の時間を要しており、一度ソートせずに、それを反復処理することができますし、最速のオプションになります。

リストをソートする必要がある場合（または事前にソートされたアクセス権がある場合）、2番目のステップの中で最も速いオプションはRANK = np.searchsorted(st, val) + 1です。リストはすでにソートされているので、索引を検索すると、リスト全体を反復する代わりに、バイナリ検索でO（log n）時間しかかかりません。これは、元のコードよりもずっと速くなります。

Answer 2

アレイの並べ替えはやや遅いようです。最後に配列をソートする必要がない場合は、numpyのブール演算が高速になります。

arr = np.array(X) 
bool_array = arr < val # Returns boolean array 
RANK = float(np.sum(bool_array)) 
PCT_RANK = RANK/len(X) 

また、リストの理解度を使用してnumpyをすべて避けてください。

上記の数値解は、私のシステムでは6.66usですが、リストの理解方法は3.74usです。