algorithm - 如何过滤一个非常非常大的文件

Question

我有一个非常大的未排序文件，1000GB，包含 ID 对

1. ID:ABC123 ID:ABC124
2. ID:ABC123 ID:ABC124
3. 身份证号:ABC123 身份证号:ABA122
4. ID:ABC124 ID:ABC123
5. ID:ABC124 ID:ABC126

我想过滤文件

1)重复

example
ABC123 ABC124
ABC123 ABC124

2) 反向对(丢弃第二次出现的)

example
ABC123 ABC124
ABC124 ABC123

过滤后，上面的示例文件看起来像

1. ID:ABC123 ID:ABC124
2. 身份证号:ABC123 身份证号:ABA122
3. ID:ABC124 ID:ABC126

目前我的解决方案是这样的

my %hash;

while(my $line = <FH>){
     chomp $line; #remove \n
     my ($id1,$id2) = split / /, $line;
     if(exists $hash{$id1$1d2} || exists $hash{$id2$id1}){
            next;
     }
     else{
         $hash{$id1$id2} = undef ; ## store it in a hash
         print "$line\n";
      }
}

它为较小的列表提供了我想要的结果，但对于较大的列表占用了太多内存，因为我将哈希存储在内存中。

我正在寻找一个需要更少内存的解决方案。我的一些想法是

1) 将散列保存到文件中，而不是内存中

2) 多次遍历文件

3) 使用 unix sort -u -k1,2

对文件进行排序和唯一化

在 stack exchange cs 上发帖后，他们建议使用外部排序算法

Answer 1

你可以使用 map reduce用于任务。

Map-Reduce 是一种批处理框架，可让您轻松地将工作分配给多台机器，并使用并行处理，而无需考虑同步和容错。

map(id1,id2):
    if id1<id2:
        yield(id1,id2)
   else:
        yield(id2,id1)

reduce(id1,list<ids>):
   ids = hashset(ids) //fairly small per id
   for each id2 in ids:
       yield(id1,id2)

map-reduce 实现允许您将工作分配到多台机器上，几乎不需要额外的编程工作。
假设每个 ID 都与少量其他 ID 相关联，该算法还需要对数据进行线性(且相当小)的遍历，所需的额外内存量也相当小。

请注意，这将改变对的顺序(在某些情况下，第一个 id 第二)
如果原始 id 的顺序很重要，你可以很容易地用一个额外的字段来解决它。
另请注意，数据的顺序已更改，使用 map-reduce 时无法克服它。

为了提高效率，您可能想要添加一个组合器，在这种情况下它会完成与 reducer 相同的工作，但它是否真的有用在很大程度上取决于数据。

Hadoop是一个实现Map-Reduce的开源库，在社区中被广泛使用。