Сортировать по значению хэш хешей 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

Вы также можете решить эту проблему для вложенной структуры данных произвольной глубины вложения, используя рекурсивное решение. Вы рекурсивно создаете целевой массив, содержащий пути и значения, а затем сортируете этот массив.

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 2

Вместо создания нового хэша рассмотрите возможность создания отсортированного массива. Выполните итерацию по начальным значениям, вставив в массив в соответствии со значением пару ключ-значение, затем выполните итерацию по результирующему массиву. Это должно дать вам O (n) на начальной итерации + O (lg n) для каждой вставки + O (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{$_});
}

Вы можете передать цикл map / foreach, который генерирует fhash, непосредственно в сортировку.

Answer 5

Эти другие решения кажутся более элегантными, потому что они "умные". Однако, учитывая простоту вашей структуры данных, ваш метод на самом деле просто отлично. Эта структура легко сплющена. Вы запросили более эффективное решение, но не было предоставлено.