3

我有一个类似于以下的哈希结构：

KeyA => {
         Key1 => {
                   Key4 => 4
                   Key5 => 9
                   Key6 => 10
                 }
         Key2 => {
                   Key7 => 5
                   Key8 => 9
                 }
        }
KeyB => {
         Key3 => {
                   Key9 => 6
                   Key10 => 3
                 }
        }

我需要打印出通过哈希结构的遍历路径和遍历结束时的值，以便按值排序。例如，对于上面的哈希结构，我需要打印：

KeyB Key3 Key10 3
KeyA Key1 Key4  4
KeyA Key2 Key7  5
KeyB Key3 Key9  6
KeyA Key2 Key8  9
KeyA Key1 Key5  9
KeyA Key1 Key6  10

目前，为了解决这个问题，我正在使用嵌套的 foreach 循环遍历哈希结构，并通过插入一个键等于遍历路径（例如“KeyA Key3 Key10”）且值等于末尾值的元素来创建扁平哈希遍历路径（例如 3），然后执行另一个 foreach 循环，按值对展平的哈希进行排序。

有没有更有效的方法来做到这一点？

4

5 回答 5

3

考虑创建一个排序数组，而不是创建一个新的哈希。遍历初始值，根据值，键值对插入到数组中，然后遍历结果数组。这应该在初始迭代中为您提供 O(n) + 每个插入的 O(lg n) + 最后迭代的 O(n)。

于 2009-04-17T22:28:35.773 回答
3

您还可以使用递归解决方案为任意嵌套深度的嵌套数据结构解决此问题。您递归地构建一个包含路径和值的目标数组，然后对该数组进行排序。

use warnings;
use strict;

sub paths {
    my ($data, $cur_path, $dest) = @_; 
    if (ref $data eq 'HASH') {
        foreach my $key (keys %$data) {
            paths($data->{$key}, [@$cur_path, $key], $dest);
        }   
    } else {
        push @$dest, [$cur_path, $data];
    }   
}

my $data = {
    KeyA => {
        Key1 => { Key4 => 4, Key5 => 9, Key6 => 10 },
        Key2 => { Key7 => 5, Key8 => 9 }
    },
    KeyB => { Key3 => { Key9 => 6, Key10 => 3 } }
};

my $dest = []; 
paths($data, [], $dest);

foreach my $result (sort { $a->[1] <=> $b->[1] } @$dest) {
    print join(' ', @{$result->[0]}, $result->[1]), "\n";
}
于 2009-04-18T07:16:38.577 回答
1

对于您给出的数据结构，嵌套循环并没有真正的替代方案。（可能有更好的数据结构，但我们无法知道。）我会这样编码：

use strict;
use warnings;

my %hash = (
    KeyA => {
        Key1 => {
            Key4 => 4,
            Key5 => 9,
            Key6 => 10,
        },
        Key2 => {
            Key7 => 5,
            Key8 => 9,
        },
    },
    KeyB => {
        Key3 => {
            Key9 => 6,
            Key10 => 3,
        },
    },
);

my @array;
while (my ($k1, $v1) = each %hash) {
    while (my ($k2, $v2) = each %$v1) {
        while (my ($k3, $v3) = each %$v2) {
            push @array, [$k1, $k2, $k3, $v3];
        }
    }
}

foreach my $x (sort { $a->[-1] <=> $b->[-1] } @array) {
    print join(' ', @$x), "\n";
}
于 2009-04-18T02:02:42.263 回答
0

使用多维散列仿真将其转换为平面散列（参见 perlvar 中的 $;），然后对生成的散列进行排序。

use strict;
use warnings;
my %hash = (
    KeyA => {
          Key1 => {
                    Key4 => 4,
                    Key5 => 9,
                    Key6 => 10,
                  },
          Key2 => {
                    Key7 => 5,
                    Key8 => 9,
                  }
         },
    KeyB => {
          Key3 => {
                    Key9 => 6,
                    Key10 => 3,
                  },
         },
);

my %fhash = 
   map {
        my @fh;
        foreach my $k2 (keys %{$hash{$_}}) {
                foreach my $k3 (keys %{$hash{$_}{$k2}}) {
                        push @fh, (join($;, $_, $k2, $k3) => $hash{$_}{$k2}{$k3});
                }   
        }
        @fh;
   } keys %hash;



foreach (sort { $fhash{$a} <=> $fhash{$b} } keys %fhash) {
    printf("%s\t%d\n", join("\t", split(/$;/, $_)), $fhash{$_});
}

您可以将生成 fhash 的 map / foreach 循环直接传递给排序。

于 2010-08-17T06:16:38.883 回答
-2

这些其他解决方案似乎更优雅，因为它们“聪明”。但是，鉴于您的数据结构的简单性，您的方法实际上很好。这种结构很容易变平。您要求提供更有效的解决方案，但没有提供。

于 2010-08-17T02:42:07.303 回答