按值排序 哈希值 哈希值 哈希值 Perl

Question

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

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循环，按值对扁平散列进行排序。

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

Answer 1

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

Answer 2

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

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";
}

Answer 3

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

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";
}

Answer 4

使用多维哈希模拟将其转换为平面哈希（请参阅 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 循环直接传递给排序。

Answer 5

这些其他解决方案看起来更优雅，因为它们“聪明”。 但是，考虑到数据结构的简单性，您的方法实际上就很好了。 这种结构很容易被扁平化。 您要求更有效的解决方案，但没有提供。