python - for loop in for loop 的更快替代方案

Question

我有一本包含约 150,000 个键的字典。没有重复的键。每个 key 的长度为 127 个字符，每个 key 在 1-11 个位置上有所不同(大多数差异发生在 key 的末尾)。每个键的值是一个唯一的 ID 和一个空白列表 []。对于一个给定的键，我想找到所有其他恰好相差 1 个字符的键，然后将 ID 附加到给定的键空白列表中。最后我想要一个键和它的值(一个 ID 和一个包含一个字符不同的所有键的列表)。

我的代码可以工作，但问题是它太慢了。双 for 循环是 150,000^2 = ~250 亿。在我的电脑上，我每分钟可以执行约 200 万次循环(每次都执行 match1 函数)。这将需要大约 8 天的时间才能完成。没有 match1 函数的循环运行速度快约 7 倍，因此将在约 1 天内完成。

我想知道是否有人知道如何提高速度？

# example dictionary
dict = {'key1' : ['1', []], 'key2' : ['2', []], ... , 'key150000' : ['150000', []]}


def match1(s1,s2,dict):    
    s = 0
    for c1, c2 in zip(reversed(s1), reversed(s2)):
        if s < 2:
            if c1 != c2:
                s = s + 1
        else:
            break
    if s == 1:
        dict1[s1][1].append(dict1[s2][0])


for s1 in dict:
    for s2 in dict:
        match1(s1,s2,dict)

Answer 1

目前您正在检查每个键与其他每个键的总 O(n^2) 比较。洞察力是我们只需要检查其他 key 的一小部分。

假设每个键的字符具有 k 不同值的字母表。例如，如果您的 key 是由 a-z 和 0-9 组成的简单 ASCII 字符串，则为 k = 26 + 10 = 30。

给定任何键，我们可以生成所有可能的键，这些键距离一个字符:有 127 * k 这样的字符串。在您将每个键与大约 150,000 个其他键进行比较之前，现在我们只需要与 127 * k 进行比较，在 k = 30 的情况下为 3810。这将整体时间复杂度从 O(n^2) 降低到 O(n * k) ，其中 k 是一个独立于 n 的常量。 这是当您扩展 n 时真正加速的地方。

这里有一些代码可以生成一个键的所有可能的邻居:

def generate_neighbors(key, alphabet):
    for i in range(len(key)):
        left, right = key[:i], key[i+1:]
        for char in alphabet:
            if char != key[i]:
                yield left + char + right

所以，例如:

>>> set(generate_neighbors('ab', {'a', 'b', 'c', 'd'}))
{'aa', 'ac', 'ad', 'bb', 'cb', 'db'}

现在我们计算每个键的邻域:

def compute_neighborhoods(data, alphabet):
    keyset = set(data.keys())
    for key in data:
        possible_neighbors = set(generate_neighbors(key, alphabet))
        neighbors = possible_neighbors & keyset

        identifier = data[key][0]

        for neighbor in neighbors:
            data[neighbor][1].append(identifier)

现在举个例子。假设

data = {
 '0a': [4, []],
 '1f': [9, []],
 '27': [3, []],
 '32': [8, []],
 '3f': [6, []],
 '47': [1, []],
 '7c': [2, []],
 'a1': [0, []],
 'c8': [7, []],
 'e2': [5, []]
}

然后:

>>> alphabet = set('abcdef01234567890')
>>> compute_neighborhoods(data, alphabet)
>>> data
{'0a': [4, []],
 '1f': [9, [6]],
 '27': [3, [1]],
 '32': [8, [5, 6]],
 '3f': [6, [8, 9]],
 '47': [1, [3]],
 '7c': [2, []],
 'a1': [0, []],
 'c8': [7, []],
 'e2': [5, [8]]}

还有一些优化我没有在这里实现。首先，你说这些键在后面的字符上大多不同，而且它们最多在 11 个位置不同。这意味着我们可以更聪明地计算交集 possible_neighbors & keyset 和生成邻域。首先，我们修改 generate_neighbors 以首先修改 key 的 trailing 字符。然后，我们不是一次生成整个邻居集，而是一次生成一个，并检查是否包含在 data 字典中。我们跟踪找到了多少个，如果找到 11 个，我们就会中断。

我没有在我的回答中实现这个的原因是我不确定它是否会导致显着的加速，并且实际上可能更慢，因为这意味着删除优化的 Python带有纯 Python 循环的内置(设置交集)。