亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標題: perl遞歸問題 [打印本頁]
作者: riverlee2008    時間: 2010-05-13 21:28
標題: perl遞歸問題
本帖最后由 riverlee2008 于 2010-05-13 21:29 編輯

有個文件,兩列,第一列是子節(jié)點,第二列表示父親幾點,程序出來就是一個樹(有向無環(huán)圖,如下圖), 想做的事情是給定一個節(jié)點,想找出它的所有子孫節(jié)點, 程序已經實現(xiàn),通過遞歸,對于樹中較底層的結點,獲取子孫節(jié)點沒有問題, 但對于樹中較上層的節(jié)點,遞歸出現(xiàn) Deep recursion on subroutine "main::findnodes",內存飆到48G以上(本機內存大小48G), 且遞歸次數(shù)超過140000000次多.

現(xiàn)將程序和數(shù)據(jù)文件附上,忘論壇內高手指點指點,或者給個別的思路(詳細程序數(shù)據(jù)見附件).

  1. #!/usr/bin/perl

  3. use strict;
  4. use warnings;

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


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

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


  31. #######################################
  32. #構建一個變量用來記錄其所有的offspring
  33. my $rr={};
  34. findnodes("DOID:4",\%parent2child,$rr);

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

  38. #use recursion to find the offspring nodes
  39. #here  defined the variable to see how many time we call the findnodes
  40. my $count=0;
  41. sub findnodes{
  42.         my($search,$ref,$resultref)=@_;
  43.         $count++;
  44.         if($count % 20000 ==0){
  45.                 print "recursion:",$count,"\n";
  46.         }
  47.         if(exists($ref->{$search})){
  48.                 foreach my $node(keys %{$ref->{$search}}){
  49.                         $resultref->{$node}=1;
  50.                         findnodes($node,$ref,$resultref);
  51.                 }
  52.         }else{
  53.                 return $resultref;
  54.         }
  55. }

復制代碼

ask_help_CU.tar.bz2 (55.38 KB, 下載次數(shù): 75)


作者: riverlee2008    時間: 2010-05-13 21:41
路過要回帖的啊~~
作者: iamlimeng    時間: 2010-05-13 23:47
我想樓主的程序本身應該沒問題，而是因為數(shù)據(jù)的問題，造成死循環(huán)，大量消耗內存，最終死機。

寫了段代碼，查出有重復數(shù)據(jù)：DOID:833,DOID:833,duplicated
  1. #!/usr/bin/perl

  3. use strict;
  4. use warnings;

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

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

  25. <STDIN>;
復制代碼
刪除重復的錯誤數(shù)據(jù)，程序運行正常！
作者: riverlee2008    時間: 2010-05-14 00:01
回復 3# iamlimeng

    多謝指出問題，我看看去，繼續(xù)關注～
作者: riverlee2008    時間: 2010-05-14 00:29
回復 3# iamlimeng


    驗證完畢，多謝3樓道兄弟～
作者: liyangole    時間: 2010-05-14 08:48
能給出原文件的例子嗎？我也練習練習
作者: liyangole    時間: 2010-05-14 09:08
附件的 原文件下載后不對啦。請LZ傳一個原文件。
作者: liyangole    時間: 2010-05-14 09:14
ok,好了，下載后改了后綴，哈哈
作者: liyangole    時間: 2010-05-14 10:05
路過 學習中。
作者: liyangole    時間: 2010-05-14 10:30
<IN>;#skip the header？？
作用：skip the header?

還有 lz 能否講講 sub findnodes 實現(xiàn)的說明，小弟不勝感激！
作者: yybmsrs    時間: 2010-05-14 19:31
回復 10# liyangole


    根據(jù)給出的節(jié)點找子節(jié)點，然后再找子節(jié)點的子節(jié)點，一直到找不到為止。
作者: riverlee2008    時間: 2010-05-16 10:27
回復 10# liyangole


    就是一個遞歸,慢慢研究吧, :wink:
作者: 唐歸來    時間: 2016-04-05 08:40
路過學習了。。。
作者: rubyish    時間: 2016-05-11 03:49
youyishi ~~



歡迎光臨 Chinaunix (http://www.72891.cn/) Powered by Discuz! X3.2