忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
1234567
最近访问板块 发新帖
楼主: Windows19

字符串排序 [复制链接]

论坛徽章:
22
2015年亚洲杯之科威特
日期:2015-04-18 15:27:07每日论坛发贴之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之广夏
日期:2016-03-28 16:20:51程序设计版块每日发帖之星
日期:2016-04-09 06:20:00CU十四周年纪念徽章
日期:2016-05-03 09:35:1415-16赛季CBA联赛之天津
日期:2016-11-18 08:31:3115-16赛季CBA联赛之山西
日期:2016-12-07 16:29:5315-16赛季CBA联赛之八一
日期:2017-01-10 11:34:3415-16赛季CBA联赛之吉林
日期:2017-03-30 22:51:1915-16赛季CBA联赛之广夏
日期:2017-04-13 20:51:52程序设计版块每日发帖之星
日期:2016-01-27 06:20:00每日论坛发贴之星
日期:2015-12-28 06:20:00
发表于 2017-06-22 12:24 |显示全部楼层
回复 60# 523066680

3q加了

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-06-22 21:23 |显示全部楼层
本帖最后由 523066680 于 2017-06-23 09:25 编辑

新学了一个模块 - DB_File,不熟练。
优点:占用内存少
缺点:特别耗时

处理机制:参考63楼

  1. =info
  2.     Code by 523066680
  3.     2017-06
  4. =cut

  5. #!/usr/bin/perl
  6. use Fcntl;
  7. use DB_File;
  8. use IO::Handle;
  9. use Data::Dumper;
  10. use Time::HiRes qw/sleep/;
  11. STDOUT->autoflush(1);

  12. our $SRC = "D:/A.txt";
  13. our $DST = "D:/Final.txt";
  14. our $FH_SRC;
  15. our $FH_DST;
  16. our $DB_KEY    = "F:/keywords.dat";
  17. our $DB_LINE   = "F:/lines.dat";
  18. our $DB_OFFSET = "F:/line_offset.dat";
  19. our $DB_SORT   = "F:/sort.dat";

  20. our $fold = "D:/tempfolder_words";  #尽可能独立的目录名称

  21. our %keywords;
  22. our @lines;
  23. our @offset;   #保存每一行的索引位置+长度
  24. our %rank;     #每行的元素次数信息

  25. unlink $DB_KEY;
  26. unlink $DB_LINE;
  27. unlink $DB_OFFSET;
  28. unlink $DB_SORT;

  29. tie %keywords, "DB_File", $DB_KEY, O_WRONLY|O_CREAT, 0666, $DB_BTREE or die $!;
  30. tie @lines, "DB_File", $DB_LINE, O_WRONLY|O_CREAT, 0666, $DB_RECNO or die $!;
  31. tie @offset, "DB_File", $DB_OFFSET, O_WRONLY|O_CREAT, 0666, $DB_RECNO or die $!;

  32. # 排序函数设置
  33. $DB_BTREE->{'compare'} = \&Compare ;
  34. tie %rank, "DB_File", $DB_SORT, O_WRONLY|O_CREAT, 0666, $DB_BTREE or die $!;

  35. #our %rank;           #等级索引

  36. LOAD_DATA:
  37. {
  38.     print "Loading ... \n";
  39.     open $FH_SRC, "<:raw", $SRC or die $!;

  40.     my $filesize = -s $SRC;
  41.     my $curr = 0;
  42.     my $prev = 0;

  43.     my $time_a = time();
  44.     my $percent;

  45.     #每行的偏移量
  46.     my $offsetA = 0;
  47.     my $offsetB;
  48.     my @parts;

  49.     #单行的重复关键词判断
  50.     my %inline;

  51.     while ( my $line = <$FH_SRC>)
  52.     {
  53.         #next if ($line=~/^\s*\r?\n$/);  #排除空行
  54.         %inline = ();
  55.         @parts = $line =~/([a-zA-Z]+|[\d]+)/g;

  56.         #累积关键字出现的次数
  57.         for my $e (@parts)
  58.         {
  59.             if ( not exists $keywords{$e} ) { $keywords{$e} = 1    }
  60.             else { $keywords{$e}++ if (not exists $inline{$e}) }

  61.             $inline{$e} = 1;
  62.         }

  63.         #每行的关键字数据
  64.         push @lines, join(",", keys %inline);

  65.         #每行的偏移量和长度信息
  66.         $offsetB = tell( $FH_SRC );
  67.         push @offset, join(",", $offsetA, $offsetB - $offsetA);

  68.         #更新起点位置
  69.         $offsetA = tell( $FH_SRC );

  70.         $curr = $offsetA / $filesize * 100.0;
  71.         if ( ($curr - $prev) > 1.0  )
  72.         {
  73.             print ".";
  74.             $prev = $curr;
  75.         }
  76.         
  77.     }
  78.     print "\n";

  79.     close $FH_SRC;

  80.     printf "Time use: %s seconds\n", time()- $time_a;
  81. }

  82. ANALYSE_AND_SORT:
  83. {
  84.     my $time_a = time();
  85.     print "Sorting key of each line ... \n";

  86.     #利用 DB_File 机制排序
  87.     for my $idx ( 0 .. $#lines )
  88.     {
  89.         # key = 行号,每个关键字的次数(从大到小)
  90.         $key = join ( ",", $idx,
  91.                     reverse sort { $a <=> $b } map { $keywords{$_} } split(",", $lines[$idx])
  92.                 );

  93.         # value = 该行的位置索引
  94.         $rank{$key} = $offset[$idx];
  95.     }

  96.     printf "Time use: %s seconds\n", time()- $time_a;
  97. }

  98. FINAL_OUTPUT:
  99. {
  100.     print "Almost finish\n";

  101.     my $time_a = time();
  102.     my ($k, $v);
  103.     my ($site, $len);
  104.     my $buff;

  105.     open $FH_SRC, "<:raw", $SRC or die $!;
  106.     open $FH_DST, ">:raw", $DST or die $!;

  107.     while ( ($k, $v) = each %rank )
  108.     {
  109.         ($site, $len) = split(",", $v);
  110.         seek($FH_SRC, $site, 0);
  111.         read($FH_SRC, $buff, $len);
  112.         $buff=~s/\r?\n$//;
  113.         print $FH_DST $buff,"\r\n";
  114.     }

  115.     close $FH_SRC;
  116.     close $FH_DST;

  117.     printf "Time use: %s seconds\n", time() - $time_a;

  118.     untie %keywords;
  119.     untie @lines;
  120.     untie @offset;
  121.     untie %rank;
  122. }

  123. sub Compare
  124. {
  125.     my ($ka, $kb) = @_ ;
  126.     my @ar = split(",", $ka);
  127.     my @br = split(",", $kb);
  128.     my $i = 1;

  129.     while ( ($ar[$i] <=> $br[$i] ) == 0
  130.             and $#ar > $i
  131.             and $#br > $i
  132.             #and $i < 3
  133.         ) {  $i++;  }
  134.    
  135.     $br[$i] <=> $ar[$i]  ||  $#br <=> $#ar || $br[0] <=> $ar[0];
  136.     #如果最后一位相同,比较元素数量;如果数量相同,按下标大小排列
  137. }

  138. __END__
复制代码

评分

参与人数 1信誉积分 +10 收起 理由
Windows19 + 10 再赏

查看全部评分

1人打赏

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-06-22 23:12 |显示全部楼层
本帖最后由 523066680 于 2017-06-23 15:04 编辑

以原贴的段落为例,
[0]65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
[1]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
[2]yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5
[3]efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
[4]efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
[5]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
[6]65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com

处理结果:
[1]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33sdds1
[0]65425855662efssaezsdfcsf//sff.sdf/'s;f]\sDed33dds3
[5]65425855662efssaezsdfcsf/        /sff.sdf/'s;f]  \sDed33s00000000
[4]efssaezsdfcsf/        58969752/sff.sdf/'s;f]  \sDed33sdds5
[3]efssaezsdfcsf//58969752sff.sdf/'s;f]\sDed33sds0
[6]65425855662efs\saezsdf][grytryg*f-x+f5g5ty'5t;54r]\5/e.,6ftfr//www.fsfsf.com
[2]yjyjgwwwghfg56www g.tgjgcom445.5454.'55.4l5

每行的关键字在全文中出现的次数统计(单行内多次计为一次)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),65425855662(4),3(1),dds(1)
f(6),s(5),sff(5),efssaezsdfcsf(5),33(5),sdf(5),sDed(5),65425855662(4),sdds(2),1(1)
5(3),g(2),www(2),yjyjgwwwghfg(1),56(1),445(1),tgjgcom(1),4(1),l(1),5454(1),55(1)
f(6),33(5),sdf(5),sDed(5),s(5),sff(5),efssaezsdfcsf(5),58969752(2),0(1),sds(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),5(3),sdds(2),58969752(2)
f(6),efssaezsdfcsf(5),s(5),sff(5),sDed(5),sdf(5),33(5),65425855662(4),00000000(1)
f(6),65425855662(4),5(3),g(2),www(2),x(1),ftfr(1),e(1),com(1),54(1),t(1),ty(1),fsfsf(1),grytryg(1),efs(1),r(1),6(1),saezsdf(1)

