python - 程序运行速度太慢

Question

我创建了一个程序来查找拼字游戏中可用的最佳单词，但是当它根据 Sowpods 字典检查所有可能单词的列表时，需要很长时间才能完成。当给定 7 个字母时，我仍然没有看到它成功完成算法这是我的代码:

import itertools
Dictionary = open("Sowpods.txt").read().splitlines()
rackLetters = []
realwords = []
allwords = []
pointValues = {"Blank":0, "A":1, "B":3, "C":3, "D":2, "E":1, "F":4, "G":2, "H":4, "I":1, "J":8, "K":5, "L":1, "M":3, "N":1, "O":1,
               "P":3, "Q":10, "R":1, "S":1, "T":1, "U":1, "V":4, "W":4, "X":8, "Y":4, "Z":10}

def isword(word): #Checks if the give word is in the dictionary
    if word in Dictionary:
        return True
    else:
        return False

def pointcalc(wordlist): #Finds value of a word
    y = 0
    for x in range(0, len(wordlist)):
        y += pointValues[wordlist[x]]
    return y

numoftiles = int(input("How many tiles are in your rack? ")) #Finds number of tiles in user's rack

try:
    int(numoftiles) #Ensures that the number is not a decimal
except:
    print("The amount of tiles in your rack must be a whole number.")
    exit(0)

if numoftiles > 7 or numoftiles < 1: #Ensures that the player has a valid amount of scrabble tiles
    print("Number of tiles in rack must be between inclusive 1 and 7.")
    exit(0)

for x in range(0, numoftiles):
    letter = input("Letter #" + str(x+1) + "? ").upper()
    if len(letter) != 1:
        exit(0)
    rackLetters.append(letter) #Creates List of letters in user's rack

for x in range(0, numoftiles):
    permutations = list(itertools.permutations(rackLetters, x+1))
    allwords.extend(permutations)
print(allwords)
for x in range(0, len(allwords)):
    concat = ''.join(allwords[x]) #Joins list of rack letters into one word
    if isword(concat):
        realwords.append(concat)

for x in range(0, len(realwords)):
    print(realwords[x] + "-" + str(pointcalc(list(realwords[x]))))

Answer 1

创建单词的set()。在集合中查找的时间复杂度为 O(1):

在此行中创建集合:

Dictionary = set(open("Sowpods.txt").read().splitlines())

使用set()只需不到一秒即可完成

示例:

How many tiles are in your rack? 7
Letter #1? d
Letter #2? e
Letter #3? f
Letter #4? g
Letter #5? a
Letter #6? f
Letter #7? e

[('D',), ('E',), ('F',), ('G',), ('A',), ('F',), ('E',), ...
DE-3
DA-3
DE-3
ED-3
EF-5
EA-2
EF-5
EE-2
...