Chinaunix

标题: 大数据去重复,求速度 [打印本页]
作者: gongyonghui2    时间: 2014-05-21 21:49
标题: 大数据去重复,求速度
本帖最后由 gongyonghui2 于 2014-05-22 14:28 编辑

数据有1亿5千万行3列
每行均是数字，形如


数据重复是指：任意两行，每一行的三个数排序后，这两行一样，那么就是重复。
求perl能达到去重复效率最高的方法。
数据链接:http://pan.baidu.com/s/1dDekRLJ
作者: yinyuemi    时间: 2014-05-21 22:03
本帖最后由 yinyuemi 于 2014-05-21 22:04 编辑

回复 1# gongyonghui2

没测试～
    perl -nale 'print if !h{(join "@",sort @F)}++' file
作者: q1208c    时间: 2014-05-22 08:33
perl怕是不行了.
直接用 sort 吧. 或者用 sort的算法.

用楼上的方法, 估计 OOM的可能性大.
作者: stanley_tam    时间: 2014-05-22 09:24
要是偶的话，把文件切成小块，用merge sort排序，然后去重就简单了。
不过你这要的是速度，一起坐等高手咯{:3_193:}
作者: MMMIX    时间: 2014-05-22 09:52
本帖最后由 MMMIX 于 2014-05-22 09:52 编辑

回复 1# gongyonghui2


    你现在效率不高的方法是什么？处理该文件需要多少时间/内存？
作者: MMMIX    时间: 2014-05-22 09:57
q1208c 发表于 2014-05-22 08:33
perl怕是不行了.


问题不大，除了输入文件重复行很少可能导致内存溢出。
作者: gongyonghui2    时间: 2014-05-22 10:42
回复 5# MMMIX


    用的是sort {$a<=>$b} 后join成字串，然后再用hash去重复，但是sort的时间跑了大概20分钟还没有sort完，内存不够了。
作者: MMMIX    时间: 2014-05-22 11:32
本帖最后由 MMMIX 于 2014-05-22 11:33 编辑

回复 7# gongyonghui2


    完整的代码贴上来看看。另外，你机器有多少内存？

2楼的代码你测试过么？什么结果？
作者: gongyonghui2    时间: 2014-05-22 13:46
本帖最后由 gongyonghui2 于 2014-05-22 13:54 编辑

回复 8# MMMIX
  1. open IN,"tt1.txt";
  2. open OU,">","result.txt";
  3. my %hash=();

  5. while(<IN>){
  6.         chomp;
  7.         my $tmp=join "\t",sort {$a<=>$b} split /\t/;       
  8.         $hash{$tmp}++;
  9. }
  10. print "sortDone\n";
  11. while(my ($cc)=each %hash){
  12.         print OUT $cc,"\n";       
  13. }
复制代码
机器6G内存,2楼代码原理一样，也是用hash去重，命令行运行出错
作者: timespace    时间: 2014-05-22 14:03
  1. >>> 150*1000*1000*12/(1024*1024)
  2. 1716.61376953125
复制代码
每个数字用32位为整数存储，内存就有1700MB，加上内部数据结构，估计物理内存hold不住了，一旦用上交换，那就遥遥无期了。这个例子更适合shell的“sort -n -k...”，自动处理外部排序。
作者: 不能超过15字    时间: 2014-05-22 14:19
sort -u 不行嘛
作者: timespace    时间: 2014-05-22 14:24
当标准方法不能一步到位时，也可以考虑分而治之。具体如何划分取决于第一列数值的分布，比如以取模（第一列数值 % 10）来划为10个文件，每个文件的去重相互独立独立，最后合并。这个文件大小对于磁盘连续IO是没有压力的，但可以极大缓解内存的不足。
作者: MMMIX    时间: 2014-05-22 14:51
回复 9# gongyonghui2


    照理说，6G内存的机器处理这个数据文件不成问题。你用的是 64-bit 操作系统吧？
作者: MMMIX    时间: 2014-05-22 15:02
本帖最后由 MMMIX 于 2014-05-22 15:03 编辑

回复 12# timespace


    另外一个方法就是直接弄个数据库，把数据导入数据库，再导出就行了。
作者: timespace    时间: 2014-05-22 15:28
本帖最后由 timespace 于 2014-05-22 19:47 编辑

回复 14# MMMIX
惭愧，很久不用perl，理解错需求了。
   
