Python读取大文件并消除重复行

Question

我有一个巨大的文本文件，里面有重复的行。文件大小约为150000000行。我想找到最有效的方法读取这些行并消除重复项。我正在考虑一些方法：-

1. 将整个文件读入，使用list(set(lines))。
2. 每次读取10k行，对其进行list(set(lines))操作，将另外的10k行读取到列表中，再进行list(set(lines))。重复以上步骤。

你会如何解决这个问题？任何形式的多进程处理是否有帮助？

- user277465

---

文件是否已排序？每行字符数是否固定？每行大约有多少个字符？ - tommy.carstensen

你不关心当前行的顺序吗？因为使用set可能会弄乱它们。 - Shashank

你们两种方法都指向同一个问题，这种情况下的 set() 不会有任何魔力，因为比较字符串的成本是 O(mn)，当你处理 150000000 行时，这种方法似乎不可行。 - ZdaR

你的代码有多少行是重复的？超过50%？少于1%？如果有很大一部分代码是重复的，我会采用分治法。 - tommy.carstensen

@joe-koberg在这里回答了同样的问题[https://dev59.com/Q3A75IYBdhLWcg3wJFcL]。用户log0在这里解释了如何将大文件分割成较小块[https://dev59.com/AGEh5IYBdhLWcg3wKQnY]。 - tommy.carstensen

Answer 1

多进程并不会真正有所帮助，因为您的瓶颈在于内存。您需要使用哈希表:

1. 读取行
2. 计算哈希值，例如md5，在已遇到的所有哈希值的集合中查找。
3. 如果哈希值未在集合中找到，则输出该行并将此哈希值添加到集合中。

需要注意以下几点：

• md5需要128位，即使没有额外开销，也需要超过2G的内存。
• 集合和字典的内存开销很大。

因此，如果您拥有4GB以上的内存，这是可行的。更可扩展的解决方案是将遇到的哈希值存储在磁盘上的排序文件中，并每次搜索它们。这会（非常！）慢，但您可以将内存占用降至所需的任意低水平。

此外，如果您不关心结果文件中的行顺序，则可以根据某个哈希函数将文件分成较小的文件（具有以a开头的md5 值的行，具有以b开头的md5值的行等）。这将使它们足够小，以便只需对其进行 sort | uniq （或者如果您愿意的话，通过Python在内存中排序）并连接结果。

- thule

---

每行平均有13-20个字符，所以我猜测没有必要计算md5（128位）？ - tommy.carstensen

你可以使用更短的哈希值，例如Python中的hash()函数来节省内存。不确定它的效果如何。 - thule

@tommy.carstensen 我猜是有的，因为总行数为150000000，在如此大的数据集上匹配字符串将消耗大量时间，我认为这种哈希方法比set()更好。 - ZdaR

我喜欢这种哈希方法。问题是如何处理哈希冲突。你可能会有两个不同的字符串，但它们的哈希值相同。我不知道默认的哈希函数有多好，所以使用@letitbee建议的md5仍然可能更好。 - Roman Kutlak

我认为你可以截断sha1并仍然获得相当好的熵。但是由于输入集非常大，我不知道这是否是一个好主意。 - thule

Answer 2

这里的问题在于内存，所以完全将文件加载到内存中可能不是一个选项。

由于您不需要维护行的顺序，因此一种潜在的选择是进行某种基数排序：

for each line in file:
    put this line into a new file based on the first character

新文件现在应该会小得多，如果仍然太大，您可以基于第二、第三个字符等递归地拆分文件（例如，原始文件中每行都以a开头）。

一旦这些文件足够小，可以使用 list(set(list)) 方法进行操作，完成后再使用 cat 将文件合并。或者，如果可用的话，您也可以使用 uniq UNIX 命令行工具。

请注意，基数排序部分很容易并行化，因为每行与其他行是独立的。

- robbrit

Answer 3

先思考一下是否真的需要在Python中解决这个问题。你可以：

• 调用sort和uniq，这些标准工具存在于大多数posix系统中。它们会完成任务，速度更快，并且在你考虑到边缘情况（例如内存耗尽）之前就已经解决了。
• 最简单的解决方案可能是使用sqlite包创建一个内存数据库，将所有行插入到临时表中，然后从中执行select distinct...。同样，sqlite的性能比你在纯Python中自己实现要好。

- user2722968

---

不，SQLite 会使情况变得更糟，而不是更好。你实际上可以使用常规的基于磁盘的数据库来完成它，但这非常低效，而且这并没有解决问题，而是让别人来解决它。 - thule