更快的列表居中方式

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中的插入点。这并不意味着值实际上在列表中，所以我们必须检查它（通过检查返回值是否在现有列表范围内，并检查返回索引处的值是否是搜索的值），如果是，append，else appendNone。你知道吗