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 需要编写一个 subtext从哈希中返回 s 的数组， - 按照依赖顺序，所以从上面的例子需要得到：

"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 只需要输出一次。

尚未提供任何代码示例，因为不知道如何开始。;( 存在一些 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 回答