Сортировать по значению хеш хешей Perl

У меня есть хэш-структура, подобная следующей:

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, который сортирует сглаженный хэш по значению.

Есть ли более эффективный способ сделать это?


sorting hash perl perl-data-structures
person Community    schedule 17.04.2009    source источник
comment
Если конечные значения не обязательно уникальны, вам следует push @{ $flat{$path} } => $value.   -  person Greg Bacon    schedule 17.08.2010

Ответы (5)


arrow_upward
3
arrow_downward

Вместо создания нового хеша рассмотрите возможность создания отсортированного массива. Обход начальных значений, вставка в массив в соответствии со значением, пара ключ-значение, а затем итерация по результирующему массиву. Это должно дать вам O (n) на начальной итерации + O (lg n) для каждой вставки + O (n) для последней итерации.

person Justin R.    schedule 17.04.2009

arrow_upward
3
arrow_downward

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

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";
}
person nohat    schedule 18.04.2009

arrow_upward
1
arrow_downward

Для указанной вами структуры данных альтернативы вложенному циклу нет. (Может быть, структура данных получше, но мы не можем узнать об этом.) Я бы закодировал ее так:

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";
}
person Michael Carman    schedule 18.04.2009

arrow_upward
0
arrow_downward

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

person MkV    schedule 17.08.2010

arrow_upward
-2
arrow_downward

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

person jwebster    schedule 17.08.2010