リストのセンタリングの高速化

Question

私はより良い、より迅速な方法をいくつかのリストを中心に探しています。今、私は以下の持っている：

効果に mはに対して中央に配置され、そこから別のリスト（ sm）と値のリスト、反対中央に乱数の範囲を含むリスト（ mを）（作成

import random 

m = range(2000) 

sm = sorted(random.sample(range(100000), 16000)) 
si = random.sample(range(16005), 16000) 

# Centered array. 
smm = [] 

print sm 
print si 

for i in m: 
    if i in sm: 
     smm.append(si[sm.index(i)]) 
    else: 
     smm.append(None) 

print m 
print smm 

si）を追加します。

このサンプルはかなり速く実行されますが、パフォーマンスが大幅に向上した大きなタスクを実行すると、パフォーマンスが低下して停止します。

Answer 1

あなたのメインループは、この悪名高い行含まれています

if i in sm: 

を何もないように見えるが、smがsortedの結果であるので、それはそれは大きなデータセットと遅いです理由を説明list、したがってO(n)のルックアップ、です。

さらに、悪名高いsi[sm.index(i)]を使用しているため、アルゴリズムはO(n**2)になります。

あなたがインデックスを必要とするので、setを使用することはそれほど容易ではない、とやる方が良いがあります：

smがソートされているので、あなたはこのように、O(log(n))にインデックスを見つけるためにbisectを使用することができます。

for i in m: 
    j = bisect.bisect_left(sm,i) 
    smm.append(si[j] if (j < len(sm) and sm[j]==i) else None) 

小文字の説明：bisectは、smにiの挿入ポイントを示します。値が実際にリストにあることを意味するわけではないので、返された値が既存のリスト範囲内にあるかどうかをチェックし、返されたインデックスの値が検索された値であるかどうかをチェックする必要があります。追加する。そうでない場合は、Noneを追加する。