大数据去重复,求速度

fender0107401

这个问题有很多种解决方法，我感觉最好利用数据自身的特点，lz贴出来的数据似乎有些规律性可以利用。

timespace

回复 20# MMMIX
是不太科学，从现在的结果也不足以倒推出原因。。。

从Perl官网找到一封1998年的C数据结构文档http://blob.perl.org/tpc/1998/Pe ... Perl%20Illustrated/，如今HASH函数可能不同，但基础数据结构应该还有参考价值，其中hash的实现：


考虑64位系统，load factor（元素个数/buckets）小于1，还没算上hash key字符串内容：

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. # SvNULL (ANY, REFCNT, FLAGS & Type)
   
6. my $SvNULL_size = 8*3;
   
7. 
   
8. # SvPV (SvNULL, PVX, CUR, LEN)
   
9. my $SvPV_size = $SvNULL_size + 8*3;
   
10. 
    
11. # SvIV (SvNULL, IVX/NVX)
    
12. my $SvIV_size = $SvNULL_size + 8;
    
13. 
    
14. # HE (next, hek, val)
    
15. my $bucket_size = 8;
    
16. my $entry_size = 8*3 + 8*2 + $SvIV_size + $bucket_size;
    
17. 
    
18. # HV
    
19. my $entrys = 150e6;
    
20. my $HV_size_min = $entrys * $entry_size;
    
21. 
    
22. printf "hash size %.2f GB\n", $HV_size_min/2**30;

复制代码

输出：

1. $ ./hash_storage.pl
   
2. hash size 11.18 GB

复制代码

在加上原始字符串的2.5GB，那就是13.68GB，基本就是最保守的内存估计了，不过距离真实的19GB+还有不少空白。


   

MMMIX

回复 22# timespace


    我拿楼主提供的数据实际测试了一下，16M的数据（无重复），在运行时最多要占用 86M 多的空间，差不多是实际数据的五倍多。这 hash 快是快，可是占用空间也太多了点。

huang6894

菜鸟来一个~
因为数据太大没下。。自己弄了100W行试了下~

laputa73

回复 23# MMMIX


    以前测过redis的内存占用,大约是原始数据的4倍
   
   LZ给出的数据，第一二列重复率极高，应该有优化算法，类似用3层hash替代1层hash的方法（相当于减少了key的总数）。

1. open IN,"tt1.txt";
   
2. open OU,">","result.txt";
   
3. my %hash=();
   
4. my $line=0;
   
5. while(<IN>){
   
6.         chomp;
   
7.         my @tmp=sort {$a<=>$b} split /\t/;        
   
8.         $hash{$tmp[0]}{$tmp[1]}{$tmp[2]}++;
   
9.         #print @tmp;
   
10.         $line++;
    
11.         last if $line >10000000;
    
12. }
    
13. print "sortDone\n";
    
14. 
    
15. while(my ($cc)=each %hash){
    
16.         print OUT $cc,"\n";        
    
17. }

复制代码

测试了一下，处理前10M行，使用内存440M,1分多钟。
6G内存应该够用。

zhlong8

回复 22# timespace


    http://cpansearch.perl.org/src/RURBAN/illguts-0.47/index-18.html

timespace

回复 26# zhlong8
太强大了，3ks。扫了一眼，内存确实变得更多了。


   

luwp

我以前在linux/unix上是用sort  按指定列排序，然后去重

sort命令本身就是归并排序，你可以看到在tmp疯狂的生产大量的碎片，然后慢慢得到最终结果


sort命令不会把内存弄爆的