如何有效地比较Python中的大型列表？

Question

我试图找到9个字母的单词,当你平均分成3个部分,然后乱七八糟地,你会得到另一个9个字母的单词.

for i in nineWordList:
    for j in nineWordList:
        if (i[3:5] + i[0:2] + i[6:8]) == j:
            correctWords.append(i)
        elif (i[3:5] + i[6:8] + i[0:2]) == j:
            correctWords.append(i)
        elif (i[0:2] + i[6:8] + i[3:5]) == j:
            correctWords.append(i)
        elif (i[6:8] + i[0:2] + i[3:5]) == j:
            correctWords.append(i)
        elif (i[6:8] + i[3:5] + i[0:2]) == j:
            correctWords.append(i)

我就是这样做的.唯一的问题是nineWordList长68,000个元素,这需要很长时间.我怎样才能提高它,使其更有效率？

Answer 1

使用集合以避免必须在列表中的两个级别上循环:

nineWordSet = set(nineWordList)
for i in nineWordSet:
    if i[3:5] + i[0:2] + i[6:8] in nineWordSet:
        correctWords.append(i)
    elif i[3:5] + i[6:8] + i[0:2] in nineWordSet:
        correctWords.append(i)
    elif i[0:2] + i[6:8] + i[3:5] in nineWordSet:
        correctWords.append(i)
    elif i[6:8] + i[0:2] + i[3:5] in nineWordSet:
        correctWords.append(i)
    elif i[6:8] + i[3:5] + i[0:2] in nineWordSet:
        correctWords.append(i)

这仍然需要遍历所有68,000个条目(你显然无法避免),但在第一遍中,它会将列表转换为集合,因此in可以在恒定时间内进行成员资格测试.这为您提供线性时间复杂度,而不是嵌套循环所具有的二次时间复杂度.当然,额外的设置将需要更多的内存,但这应该不是问题.

顺便说一句.我相信你的切片是关闭的.i[0:2]不会产生3个字母的单词(当你想要均匀分割9个字母的单词时):

>>> x = 'abcdefghi'
>>> x[0:2], x[3:5], x[6:8]
('ab', 'de', 'gh')

切片中的第二个索引始终是非包含性的,因此您需要将其增加一个:

>>> x[0:3], x[3:6], x[6:9]
('abc', 'def', 'ghi')

您还可以通过使用itertools.permutations生成那些可能的复句词来缩短您的条件.这样,您的支票可能会更好一点:

import itertools
nineWordSet = set(nineWordList)

for word in nineWordSet:
    for perm in itertools.permutations((word[0:3], word[3:6], word[6:9])):
        # skip the original permutation
        if perm == word:
            continue

        elif perm in nineWordSet:
            correctWords.append(word)

            # stop checking for more permutations
            break