Python中的整数比较使一切变得非常缓慢

3 投票

5 回答

640 浏览

提问于 2025-04-15 19:34

以下的代码让我非常头疼：

def extract_by_letters(letters, dictionary):

    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               if word in dictionary: #I cant leave this line out
                   dictionary.remove(word)

    return dictionary

首先，关于那行 'if word in dictionary'。我为什么不能把它去掉呢？如果去掉就会出现一个错误，提示 ValueError: list.remove(x): x not in list。

但显然它是存在的。

其次，字典是一个大约有50,000个单词的文件，单词之间用换行符分隔。上面的代码运行大约需要2分钟……实在是太慢了。我对代码做了一些调整，发现：

if word.count(letter) != letters.count(letter):

这一行似乎是导致我所有问题的原因。如果我把这一行去掉（虽然这样会完全搞乱输出），函数处理字典的时间就缩短到大约2秒。

我原以为是计数函数的问题，但其实不是。

如果我把if语句改成类似于：

print word.count(letter) 
print letters.count(letter)

那么函数运行大约需要3秒。

我确信是比较操作的问题。还有其他建议吗？有没有更好的方法来解决这个问题？

提前谢谢大家！

性能优化字典操作时间复杂度编程调试整数比较列表处理代码效率逻辑错误

5 个回答

这里有一个函数，可以大大提高速度：

def extract_by_letters(letters,dictionary):
    letdict = zip(set(letters),[letters.count(let) for let in set(letters)])
    outarr = []
    for word in dictionary:
        goodword = True
        for letter in letdict:
            if word.count(letter) != letdict[letter]:
                goodword = False
                break
        if goodword:
            outarr.append(word)
    return outarr

我做了一些优化：

我创建了一个字典，把字母和它们出现的频率对应起来。这样，你就不需要每次都用letters.count去计算字母的数量，而是只需要做一次，然后把结果存起来。
我没有从字典中删除单词，而是把它们添加到一个数组中，最后从函数返回这个数组。如果你的字典很大，匹配的单词可能只有几个。而且，如果字典是一个数组（我猜是这样），每次调用删除时，它都得先从头开始查找那个单词，然后再删除。用单词的索引直接弹出会更快。
当发现字母计数不匹配时，立即跳出循环。这可以避免在已经找到答案的情况下，做不必要的检查。

我不确定你在字母变量中是否有重复的字母，所以我确保使用letdict来处理这种情况。如果你之前在字母变量中有重复的字母，那么你就会重复检查这些字母在单词中的数量。

回答于 2025-04-15 由 Python大师

分享举报

你遇到这个错误的原因是，如果有多个字母的数量相同，你就会尝试多次删除这个单词。

之所以运行得这么慢，是因为你在一个循环里又嵌套了另一个循环，这样会让程序变得很复杂。

如果你能写一两句话说明这个函数的目的，那就更容易对它进行改进了。与此同时，这样可以避免在已经删除一个单词后再去检查它是否需要被删除。

def extract_by_letters(letters, dictionary):
    for word in dictionary[:]:  # bad idea to change this while you iterate over it
        for letter in letters:
            if word.count(letter) != letters.count(letter):
                dictionary.remove(word)
                break
    return dictionary

如果字典是一个 set，那么你会发现速度会有所提升。如果字典是一个 list，那么速度提升会更明显。

回答于 2025-04-15 由 Python大师

分享举报

试着从头开始构建输出，而不是从中删除内容：

def extract_by_letters(letters, dictionary):
    d = []
    for word in dictionary:
       for letter in letters:
           if word.count(letter)>0:
               d.append(word)
               break
    return d

或者，你可以使用正则表达式：

import re
def extract_by_letters(letters, dictionary):
    regex = re.compile('['+letters+']')
    d=[]
    for word in dictionary:
       if regex.search(word):
           d.append(word)
    return d

或者，也许最简单的方法是：

import re
def extract_by_letters(letters, dictionary):
    regex = re.compile('['+letters+']')
    return [word for word in dictionary if regex.search(word)]

最后这个方法在我的Mac上扫描/usr/share/dict/words这个文件时几乎没有明显的时间消耗，这个文件里有234936个单词。

回答于 2025-04-15 由 Python大师

分享举报

Python中的整数比较使一切变得非常缓慢

5 个回答

撰写回答