使列表查找更快？

Question

我有一个文件，每一行都包含人名和一个包含演讲文本的文件。名称文件非常大（250k 行）按字母顺序排列，演讲文件大约有 1k 行。我想要做的是在我的文本文件中查找名称，并替换我的名称文件中出现的每个名称。这是我的代码编辑：打开列表的 with 函数只执行一次。

members_list = []
with open(path, 'r') as l:
    for line in l.readlines():
        members_list.append(line.strip('\n'))

for member in self.members_list:
    if member in self.body:
        self.body = self.body.replace(member, '<member>' + member + '</member>')

此代码到运行大约需要 2.2 秒，但因为我有很多语音文件 (4.5k)，所以总时间约为 3 小时。有没有可能让它更快？发电机是正确的选择吗？

Answer 1

目前，当您检查 "if member in self.body" 时，您会为 250,000 个名字中的每一个重新阅读记忆中的每个演讲一次。

您需要对语音正文进行一次解析，找出整个单词、空格和标点符号。然后你需要看看你是否找到了一个名字，使用已知成员名字的线性时间查找，或者最坏的日志时间。

问题是您必须找到具有不同字长的成员名称。所以这是我写的一个快速（但不是很好）的实现来处理检查最后三个单词。

# This is where you load members from a file. 
# set gives us linear time lookup
members = set()
for line in ['First Person', 'Pele', 'Some Famous Writer']:
    members.add(line)

# sample text
text = 'When Some Famous Writer was talking to First Person about Pele blah blah blah blah'
from collections import deque

# pretend we are actually parsing, but I'm just splitting. So lazy.
# This is why I'm not handling punctuation and spaces well, but not relevant to the current topic
wordlist = text.split()

# buffer the last three words
buffer = deque()

# TODO: loop while not done, but this sort of works to show the idea
for word in wordlist:
    name = None
    if len(buffer) and buffer[0] in members:
        name = buffer.popleft()

    if not name and len(buffer)>1:
        two_word_name = buffer[0] + ' ' + buffer[1]
        if two_word_name in members:
            name = two_word_name
            buffer.popleft()
            buffer.popleft()

    if not name and len(buffer)>2:
        three_word_name = buffer[0] + ' ' + buffer[1] + ' ' + buffer[2]
        if three_word_name in members:
            name = three_word_name
            buffer.popleft()
            buffer.popleft()
            buffer.popleft()

    if name:
        print ('<member>', name, '</member> ')

    if len(buffer) >2:
        print (buffer.popleft() + ' ')

    buffer.append(word)

# TODO handle the remaining words which are still in the buffer
print (buffer)

我只是想展示这个概念。这不处理空格或标点符号。这根本不处理结束——它需要在未完成时循环。它在解析时创建了一堆临时字符串。但它说明了一次解析的基本概念，尽管它在解析语音文本时速度非常慢，但它可能比搜索语音文本 250,000 次要好。

您要解析文本并检查集合中的名称的原因是您只执行一次。集合具有分摊线性时间查找，因此检查名称是否在成员中要快得多。

如果有机会，我可能会稍后将其编辑为生成令牌的 class，并在最后修复查找名称的问题，但我并不打算将其作为您的最终代码。

使列表查找更快？

Make list lookup faster?

python

loops

python-3.5