处理后的顺序(按行排序,从最高的频率开始对比;如果最高的次数相同,则对比第二列,以此类推)
f(6),s(5),sff(5),efssaezsdfcsf(5),33(5),sdf(5),sDed(5),65425855662(4),sdds(2),1(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),65425855662(4),3(1),dds(1)
f(6),efssaezsdfcsf(5),s(5),sff(5),sDed(5),sdf(5),33(5),65425855662(4),00000000(1)
f(6),efssaezsdfcsf(5),sff(5),s(5),sDed(5),33(5),sdf(5),5(3),sdds(2),58969752(2)
f(6),33(5),sdf(5),sDed(5),s(5),sff(5),efssaezsdfcsf(5),58969752(2),0(1),sds(1)
f(6),65425855662(4),5(3),g(2),www(2),x(1),ftfr(1),e(1),com(1),54(1),t(1),ty(1),fsfsf(1),grytryg(1),efs(1),r(1),6(1),saezsdf(1)
5(3),g(2),www(2),yjyjgwwwghfg(1),56(1),445(1),tgjgcom(1),4(1),l(1),5454(1),55(1)

纯数字,前后对比:
Before:
[0]6,5,5,5,5,5,5,4,1,1
[1]6,5,5,5,5,5,5,4,2,1
[2]3,2,2,1,1,1,1,1,1,1,1
[3]6,5,5,5,5,5,5,2,1,1
[4]6,5,5,5,5,5,5,3,2,2
[5]6,5,5,5,5,5,5,4,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1

