Python搜索大列表速度

Question

我在搜索一个很大的列表时遇到了速度问题。我有一个文件，里面有很多错误和非常奇怪的单词。我正试图使用difflib在一个包含650000个单词的字典文件中找到最接近的匹配项。下面的方法工作得很好，但是非常慢，我想知道是否有更好的方法来解决这个问题。这是代码：

from difflib import SequenceMatcher
headWordList = [ #This is a list of 650,000 words]


openFile = open("sentences.txt","r")

for line in openFile:
    sentenceList.append[line]

percentage = 0
count = 0

for y in sentenceList:
      if y not in headwordList:

         for x in headwordList:
             m = SequenceMatcher(None, y.lower(), x)

             if m.ratio() > percentage:
                 percentage = m.ratio()

                 word = x

         if percentage > 0.86:        
             sentenceList[count] = word
count=count+1

感谢你的帮助，软件工程甚至还没有接近我的强项。非常感谢。

Answer 1

您应该将headwordList更改为set。

测试将非常缓慢。它必须对headwordList中的每个单词进行字符串比较，一次一个单词。这将花费与列表长度成比例的时间；如果将列表长度加倍，则将花费双倍的时间进行测试（平均）。

对于set，执行in测试所需的时间总是相同的；它不依赖于set中元素的数量。所以这将是一个巨大的加速。

现在，整个循环可以简化为：

     for x in headwordList:
         m = SequenceMatcher(None, y.lower(), x)

         if m.ratio() > percentage:
             percentage = m.ratio()

             word = x

     if percentage > 0.86:        
         sentenceList[count] = word

所有这些都是从headwordList中找到比率最高的单词，并保留它（但只有当比率超过0.86时才保留它）。这是一个更快的方法。我要把名字headwordList改成headwords，因为我希望你把它变成set，而不是list。

def check_ratio(m):
    return m.ratio()

y = y.lower()  # do the .lower() call one time
m, word =  max((SequenceMatcher(None, y, word), word) for word in headwords, key=check_ratio)
percentage = max(percentage, m.ratio())  # remember best ratio
if m.ratio() > 0.86:
    setence_list.append(word)

这看起来有点棘手，但在Python中这是最快的方法。我们将调用内置的max()函数来查找具有最高比率的SequenceMatcher结果。首先，我们构建一个“生成器表达式”，尝试headwords中的所有单词，对每个单词调用SequenceMatcher()。但当我们结束的时候，我们也想知道这个词是什么。因此，生成器表达式生成元组，元组中的第一个值是SequenceMatcher结果，第二个值是单词。max()函数不知道我们关心的是比率，所以我们必须告诉它；我们通过制作一个函数来测试我们关心的东西，然后将该函数作为key=参数传递。现在max()为我们找到比率最高的值。max()使用生成器表达式生成的所有值并返回单个值，然后将其解压到变量m和word。

在Python中，最好使用像sentence_list这样的变量名，而不是sentenceList。请参阅以下指南：http://www.python.org/dev/peps/pep-0008/

使用递增索引变量并将其分配到列表中的索引位置是不好的做法。相反，从空列表开始，使用.append()方法函数附加值。

另外，你可能会做得更好，建立一个字典的单词和他们的比率。

注意，您的原始代码似乎有一个错误：只要任何单词的百分比超过0.86，所有单词都将保存在sentenceList中，不管它们的比率是多少。上面我写的代码只保存了单词本身的比例足够高的单词。

编辑：这是为了回答一个关于需要用括号括起来的生成器表达式的问题。

每当我收到错误消息时，我通常会将生成器表达式单独拆分并将其分配给一个变量。像这样：

def check_ratio(m):
    return m.ratio()

y = y.lower()  # do the .lower() call one time
genexp = ((SequenceMatcher(None, y, word), word) for word in headwords)
m, word =  max(genexp, key=check_ratio)
percentage = max(percentage, m.ratio())  # remember best ratio
if m.ratio() > 0.86:
    setence_list.append(word)

这就是我的建议。但是，如果您不介意复杂的行看起来更加繁忙，您只需按照错误消息的建议添加一对额外的圆括号，这样生成器表达式就完全用圆括号括起来了。就像这样：

m, word =  max(((SequenceMatcher(None, y, word), word) for word in headwords), key=check_ratio)

Python允许在将表达式传递给函数时省略生成器表达式周围的显式括号，但前提是该表达式是该函数的唯一参数。由于我们还传递一个key=参数，因此需要一个完全带圆括号的生成器表达式。

但我认为如果你把genexp单独分出来，阅读起来会更容易。

编辑：@Peter Wood指出，文档建议重用SequenceMatcher来提高速度。我没有时间测试，但我认为这是正确的方法。

幸运的是，代码变得更简单了！总是个好兆头。

编辑：我刚刚测试了代码。这个代码对我有效；看看它是否对你有效。

from difflib import SequenceMatcher

headwords = [
# This is a list of 650,000 words
# Dummy list:
    "happy",
    "new",
    "year",
]


def words_from_file(filename):
    with open(filename, "rt") as f:
        for line in f:
            for word in line.split():
                yield word

def _match(matcher, s):
    matcher.set_seq2(s)
    return (matcher.ratio(), s)

ratios = {}
best_ratio = 0

matcher = SequenceMatcher()

for word in words_from_file("sentences.txt"):
    matcher.set_seq1(word.lower())
    if word not in headwords:
        ratio, word =  max(_match(matcher, word.lower()) for word in headwords)
        best_ratio = max(best_ratio, ratio)  # remember best ratio
        if ratio > 0.86:
            ratios[word] = ratio

print(best_ratio)
print(ratios)

Answer 2

1）我将headwordList存储为一个集合，而不是一个列表，允许更快的访问，因为它是一个散列数据结构。

2）您已将sentenceList定义为列表，然后尝试将其用作具有sentenceList[x] = y的字典。我会为计数定义一个不同的结构。

3）您构造sentenceList，这不需要完成。

for line in file:
   if line not in headwordList...

4）您从不标记line，这意味着您将整行存储在sentenceList中的换行符之前，并查看它是否在wordlist中

Answer 3

有两件事可以提供一些小帮助：

1）使用this SO answer中的方法最有效地读取大文件。

2）更改代码

for x in headwordList:
    m = SequenceMatcher(None, y.lower(), 1)

到

yLower = y.lower()
for x in headwordList:
    m = SequenceMatcher(None, yLower, 1)

你要把每个句子转换成65万次。没必要那么做。