如何數組元素（兩種不同長度）的數組轉換成樹/哈希

Question

我怎麼能轉換編程陣列的列表這樣

$dat_a = [qw(a1 b1 c1 d1 e1)] 
$dat_b = [qw(a1 b1 c2 d2 e1)] 
$dat_c = [qw(a1 b2 c3)] 
[...] 

成層次結構（散）像

# {a1}--{b1}-{c1}-{d1}{e1}=42 
#  \  \{c2}-{d2}{e1}=84 
#  |{b2}-{c3}=72 

填充哈希像這樣與dinamically生成的代碼：

$dat_hierarchy->{a1}{b1}{c1}{d1}{e1} ++ 
$dat_hierarchy->{a1}{b1}{c2}{d2}{e1} ++ 
$dat_hierarchy->{a1}{b2}{c3} ++ 

我在這裏的問題是，在運行裏面的陣列具有不同的長度，並且最大長度在運行之間也是可變的。

一個類似的問題是將文件路徑轉換爲目錄樹 ，所以我認爲將會有一些標準算法來解決這個問題 。

如果我對深度（或數組長度）進行硬編碼，我可以考慮的一個可行的解決方案是將這個問題轉換爲更通用的將矩陣轉換爲層次結構的問題。這意味着將陣列 轉換爲矩陣（添加尾隨0以使所有陣列具有相同的長度）。這樣的解決方案將是微不足道的（如果腳本是 hardocoded針對深度/長度）

#[Perlish pseudocode] 
$max_array_idx  = find_maximum_array_index (\@list_of_arrays) 
@lst_of_matrix_arrays = fill_to_same_length(\@list_of_arrays, $max_array_idx) 
$hierarchy   = create_tree(\@list_of_matrix_arrays, $max_array_idx) 

sub create_tree { 
    my ($list_of_matrix_arrays, $max_array_idx) = @_; 

    # <problem> how to dinamically handle $max_array_idx?? 

    # if I use fixed depth then is trivial 
    # $max_fixed_idx = 2 
    # hardcoded hash construction for depth 3! 

    # Trivial solution for fixed hash depth: 
    foreach my $array ($list_of_matrix_arrays) { 
     $dat_hierarchy->{$array->[0]}{$array->[1]}{$array->[2]} ++  
    } 
} 

所以，我apreciate有關如何避免硬編碼 在散列中使用數組索引的最大數量的任何建議創建，

一個可能的解決方案可能是使用一些元編程來使用運行時$ max_fixed_idx？來填充散列。 它會像下面這樣一個好主意嗎？

sub populate_hash { 
    my ($array) = @_; 
    my $array_max_idx = @$array - 1; 

    # create hash_string " $dat_hierarchy->{$array->[0]}{$array->[1]}{$array->[2]} ++" 
    my $str = '$dat_hierarchy->'; 
    foreach my $idx (0..$array_max_idx) { 
     # using the indexes instead the elements to avoid quotation problems 
     $str .= '{$array->['.$idx.']}'; 
     # how to sanitize the array element to avoid code injection in the further eval? what happen if an array element is called "sub {system('rm -rf ~/')}" ;-) 
     # http://xkcd.com/327/ 
    } 
    $str .= ' ++'; 

    # populate hash 
    # $str for lengh 3 arrays would be '$dat_hierarchy->{$array->[0]}{$array->[1]}{$array->[2]} ++' 
    eval($str) or die 'error creating the hash'; 
} 

什麼是遞歸？

Answer 1

如果我正確理解你的問題，我會做類似於下面的事情。

在下面的解決方案的相關位是$sub_hash = ($sub_hash->{$hash_key} ||= {});

#!/usr/bin/perl 
use strict; 
use warnings; 

package HashBuilder; 

    sub new { 
    my $pkg = shift; 
    return bless {}, $pkg; 
    } 

    sub add { 
    my ($pkg,$data) = @_; 
    my $sub_hash = $pkg; 

    for my $idx (0..$#{$data}) { 
     my $hash_key = $data->[$idx]; 
     $sub_hash = ($sub_hash->{$hash_key} ||= {}); 
    } 
    } 

    sub get_hash { 
    my $pkg = shift; 
    return %$pkg; 
    } 

package main; 

use Data::Dumper; 

my $dat_a = [qw(a1 b1 c1 d1 e1)]; 
my $dat_b = [qw(a1 b1 c2 d2 e1)]; 
my $dat_c = [qw(a1 b2 c3)]; 

my $builder = HashBuilder->new(); 
$builder->add($dat_a); 
$builder->add($dat_c); 
$builder->add($dat_b); 

my %hash = $builder->get_hash(); 
$hash{a1}{b2}{c3} = 16; 

print Dumper(\%hash); 

我們得到以下結果：在perlmonks很久以前討論

$VAR1 = { 
      'a1' => { 
        'b1' => { 
           'c2' => { 
             'd2' => { 
                'e1' => {} 
               } 
             }, 
           'c1' => { 
             'd1' => { 
                'e1' => {} 
               } 
             } 
          }, 
        'b2' => { 
           'c3' => 16 
          } 
        } 
     }; 

Answer 2

我會使用類似Tree::DAG_Node。

use Tree::DAG_Node; 
my $root = Tree::DAG_Node->new(); 

my $data = [qw(a1 b1 c1 d1 e1)]; 

my $node = $root; 
for my $item (@$data) { 
    my $daughter = Tree::DAG_Node->new(); 
    $daughter->name($item); 
    $node->add_daughter($daughter); 
    $node = $daughter; 
} 

Answer 3

我已經看到了類似的問題。我記得最短的解決辦法是這樣的：

use strict; use warnings; 

my @items = (
    [qw(a1 b1 c1 d1 e1)], 
    [qw(a1 b1 c2 d2 e1)], 
    [qw(a1 b2 c3)], 
); 

my $dat_hierarchy; 
for my $item (@items) { 
    eval "\$dat_hierarchy->{'" . join("'}{'", @$item) . "'}++"; 
} 

use Data::Dump; 
dd $dat_hierarchy; 

編輯：注意，該解決方案與字符串的eval嚴重的安全問題，請參見下面Schwern擁有的評論。我考慮刪除，但決定把它留在這裏作爲警告給其他人。