After
[1]6,5,5,5,5,5,5,4,2,1
[0]6,5,5,5,5,5,5,4,1,1
[5]6,5,5,5,5,5,5,4,1
[4]6,5,5,5,5,5,5,3,2,2
[3]6,5,5,5,5,5,5,2,1,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1
[2]3,2,2,1,1,1,1,1,1,1,1


论坛徽章:
22
2015年亚洲杯之科威特
日期:2015-04-18 15:27:07每日论坛发贴之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之广夏
日期:2016-03-28 16:20:51程序设计版块每日发帖之星
日期:2016-04-09 06:20:00CU十四周年纪念徽章
日期:2016-05-03 09:35:1415-16赛季CBA联赛之天津
日期:2016-11-18 08:31:3115-16赛季CBA联赛之山西
日期:2016-12-07 16:29:5315-16赛季CBA联赛之八一
日期:2017-01-10 11:34:3415-16赛季CBA联赛之吉林
日期:2017-03-30 22:51:1915-16赛季CBA联赛之广夏
日期:2017-04-13 20:51:52程序设计版块每日发帖之星
日期:2016-01-27 06:20:00每日论坛发贴之星
日期:2015-12-28 06:20:00
发表于 2017-06-23 08:57 |显示全部楼层
回复 62# 523066680

嗯嗯  测试后基本正确  就是效率有点慢,  100m耗时59分钟左右  如果要处理超过100g  估计也得1个月左右
能否加快一点时间?  比如 使用多线程处理  现在好像只用1个cpu来处理   使用多线程处理 效率会不会再快些?

如果能优化效率就太好了

辛苦了  再赏



测试文件97.0 MB耗时
$ perl 123
Loading ...
Time: 538 seconds
Sorting key of each line ...
Almost finish
Time: 1391 seconds




麻烦在有空闲时间抽空关注一下看看能不能再改进一下  谢谢

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-06-23 09:27 |显示全部楼层
本帖最后由 523066680 于 2017-06-23 10:08 编辑

回复 64# Windows19

是在服务器跑吗,如果是100G,会生成大约 600G 的临时文件。
如果每行只取一个频率最高的词作为代表 (其他低频率不考虑,可以加快)

比如这两行的每个关键字的频率列表:
[5]6,5,5,5,5,5,5,4,1
[6]6,4,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1

如果只对比开头,都是6次,这两项数据并排,后面的不再对比。

-

不懂多线程 -_-

论坛徽章:
22
2015年亚洲杯之科威特
日期:2015-04-18 15:27:07每日论坛发贴之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之广夏
日期:2016-03-28 16:20:51程序设计版块每日发帖之星
日期:2016-04-09 06:20:00CU十四周年纪念徽章
日期:2016-05-03 09:35:1415-16赛季CBA联赛之天津
日期:2016-11-18 08:31:3115-16赛季CBA联赛之山西
日期:2016-12-07 16:29:5315-16赛季CBA联赛之八一
日期:2017-01-10 11:34:3415-16赛季CBA联赛之吉林
日期:2017-03-30 22:51:1915-16赛季CBA联赛之广夏
日期:2017-04-13 20:51:52程序设计版块每日发帖之星
日期:2016-01-27 06:20:00每日论坛发贴之星
日期:2015-12-28 06:20:00
发表于 2017-06-23 10:44 |显示全部楼层
523066680 发表于 2017-06-23 09:27
回复 64# Windows19

是在服务器跑吗,如果是100G,会生成大约 600G 的临时文件。

嗯嗯,ok  还是老师你的意路灵活,

论坛徽章:
0
发表于 2017-06-23 22:36 |显示全部楼层
这是个大工程,向523066680学习下。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP