免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 14372 | 回复: 14

如何可以提高hash遍历的效率 [复制链接]

论坛徽章:
0
发表于 2018-05-10 10:39 |显示全部楼层
大家好!请教一个问题
对于$hash{$key}=A;
key value
1    4
10    15
$hash1{$key1}=B;
key value
2     3
3     6
假设这两个hash的键和值分别指代的都是数值,如果进行值比较
foreach my $key (sort keys %hash){
       foreach my $key1 (sort keys %hash1){
              if($key>=$key)&&($key<=$hash{$key}){
                   print ........
              }
}
}   
当涉及到进行键 值的比较的时候,且文件很大很大的时候假设几百万行,再进行if中的判断 就非常非常慢,因为会读完所有的值再判断,我可以如何修改才能提高hash遍历的效率呢?
谢谢大家了!

论坛徽章:
0
发表于 2018-05-10 10:58 |显示全部楼层
你把两个大文件都读入内存,要考虑你电脑的内存容量,数据量大的情况,这种方法不可取,严重的会导致内存耗尽死机。

应该改变算法,逐行进行对比判断,或者一次读取少量的行进行对比判断。

论坛徽章:
12
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2018-03-16 10:24:0515-16赛季CBA联赛之山东
日期:2017-11-10 14:32:142016科比退役纪念章
日期: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联赛之北京
日期:2019-08-13 17:30:53
发表于 2018-05-10 11:16 |显示全部楼层
本帖最后由 523066680 于 2018-05-10 11:23 编辑

