免费注册 查看新帖 |

Chinaunix

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

perl递归问题 [复制链接]

论坛徽章:
0
发表于 2010-05-13 21:28 |显示全部楼层
本帖最后由 riverlee2008 于 2010-05-13 21:29 编辑

有个文件,两列,第一列是子节点,第二列表示父亲几点,程序出来就是一个树(有向无环图,如下图), 想做的事情是给定一个节点,想找出它的所有子孙节点, 程序已经实现,通过递归,对于树中较底层的结点,获取子孙节点没有问题, 但对于树中较上层的节点,递归出现 Deep recursion on subroutine "main::findnodes",内存飙到48G以上(本机内存大小48G), 且递归次数超过140000000次多.

现将程序和数据文件附上,忘论坛内高手指点指点,或者给个别的思路(详细程序数据见附件).

  1. #!/usr/bin/perl

  2. use strict;
  3. use warnings;

  4. ###############################
  5. #usage
  6. #test1:  perl findoffspring.pl do_ontology_926.txt DOID:3211
  7. #test2:  perl findoffspring.pl do_ontology_926.txt DOID:4
  8. #test1 work fine, but test2 didnot work fine, where DOID:4 is the top node in the tree
  9. my($child2parentfile,$searchnode) = @ARGV;


  10. #child id 2 parent id
  11. #"do_id","parent_do_id"
  12. my %parent2child;
  13. my %doids;
  14. open(IN,$child2parentfile) or die $!;
  15. <IN>;#skip the header
  16. while(<IN>){
  17.         s/[\r\n"]//g;
  18.         my($c,$p) = split "\t";
  19.         $parent2child{$p}->{$c}=1;
  20.         $doids{$c}=1;
  21.         $doids{$p}=1;
  22. }       

  23. print "DO num:",scalar keys %doids,"\n";


  24. #######################################
  25. #构建一个变量用来记录其所有的offspring
  26. my $rr={};
  27. findnodes("DOID:4",\%parent2child,$rr);

  28. print join "\n",(keys %{$rr});

  29. #use recursion to find the offspring nodes
  30. #here  defined the variable to see how many time we call the findnodes
  31. my $count=0;
  32. sub findnodes{
  33.         my($search,$ref,$resultref)=@_;
  34.         $count++;
  35.         if($count % 20000 ==0){
  36.                 print "recursion:",$count,"\n";
  37.         }
  38.         if(exists($ref->{$search})){
  39.                 foreach my $node(keys %{$ref->{$search}}){
  40.                         $resultref->{$node}=1;
  41.                         findnodes($node,$ref,$resultref);
  42.                 }
  43.         }else{
  44.                 return $resultref;
  45.         }
  46. }

复制代码

ask_help_CU.tar.bz2 (55.38 KB, 下载次数: 75)

论坛徽章:
0
发表于 2010-05-13 21:41 |显示全部楼层
路过要回帖的啊~~

论坛徽章:
0
发表于 2010-05-13 23:47 |显示全部楼层
我想楼主的程序本身应该没问题,而是因为数据的问题,造成死循环,大量消耗内存,最终死机。

写了段代码,查出有重复数据:DOID:833,DOID:833,duplicated
  1. #!/usr/bin/perl

  2. use strict;
  3. use warnings;

  4. my %p2c;
  5. my $child2parentfile = "do_ontology_926.txt";
  6. open(IN,$child2parentfile) or die $!;
  7. <IN>;#skip the header
  8. my @lines = <IN>;
  9. close IN;
  10. foreach(@lines){
  11.         s/[\r\n"]//g;
  12.         my($c,$p) = split "\t";
  13.         $p2c{$p}{$c}++;
  14. }

  15. foreach(@lines){
  16.         s/[\r\n"]//g;
  17.         my($c,$p) = split "\t";
  18.         if ($p2c{$p}{$c} > 1) { print "$c,$p,$p2c{$p}{$c}\n"; }
  19.         if ($p2c{$p}{$c} && $p2c{$c}{$p}) { print "$c,$p,duplicated\n"; }
  20. }

  21. <STDIN>;
复制代码
删除重复的错误数据,程序运行正常!

论坛徽章:
0
发表于 2010-05-14 00:01 |显示全部楼层
回复 3# iamlimeng

    多谢指出问题,我看看去,继续关注~

论坛徽章:
0
发表于 2010-05-14 00:29 |显示全部楼层
回复 3# iamlimeng


    验证完毕,多谢3楼道兄弟~

论坛徽章:
0
发表于 2010-05-14 08:48 |显示全部楼层
能给出原文件的例子吗?我也练习练习

论坛徽章:
0
发表于 2010-05-14 09:08 |显示全部楼层
附件的 原文件下载后不对啦。请LZ传一个原文件。

论坛徽章:
0
发表于 2010-05-14 09:14 |显示全部楼层
ok,好了,下载后改了后缀,哈哈

论坛徽章:
0
发表于 2010-05-14 10:05 |显示全部楼层
路过 学习中。

论坛徽章:
0
发表于 2010-05-14 10:30 |显示全部楼层
<IN>;#skip the header??
作用:skip the header?

还有 lz 能否讲讲 sub findnodes 实现的说明,小弟不胜感激!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP