python - 更快地将列表居中的方法

Question

我正在寻找一种更好、更快的方法来居中几个列表。现在我有以下内容:

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

这实际上创建了一个列表 (m)，其中包含一系列以随机数为中心的随机数，另一个列表 (sm)，其中 m > 居中并附加一个值列表 (si)。

此示例运行得相当快，但是当我运行具有更多变量的较大任务时，性能会减慢直至停止。

Answer 1

你的主循环包含这个臭名昭著的行:

if i in sm:

似乎没什么，但自从 sm是 sorted 的结果这是一个list ，因此O(n)查找，这解释了为什么大数据集速度很慢。

此外，您正在使用更臭名昭著的 si[sm.index(i)] ，这使得你的算法 O(n**2) .

由于您需要索引，因此使用 set并不那么容易，还有更好的事情要做:

自 sm已排序，您可以使用 bisect查找 O(log(n)) 中的索引，像这样:

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为您提供插入点 i在sm 。这并不意味着该值实际上在列表中，因此我们必须检查(通过检查返回的值是否在现有列表范围内，并检查返回索引处的值是否是搜索到的值)，如果是，追加，否则追加 None .