按值哈希的哈希排序 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循环，该循环按值对扁平化的哈希进行排序。

有没有更有效的方法？

- Melissa

---

如果叶子节点的值不一定是唯一的，则应该执行 push @{ $flat{$path} } => $value。 - Greg Bacon

Answer 1

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

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

- nohat

Answer 2

不要创建新的哈希表，考虑创建一个排序数组。遍历初始值，根据值将键值对插入到数组中，然后遍历结果数组。这样可以在初始迭代上获得O(n) + 每次插入的O(lg n) + 最终迭代的O(n)，从而提高效率。

- Justin R.

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

- Michael Carman

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 循环传递给 sort。

- MkV

Answer 5

这些其他解决方案似乎更优雅，因为它们很“聪明”。然而，考虑到您的数据结构的简单性，您的方法实际上已经足够好了。该结构很容易被展开。您要求提供更高效的解决方案，但没有提供。

- jwebster