Sort by value hash of hash of hashes Perl

Question

I have a hash structure similar to the following:

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

I need to print out the traversal path through the hash structure and the value at the end of the traversal, such that this is ordered by value. For example, for the above hash structure I need to print:

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

Currently, to solve this I am traversing the hash structure using nested foreach loops, and creating a flattened hash by inserting an element with key equal to the traversal path (e.g. "KeyA Key3 Key10") and value equal to the value at the end of the traversal path (e.g. 3), then doing another foreach loop which sorts the flattened hash by value.

Is there a more efficient way to do this?

Solution 1

You can also solve this problem for a nested data structure of arbitrary nesting depth using a recursive solution. You recursively build up a destination array containing paths and values, and then sort that array.

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

Solution 2

Instead of creating a new hash, consider creating a sorted array. Iterate over the initial values, inserting in to the array, according to the value, the key-value pair, then iterate over the resulting array. This should give you O(n) on the initial iteration + O(lg n) for each insertion + O(n) for the final iteration.

Solution 3

For the data structure you've given there's not really an alternative to nested looping. (There might be a better data structure, but there's no way for us to know.) I'd code it this way:

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