perl - 使用 perl 创建层次文件

Question

我的任务是使用 perl 创建一个父子层次结构文件。

示例输入文件(制表符分隔)。记录将按随机顺序排列在文件中，“父”可能出现在“子”之后。

 S5 S3
 S5 S8
 ROOT   S1
 S1 S7
 S2 S5
 S3 S4
 S1 S2
 S4 77
 S2 S9
 S3 88

示例输出文件(制表符分隔)

ROOT    S1  S2  S5  S3  S4  77
ROOT    S1  S2  S5  S3  88
ROOT    S1  S7
ROOT    S1  S2  S5  S8
ROOT    S1  S2  S9

产生上述输出文件的代码

use strict;

# usage: perl parent_child_generator.pl input.txt output.txt

my $input0=$ARGV[0] or die "must provide input.txt as the first argument\n";
my $output1=$ARGV[1] or die "must provide output.txt as the second argument\n";

open(IN0,"<",$input0) || die "Cannot open $input0 for reading: $!";
open(OUT1,">",$output1) || die "Cannot open $output1 for writing: $!";

sub trim
{
    my $string=shift;
$string=~s/\r?\n$//;
$string=~s/^\s+//;
$string=~s/\s+$//;
return $string;
}

sub connectByPrior
{
my $in_child=$_[0];
my %in_hash=%{$_[1]};
my @anscestor_arr;

for (sort keys %in_hash)
{
    my $key=$_;
    my @key_arr=split(/\t/,$key);
    my $parent=$key_arr[0];
    my $child=$key_arr[1];

    if ($in_child eq $child)
    {
        push (@anscestor_arr,$parent);
        @anscestor_arr=(@{connectByPrior($parent,\%in_hash)},@anscestor_arr);
        last;
    }
}
return \@anscestor_arr;
}

my %parent_hash;
my %child_hash;
my %unsorted_hash;
while(<IN0>)
{
my @cols=split(/\t/);
for (my $i=0; $i < scalar(@cols); $i++)
{
    $cols[$i]= trim($cols[$i]);
}

my $parent=$cols[0];
my $child=$cols[1];
my $parent_child="$parent\t$child";

$parent_hash{$parent}=1;
$child_hash{$child}=1;
$unsorted_hash{$parent_child}=1;
 }
 close(IN0);

my @lev0_arr;
for (sort keys %child_hash)
{
my $rec=$_;
if (!exists($parent_hash{$rec}))
{
    push (@lev0_arr,$rec);
}
}

for (@lev0_arr)
{
my $child=$_;
my @anscestor_arr=@{connectByPrior($child,\%unsorted_hash)};
push (@anscestor_arr,$child);
print OUT1 join("\t",@anscestor_arr)."\n";
}

问题:如果输入文件不是太大，代码工作正常。实际输入文件包含超过 200k 行，并且代码处理输出所用的时间太长。您建议进行哪些改进/更改，以免处理时间过长？

Answer 1

您似乎正在尝试构建和漂亮地打印有向图:

#!/usr/bin/perl

use strict; use warnings;
use Graph::Directed;
use Graph::TransitiveClosure::Matrix;

 my $g = Graph::Directed->new;

while ( my $line = <DATA> ) {
    next unless my ($x, $y) = split ' ', $line;
    $g->add_edge($x, $y);
}

my @start = $g->source_vertices;
my @end   = $g->sink_vertices;

my $tcm = Graph::TransitiveClosure::Matrix->new( $g,
    path_vertices => 1,
);

for my $s ( @start ) {
    for my $e ( @end ) {
        next unless $tcm->is_reachable($s, $e);
        print join("\t", $tcm->path_vertices($s, $e)), "\n";
    }
}

__DATA__
S5 S3
S5 S8
ROOT   S1
S1 S7
S2 S5
S3 S4
S1 S2
S4 77
S2 S9
S3 88

输出:

根 S1 S2 S9
根 S1 S2 S5 S8
根 S1 S2 S5 S3 S4 77
根 S1 S2 S5 S3 88
根 S1 S7

我不确定是否使用 Graph 的内存开销并计算 transitive closure matrix在你的情况下将是禁止的。