Python - 针对大文件过滤/排序的建议？

Question

我有一个文件，里面大约有2000万行（大约1.5GB）。每一行的格式是：

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

这个文件里有重复的内容，但重复的形式是：

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

有些行的内容是完全一样的，但前两个元素通常是互换的（可能总是这样）。

有没有人能给我一些建议，怎么从这么大的文件中去掉这种重复的内容呢？

谢谢。

Answer 1

separator = " "
aSet = set()
with open('myfile', 'rU') as infile:
    for line in infile:
        tempLine = line.split(separator)
        tempLine = tempLine[1:2] + tempLine[0:1] + tempLine[2:]
        tempLine = separator.join(tempLine)
        if line not in aSet and tempLine not in aSet:
            aSet.add(line)

现在，aSet 里包含了一些独特的行，这些行不管 entry_1 和 entry_2 有没有交换，都是唯一的。

编辑：如果所有的条目都可以交换，而且这条线仍然被认为是独特的，那么：

separator = " "
aSet = set()
with open('myfile', 'rU') as infile:
    for line in infile:
        aSet.add(frozenset(line.split(separator)))

Answer 2

合适的解决方案取决于你的具体情况，比如你有哪些限制条件，以及你需要多频繁地执行这个操作。

如果这是一次性（或者很少进行）的操作，并且内存使用不是大问题，那么像下面这样的做法就足够了：

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. 然后对整个文件按行进行排序。
3. 去除重复项就变得简单了，因为重复的条目会排在一起。

步骤2和3可以合并，因为在排序时你可以直接在比较条目时丢弃重复项。

如果你不介意使用命令行，步骤2和3可以用 sort -u yourfile 来完成。

需要注意的是，这样会改变文件中行的顺序（你提到这不是问题）。

为了大幅减少内存使用，虽然会牺牲一些性能，你可以使用基于文件的数据库来存储和查找已访问的条目（替代 set()）。

你可以通过在内存中存储条目的哈希值来加快速度，只有在哈希值匹配时才查询数据库，以确认条目是否真的相同。哈希可以很简单，比如取每个条目的第一个字符，或者使用内置的 hash() 函数，或者选择一个 现有的哈希算法。每种方法在性能、哈希大小和冲突频率之间都有权衡。选择哪种方法取决于你的数据和限制条件。

找到最佳解决方案需要一些努力。如果你需要频繁执行这个操作，那就值得去尝试。