作者: RE_HASH    时间: 2014-05-22 21:37
试试先用perl排序每行的三个数，再sort -u
作者: timespace    时间: 2014-05-23 18:18
这帖子没结果了。。。
好奇之下，下了LZ的数据文件，解压2.5GB，还好电脑内存16GB，按照前面你们的perl代码执行前50M行（总数的1/3），物理内存占用超过6GB，意味着全部数据16GB内存都可能hold不住：
  1. $ head -50000000 tt1.txt | ./reduce.pl
  2.   PID  %CPU %MEM    RSS NSWAP ELAPSED COMM
  3.   479  99.1 40.0 6711876     -   01:34 /usr/bin/perl
复制代码
其实看这个50M，只要内存够，执行时间1分34秒，还能等。

把原文件按照每行排序后的最大数字，模11，分为11个文件，每个文件行数分布比较均匀：
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;

  5. my $modulo = 11;
  6. my @files = ();

  8. for (0 .. $modulo-1) {
  9.     open $files[$_], ">", "map_$_.txt"
  10.         or die "could not open map_$_.txt: $!";
  11. }

  13. while (<>) {
  14.     chomp;
  15.     my ($f1, $f2, $f3) = sort {$a <=> $b} split /\t/;
  16.     print {$files[$f3 % $modulo]} "$f1\t$f2\t$f3\n";
  17. }
复制代码
  1. 13282037 13358435 13856488 13894659 13915435 14064033 14125693 14858455 14869804 15549080 16652976
复制代码
最后对每个文件再运行你们的perl代码，生成11个新的文件就是最终结果，wc统计了下，重复行不到1%，印证了开始的想法，16GB内存都搞不定，必须切割小文件处理。

作者: gongyonghui2    时间: 2014-05-23 19:40
回复 17# timespace


    非常感谢
作者: gongyonghui2    时间: 2014-05-23 19:48
谢谢大家，此贴收尾
作者: MMMIX    时间: 2014-05-23 21:36
回复 17# timespace


    不科学呀，这内存占用的也太多了点。
作者: fender0107401    时间: 2014-05-23 23:51
这个问题有很多种解决方法，我感觉最好利用数据自身的特点，lz贴出来的数据似乎有些规律性可以利用。
作者: timespace    时间: 2014-05-24 11:51
本帖最后由 timespace 于 2014-05-24 11:52 编辑

回复 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;

  5. # SvNULL (ANY, REFCNT, FLAGS & Type)
  6. my $SvNULL_size = 8*3;

  8. # SvPV (SvNULL, PVX, CUR, LEN)
  9. my $SvPV_size = $SvNULL_size + 8*3;

  11. # SvIV (SvNULL, IVX/NVX)
  12. my $SvIV_size = $SvNULL_size + 8;

  14. # HE (next, hek, val)
  15. my $bucket_size = 8;
  16. my $entry_size = 8*3 + 8*2 + $SvIV_size + $bucket_size;

  18. # HV
  19. my $entrys = 150e6;
  20. my $HV_size_min = $entrys * $entry_size;

  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    时间: 2014-05-24 13:01
本帖最后由 MMMIX 于 2014-05-24 13:02 编辑

回复 22# timespace


    我拿楼主提供的数据实际测试了一下，16M的数据（无重复），在运行时最多要占用 86M 多的空间，差不多是实际数据的五倍多。这 hash 快是快，可是占用空间也太多了点。
作者: huang6894    时间: 2014-05-27 16:39
本帖最后由 huang6894 于 2014-05-27 16:52 编辑

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


作者: laputa73    时间: 2014-05-27 20:26
本帖最后由 laputa73 于 2014-05-27 21:30 编辑

回复 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";

  15. while(my ($cc)=each %hash){
  16.         print OUT $cc,"\n";        
  17. }
复制代码
测试了一下，处理前10M行，使用内存440M,1分多钟。
6G内存应该够用。
作者: zhlong8    时间: 2014-05-27 20:33
回复 22# timespace


    http://cpansearch.perl.org/src/RURBAN/illguts-0.47/index-18.html
作者: timespace    时间: 2014-05-27 20:56
回复 26# zhlong8
太强大了，3ks。扫了一眼，内存确实变得更多了。


   
作者: luwp    时间: 2014-06-30 14:54
本帖最后由 luwp 于 2014-06-30 14:55 编辑

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

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


sort命令不会把内存弄爆的



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2