Python-有关过滤/排序大文件的建议？

Question

我有一个包含约2000万行（约1.5GB）的文件。每行的格式为：

entry_1 entry_2 entry_3 ......... entry_5

该文件包含重复项，但格式为：

entry_2 entry_1 entry_3 ......... entry_5

某些行的内容相同，但是前两个元素经常（可能总是）切换。

有人对如何从这种大小的文件中删除这种性质的副本有任何建议吗？

谢谢。

Answer 1

一个合适的解决方案将取决于您具有哪些约束以及需要多长时间运行一次此操作。

如果这是一次（或不频繁）操作，并且内存使用量不是大问题，那么这样的事情就足够了：

visited = set() # use set for faster lookups
with open(out_filename, "w") as outfile:
    with open(in_filename, "r") as infile:
        for line in infile:
            x = line.split()
            k = (tuple(sorted(x[:2])), tuple(x[2:]))
            if k not in visited:
                outfile.write(line)
                visited.add(k)

内存使用情况取决于我们需要跟踪的唯一条目的数量visited。如果没有太多重复项，那么最终几乎所有数据都将存储在内存中。

如果内存使用成为问题，则可以分多个阶段进行：

1. 首先，通过对每行中的前2个元素进行排序来对文件进行预处理。
2. 按行对整个文件排序
3. 现在，删除重复项很简单，因为重复项将一起出现。

可以合并步骤2和3，因为在执行排序时比较条目时可以简单地丢弃重复项。

如果您不介意使用Shell，则可以使用进行步骤2和3 sort -u yourfile。

请注意，这会更改文件中各行的顺序（您提到的不是问题）。

要以牺牲一些性能为代价来大幅度减少内存使用量，可以使用基于文件的db来存储和查找访问的条目（代替set()）。

您可以通过将条目的哈希存储在内存中来加快此过程，并且仅在哈希匹配时才查询db，以确认条目是否确实相同。哈希可以像获取每个条目的第一个字符一样简单，也可以使用内置hash()函数，或者选择现有的哈希算法。每种方法都是性能，哈希大小和冲突频率之间的折衷方案。一个好的选择取决于您的数据和约束。

这将需要一些努力才能找到最佳解决方案。仅在需要经常执行此操作时才值得进行。