リスト内の隣人を見つける最も効率的な方法

Question

私は長さ2016のリストを持っていますが、242だけがデータを含み、残りはNoneに設定されています。私の目的は、IDW（逆距離の重み付け）の単純な形式ですべてのギャップを埋めるために値を補間することです。 だから私のスクリプトのタスクは次のとおりです。はmyList

の全項目にわたる

• 反復はmyListに値が含まれている場合（つまり、ない Noneです）あなたは「見つけた場合、単に
• それをコピーNone "をmyList内のすべてのアイテムまでの距離を計算して左と右の隣の位置/値を取得する
• 両隣からのギャップの補間値を計算します（離れた方が遠いほど、 ）

我々は唯一の14項目（5つの有効なもの）の小さなリストを持っていると仮定します

myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79] 
resultList = [None] * len(myList) 

for i in range(len(myList): 
    if not myList[i] is None: 
     resultList[i] = myList[i] 
    else: 
     distance = [i - j for j in range(len(myList)) if not myList[j] is None] 
     neighbors = min([n for n in dist if n>0]), max([n for n in dist if n<0]) 
     # rest of the interpolation (not important for my question): 
     neighbors_c = [(1/float(n))**2 for n in neighbors] 
     c_sum = sum(neighbors_c) 
     neighbors_c = [n/c_sum for n in neighbors_c] 
     resultList = myList[i-neighbors[0]]*neighbors_c[0] + myList[i-neighbors[1]]*neighbors_c[1] 

私は多くの多くのデータセットのためにそれをやっています。私はこの方法がデータセットあたり約0.59秒かかることを知りました。私の悩みは、私のリストがすべてソートされているという事実ですが、私はそれから2つの値しか必要としません。 99％の距離は何のためにも計算されません。すなわち、2つのを試みるために私を導いた：ijが負になった後、その後明らかにそれが最も近い値に走ったので、反復処理を停止します。

だからではなく、リストの内包表記：

distance = [i - j for j in range(len(myList)) if not myList[j] is None] 

私はループのための適切な操作を行います

dist = [] 
for j in range(len(myList)): 
    if not myList[j] is None: 
     dist.append(i-j) 
     if i-j < 0: break 

この方法では、データセットごとに0.38秒まで低下することができました。 myList内のすべてのアイテムを繰り返し処理する場合、この2番目のメソッドは最初は素早く（アイテムは2番目、3番目、4番目、...後にヒットし、すぐに終了します）、最後のアイテムは改善されません。 j = 0である。

すべての距離をチェックする必要はなく、最大のマイナスおよびスモールをプラスにしなくても、データセット内の特定の数値の2つの近隣を見つける手早い方法があると思いますか？

また、私はPythonにはかなり新しくなっていますので、私のスクリプトで他の非平凡な表現が見つかったら教えてください。皆さんありがとう！

Answer 1

UPDATE： ここでnumpyのinterpでそれを行う方法は次のとおりです。

import numpy as np 

myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79] 

values = [(i, val) for i, val in enumerate(myList) if val is not None] 

xp, fp = zip(*values) 

print(xp) # (0, 4, 7, 9, 13) 
print(fp) # (26, 31, 58, 42, 79) 

result = np.interp(np.arange(len(myList)), xp, fp) 
print(result) # [ 26. 27.25 28.5 29.75 31. 40. 49. 58. 50. 42. 51.25 60.5 69.75 79. ] 

オリジナルポスト：他の人がすでに提案してきたように

、あなたは最高のは、いくつかの補間を使用してオフすでに実装されnumpyまたはpandasで私はそれはあなたがNoneで始まるか終わるのリストを持っているケースを処理しないよう、あなたが学習のためか、簡単な例のためだけにこれを使用することをお勧め

myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79] 

resultList = [] 

# first lets split the list into sublists that group the numbers 
# and the Nones into groups 
for i, item in enumerate(myList): 
    if i == 0: 
     resultList.append([item]) 
    else: 
     if type(resultList[-1][-1]) == type(item): 
      resultList[-1].append(item) 
     else: 
      resultList.append([item]) 

print(resultList) # [[26], [None, None, None], [31], [None, None], [58], [None], [42], [None, None, None], [79]] 

# now lets interpolate the sublists that contain Nones 
for i, item in enumerate(resultList): 
    if item[0] is not None: 
     continue 

    # this is a bit problematic, what do we do if we have a None at the beginning or at the end? 
    if i == 0 or i + 1 == len(resultList): 
     continue 

    prev_item = resultList[i - 1][-1] 
    next_item = resultList[i + 1][0] 

    difference = next_item - prev_item 
    item_length = len(item) + 1 

    for j, none_item in enumerate(item): 
     item[j] = prev_item + float(j + 1)/item_length * difference 

# flatten the list back 
resultList = [item for sublist in resultList for item in sublist] 

print(resultList) # [26, 27.25, 28.5, 29.75, 31, 40.0, 49.0, 58, 50.0, 42, 51.25, 60.5, 69.75, 79] 

：

は、しかし、完全を期すために、ここで私が思い付いたAA迅速なソリューションです