python - 在列表中查找邻居的最有效方法

Question

我有一个长度为 2016 的列表，但只有 242 个包含数据，其余设置为无。我的目标是在值之间进行插值，以使用简单形式的 IDW(反距离加权)来填补所有空白。所以我脚本的任务是:

• 遍历 myList 的所有项目
• 如果 myList 包含一个值(即不是 None)，只需复制它
• 如果在 myList 中找到“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%的距离都是白算的。这让我尝试了两个:在 i-j 变为负数后停止迭代，因为显然它会遇到最接近的值:

所以不是列表理解:

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

我做了一个适当的 for 循环，我在距离超过零后退出并因此再次变大:

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、3、4 之后被命中，...循环并立即退出)，但最后的项目没有改进，因为迭代总是开始在 j=0。

我想知道您是否能想出任何更快的方法来找到数据集中特定数字的两个邻居，而无需检查所有距离并且只取最大的负数和最小的正数。

另外，我对 python 很陌生，所以如果您在我的脚本中发现其他非 pythonic 表达式，请告诉我。非常感谢你们!

Answer 1

更新:这是使用 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 中实现的插值。

但是为了完整起见，这里有一个我想出的快速解决方案:

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]

我建议您仅将此用于学习或简单情况，因为它不处理列表以 None

开头或结尾的情况