python - 有什么方法可以更有效地检查单词中的所有字母是否都在列表中？

Question

对于一篇研究论文，我正在模拟第 4 channel 节目倒计时的字母轮次。从本质上讲，放置了一个由 9 个随机字母组成的板，玩家必须尝试找到由尽可能长的字母组成的单词。

我目前正在使用代码:

for word in sowpods:
        testboard = list(board)
        count = 0
        for letter in word:
            if letter in testboard:
                testboard.remove(letter)
                count += 1
        if len(word) == count:
            length.append(len(word))
    if len(length) == 0:
        return 0
    return max(length)

创建可以从板子创建的字典单词列表(导入内核的 SOWPODS .txt 文件)，然后返回可能的最长单词进行统计分析(这是模拟一轮倒计时的函数的一部分) .但是，据我所知，由于重复的 for 循环、if 语句和列表编辑，当扩展到 500 左右板的更大样本时，这是非常慢的。有没有更有效的方法来检查是否可以从板上创建单词？

我尝试使用集合；我原来的测试是:

set(word) <= set(board)

但是这种方法忽略了重复，例如，如果棋盘是 [a, e, h, s, l,..) 它会将“Hassle”视为可能的词，尽管只有一个 S 可用。理想情况下，我喜欢介于列表和集合之间的数据类型，其中顺序无关紧要，但相同元素的数量很重要，但这似乎不存在。

Answer 1

您可以实现的一种加速是重新组织逻辑，以便在遇到不匹配的字母时逐个字母的循环结束。这将加速您的代码，平均而言，与不允许的字母数量成正比。

def wordsearch(board, sowpods):
    length = []
    for word in sowpods:
        testboard = list(board)
        count = 0
        for letter in word:
            if letter in testboard:
                testboard.remove(letter)
                count += 1
        if len(word) == count:
            length.append(len(word))
    if len(length) == 0:
        return 0
    return max(length)

def find_matches(allowed, dictionary):
    allowed_list = list(allowed)
    match_words = []
    for word in dictionary:    
        good = True
        for letter in word:
            if letter not in allowed_list:
                good = False
                break
        if good == True:
            match_words.append(len(word))    
    return max(match_words)

import timeit
start_time = timeit.default_timer()
allowed = 'iptneazol'
result = wordsearch(allowed, sb_list)
# code you want to evaluate
elapsed = timeit.default_timer() - start_time
print(elapsed)
>>>0.6867701730000135

start_time = timeit.default_timer()
allowed = 'iptneazol'
result = find_matches(allowed, sb_list)
elapsed = timeit.default_timer() - start_time
print(elapsed)
>>>0.10806877499999246

这也解决了允许字母出现两次的问题，因为代码不会转换允许列表。为了提高效率，您可以将 for 循环重写为调用服务函数的列表推导式，或使用迭代器/生成器。