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

Answer 4

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

Answer 5

Преобразуйте его в плоский хеш, используя многомерную хэш-эмуляцию (см. $; В 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 непосредственно в сортировку.