如果数据量大,sort keys %hash 会占用大量内存,两层 for + sort keys 消耗更大。
首先把 内层的 foreach my $key1 (sort keys %hash1){ 中的 sort keys %hash1 先存储起来,就会节省很多消耗。

  1. my @keys1 = sort keys %hash1;

  2. for my $key (sort keys %hash) {
  3.     for my $key1 ( @keys1 ) {
  4.         if ( ($key >= $key ) && ( $key <= $hash{$key} ) ) {
  5.             print ........
  6.         }
  7.     }
  8. }
复制代码

另外你这个 $key >= $key 是不是写错了,如果爆内存,for 换成 while,改用迭代的形式。

哈希可以 while ( ($k, $v) = each %hash )
数组可以用索引迭代。

论坛徽章:
0
发表于 2018-05-10 15:20 |显示全部楼层
本帖最后由 Chinaaa123 于 2018-05-10 15:22 编辑

回复 3# 523066680
是的,那里漏打了一个1!谢谢你的回答,如果我改为这样:
$sum=0;
while(($key1,$value1)=each %hash1){
        while(($key,$value)=each %hash){  #这种是每一行进行判断,也会加快速度吧?如果改为for(@key),因为我还要对$value进行一个累加,提前存进数组的话,用的时候是这样for(@key){for (@value){...}}就又复杂了!不好意思 格式有些乱!###
              if(($key>=$key1)&&($key<=$value1)){
              $sum+=$value;
              }
       }
}


论坛徽章:
42
19周年集字徽章-周
日期:2019-10-14 14:35:31平安夜徽章
日期:2015-12-26 00:06:30数据库技术版块每日发帖之星
日期:2015-12-01 06:20:002015亚冠之首尔
日期:2015-11-04 22:25:43IT运维版块每日发帖之星
日期:2015-08-17 06:20:00寅虎
日期:2014-06-04 16:25:27狮子座
日期:2014-05-12 11:00:00辰龙
日期:2013-12-20 17:07:19射手座
日期:2013-10-24 21:01:23CU十二周年纪念徽章
日期:2013-10-24 15:41:34IT运维版块每日发帖之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之新疆
日期:2016-06-07 14:10:01
发表于 2018-05-11 08:45 |显示全部楼层
两重遍历是很低效的
内层既然要排序,要考虑折半查找等等这些基本的快速查找算法.
或者用数据库啊.都有主键索引了,比你遍历的效率高多了.

论坛徽章:
0
发表于 2018-05-12 10:19 |显示全部楼层
本帖最后由 Chinaaa123 于 2018-05-12 10:23 编辑
laputa73 发表于 2018-05-11 08:45
两重遍历是很低效的
内层既然要排序,要考虑折半查找等等这些基本的快速查找算法.
或者用数据库啊.都有主 ...


你好,非常感谢提供的折半算法;但是我还有个疑问,这种算法是针对一个数组而言假设@a=/1..10000/,在里面二分查找(从1到10000都有值的情况). 我的A文件中是这样的:每一行是一个区间且只有这个区间的首尾值
10000 25000
35000 40000
...
然后我的B文件是: 如果B文件的第二列在上述A文件中的某个区间内,那么其后面第三列的value就相加,这个例子就是应该输出
10000 25000 (value1+value2+value3)这样
B文件是这样:
xx 10001 value1
xx 10002 value2
xx 15000 value3
.......
那么使用折半算法 我是不是没读一行就把这一行表示的区间作为一个数组且使其中加入值,这样是不是就更加复杂了呢?

论坛徽章:
42
19周年集字徽章-周
日期:2019-10-14 14:35:31平安夜徽章
日期:2015-12-26 00:06:30数据库技术版块每日发帖之星
日期:2015-12-01 06:20:002015亚冠之首尔
日期:2015-11-04 22:25:43IT运维版块每日发帖之星
日期:2015-08-17 06:20:00寅虎
日期:2014-06-04 16:25:27狮子座
日期:2014-05-12 11:00:00辰龙
日期:2013-12-20 17:07:19射手座
日期:2013-10-24 21:01:23CU十二周年纪念徽章
日期:2013-10-24 15:41:34IT运维版块每日发帖之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之新疆
日期:2016-06-07 14:10:01
发表于 2018-05-14 08:36 |显示全部楼层
本帖最后由 laputa73 于 2018-05-14 08:46 编辑

回复 6# Chinaaa123

1.先不考虑外层排序的情况.外层直接遍历.
比如第二行35000 40000
那么问题就是从B文件里面找到第二列落在这个区间的行.
B文件如果是排序好的, 可以针对第二列,按照二分查找可以快速定位到落在这个区间的首行, 而不需要逐行遍历.(前提B文件不是特别大,可以装载为数组)
  ps. 使用查找算法的前提是B的数据比较稀疏, 存在很多不落在A区间的数据
        如果B的数据全部或者大多数落在A的区间,那么无需查找, 顺序遍历就好了.
找到第一行以后,就逐行遍历直到超出区间.
然后重复A的下一行

2.进一步的优化.如果A也是排序的
那么已经找过的区间,在B里面就不需要继续找了.
比如第一行10000~25000匹配以后, 可以把B里面<=这个区间的直接splice掉,这样B数组越来越小,后续的查找就会更快.


论坛徽章:
0
发表于 2018-05-14 15:02 |显示全部楼层
本帖最后由 Chinaaa123 于 2018-05-15 17:12 编辑

回复 7# laputa73
多谢,我试试


论坛徽章:
0
发表于 2018-05-15 17:11 |显示全部楼层
回复 7# laputa73

这个该如何写呢?写了好久还是出不来!

论坛徽章:
42
19周年集字徽章-周
日期:2019-10-14 14:35:31平安夜徽章
日期:2015-12-26 00:06:30数据库技术版块每日发帖之星
日期:2015-12-01 06:20:002015亚冠之首尔
日期:2015-11-04 22:25:43IT运维版块每日发帖之星
日期:2015-08-17 06:20:00寅虎
日期:2014-06-04 16:25:27狮子座
日期:2014-05-12 11:00:00辰龙
日期:2013-12-20 17:07:19射手座
日期:2013-10-24 21:01:23CU十二周年纪念徽章
日期:2013-10-24 15:41:34IT运维版块每日发帖之星
日期:2016-01-27 06:20:0015-16赛季CBA联赛之新疆
日期:2016-06-07 14:10:01
发表于 2018-05-17 09:34 |显示全部楼层
本帖最后由 laputa73 于 2018-05-17 11:43 编辑

大概齐是这个意思

  1. #!/bin/env/perl


  2. my @A=([10000,25000,0],[35000,40000,0]);

  3. my $a=shift @A;
  4. my $match=0;
  5. while (<DATA>){
  6.         my @b= split /,/,$_;
  7.         if (($b[1] >= $a->[0]) && ($b[1] <= $a->[1])){
  8.                 $a->[2]+=$b[2];
  9.                 print "$a->[0],$a->[1],$a->[2]\n";
  10.                 $match=1;
  11.   }
  12.   elsif($match !=0){
  13.           $a=shift @A;
  14.           $match=0;
  15.   }
  16.         
  17. }


  18. __DATA__
  19. 'xx',9000,1
  20. 'xx',10001,111
  21. 'xx',10002,222
  22. 'xx',15000,333
  23. 'xx',30000,444
  24. 'xx',32000,444
  25. 'xx',33000,444
  26. 'xx',36001,555
  27. 'xx',46001,555
  28. #10000,25000,111
  29. #10000,25000,333
  30. #10000,25000,666
  31. #35000,40000,555
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP