11

ハッシュの配列を持っている、

my @arr = get_from_somewhere();

@arrの内容（たとえば）は次のとおりです。

@arr = (
  { id => "id2",    requires => 'someid', text => "another text2" },
  { id => "xid4",   requires => 'id2',    text => "text44" },
  { id => "someid", requires => undef,    text => "some text" },
  { id => "id2",    requires => 'someid', text => "another text2" },
  { id => "aid",    requires => undef,    text => "alone text" },
  { id => "id2",    requires => 'someid', text => "another text2" },
  { id => "xid3",   requires => 'id2',    text => "text33" },
);

次のようなものが必要です：

my $texts = join("\n",  get_ordered_texts(@arr) );

sooは、ハッシュからsの配列を返すsubを記述する必要がありtextます。これは、依存する順序であるため、上記の例から次のように取得する必要があります。

"some text",     #someid the id2 depends on it - so need be before id2
"another text2", #id2    the xid3 and xid4 depends on it - and it is depends on someid
"text44",        #xid4   the xid4 and xid3 can be in any order, because nothing depend on them
"text33",        #xid3   but need be bellow id2
"alone text",    #aid    nothing depends on aid and hasn't any dependencies, so this line can be anywhere

ご覧のとおり、@ arrには重複した「行」（上記の例では「id2」）が含まれている可能性があり、IDを1回だけ出力する必要があります。

開始方法がわからないため、まだコード例を提供していません。;（ソリューションに使用できるCPANモジュールがいくつかありますか？

誰かが私を正しい方向に向けることができますか？

4

4 に答える 4

13

グラフの使用：

use Graph qw( );

my @recs = (
   { id => "id2",    requires => 'someid', text => "another text2" },
   { id => "xid4",   requires => 'id2',    text => "text44" },
   { id => "someid", requires => undef,    text => "some text" },
   { id => "id2",    requires => 'someid', text => "another text2" },
   { id => "aid",    requires => undef,    text => "alone text" },
   { id => "id2",    requires => 'someid', text => "another text2" },
   { id => "xid3",   requires => 'id2',    text => "text33" },
);

sub get_ordered_recs {
   my %recs;
   my $graph = Graph->new();
   for my $rec (@_) {
      my ($id, $requires) = @{$rec}{qw( id requires )};

      $graph->add_vertex($id);
      $graph->add_edge($requires, $id) if $requires;

      $recs{$id} = $rec;
   }

   return map $recs{$_}, $graph->topological_sort();
}

my @texts = map $_->{text}, get_ordered_recs(@recs);
于 2012-08-28T19:58:27.877 に答える
4

興味深い問題。

これが私の最初の解決策です：

sub get_ordered_texts {
    my %dep_found;  # track the set of known dependencies
    my @sorted_arr; # output

    my $last_count = scalar @_; # infinite loop protection
    while (@_ > 0) {
        for my $value (@_) {

            # next unless we are ready for this text
            next if defined $value->{requires}
                and not $dep_found{ $value->{requires} };

            # Add to the sorted list
            push @sorted_arr, $value->{text};

            # Remember that we found it
            $dep_found{ $value->{id} }++;
        }

        if (scalar @_ == $last_count) die "some requirements don't exist or there is a dependency loop";
        $last_count = scalar @_;
    }

    return \@sorted_arr;
}

これはそれほど効率的ではなく、おそらくO(n log n)時間内に実行されますが、巨大なデータセットがない場合は、おそらく問題ありません。

于 2012-08-28T19:59:27.003 に答える
2

有向グラフを使用して依存関係ツリーを表し、グラフをウォークします。Graph.pmを使用して非常に似たようなことをしました

各ハッシュはグラフの頂点になり、エッジは依存関係を表します。これには、将来、より複雑な依存関係をサポートするだけでなく、グラフを操作するためのショートカット関数を提供するという追加の利点があります。

于 2012-08-28T19:57:59.890 に答える
1

  1. 依存関係をどうするかは、互いに「独立」しているとは言わなかった。

    たとえば、id1にはid2が必要です。id3にはid4が必要です。id3にはid5が必要です。注文はどうあるべきですか？（2の前の1と4/5の前の3を除く）

  2. 基本的に必要なのは、依存関係のツリー（有向グラフ）のBFS（幅優先探索）です（または、＃1の回答に応じてフォレスト-接続されていないツリーのセットであるフォレスト）。

    それを行うには：

    • すべてのルートノード（それ自体に要件がないID）を検索します

      grepデータ構造で使用するすべてのIDのハッシュを作成することで、これを簡単に行うことができます

    • これらすべてのルートモードを開始配列に配置します。

    • 次に、BFSを実装します。Perlで配列とループを使用して基本的なBFSを実装するためのヘルプが必要な場合は、別の質問をしてください。CPANモジュールがあるかもしれませんが、アルゴリズム/コードはかなり些細なものです（少なくとも一度書いたら:)

于 2012-08-28T19:58:12.137 に答える