如何加速 Python 列表操作

Question

如何加速 Python 列表操作

3

我有一个小的Python程序，可以逐行遍历一个超过5百万行的大型文本文件，如果符合条件就从每一行中提取一个单词，然后如果它不在列表中就将该单词添加到列表中。之后，我需要对这个巨大的列表进行字母顺序排序，然后将列表中的项目写入新的文本文件。

代码如下：

big_list = []
with open('big_text_file.txt', 'r', encoding='UTF8') as f:
    for line in  f:
        # some validation specific to line structure:
        if line[0] not in (1, 2, 3, 4, 5, 6, 7, 8, 9, 0) and '\t' in line:
            word = line.rsplit('\t')[0].lower()
            if word not in big_list:
                big_list.append(word)
sorted_list = sorted(big_list)
with open('results_file.txt', 'w', encoding='UTF8') as r:
    for item in sorted_list:
        r.write(item + "\n")

问题在于速度非常慢。有500万行，现在已经运行了12个小时以上(!)，但仍远未完成。我一定做错了什么。我有一个有8个核心的CPU，但在这种情况下只使用了一个。CPU负载仅为12％。我可以应用多进程来加快速度吗？或者由于此代码很简单，因此它不会产生太大作用？我仍然需要验证所有单词是否与一个列表匹配。

非常感谢任何建议。

- Ray P.

5

一个明显的改进是使用集合而不是列表来收集唯一项。你可以在O(1)的时间内测试一个集合中是否存在成员，而对于列表则需要O(n)的时间。 - jonrsharpe

4

如果line[0]不是(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)中的一个，那不是你想要的。你想要的是if not line[0].isdigit()。line[0]是一个字符，而不是一个整数。 - Jean-François Fabre

1

这两个建议应该会极大地加速你的代码。第二个意味着，目前每一行含有制表符的行都会将一个单词添加到列表中。第二个意味着，对于每个添加的单词，你必须为所有未来的单词执行一个额外的操作。你的运行时间是 O(n^2)，并且很容易变成 O(k << n)。（这里，k 是与你的预期条件匹配的行数。） - Arya McCarthy

Jean-François Fabre，是的！那是一个糟糕的例子，谢谢。 - Ray P.

@jonrsharpe使用一个集合（即使没有使用集合推导式），将运行时间从“无限”减少到仅36秒！ - Ray P.

2个回答

1

除了使用 set 外，我会使用正则表达式来更快地验证您的输入。这应该反映出您的 if 语句：

import re

pattern = re.compile(r'(?:^|\n(\s*))(?P<relevant_line>\D[^\n]*?\t[^\n]+)')
with open('big_text_file.txt', 'r', encoding='UTF8') as f:    

    matches = pattern.findall(f)

    big_set = set()

    for match in matches:
        word = match[1].split('\t')[0].lower()
        big_set.add(word)

sorted_list = sorted(big_set)
with open('results_file.txt', 'w', encoding='UTF8') as r:
    for item in sorted_list:
        r.write(item + "\n")

- EvilSmurf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jean-François Fabre · Accepted Answer

如评论所提到的，这里的主要瓶颈是使用了一个list。

此外：if line[0] not in (1, 2, 3, 4, 5, 6, 7, 8, 9, 0)很慢而且不起作用：line [0]是一个字符，而不是数字。请使用isdigit()来替代。

将big_list声明为set()，您可以替换：

if word not in big_list:
    big_list.append(word)

仅通过

big_list.add(word)

(只有当 set 中不存在时才会添加 word，而检查速度比使用哈希的list的O(n)要快得多)

更好的写法：您可以使用一行代码中的集合推导式重写您的代码（第一部分甚至包括排序部分）：

with open('big_text_file.txt', 'r', encoding='UTF8') as f:
    big_list = sorted({line[:line.find('\t')].lower() for line in f if not line[0].isdigit() and '\t' in line})

请注意更好的获取行首部分的方法，它避免了分割（并生成您几乎不使用的列表）。

如上所述，不需要对set进行in测试：如果单词已经在其中，则不会再次插入，并且插入决策测试旨在快速执行。

请注意，多进程可能有所帮助，但是您将面临磁盘I/O瓶颈，并且算法将更加复杂，因为您必须通过跳过8个相等的行号部分来“拆分”大文件，创建集合并相交... 让我们专注于单处理部分，看看情况如何。