Как отсортировать хеш Perl, содержащий множество данных?

Question

Я сортирую хэш в Perl. Я столкнулся с ошибкой нехватки памяти при запуске моего Perl Script:

foreach $key (sort (keys(%hash))) {
   ....
}

Как мне отсортировать хэш с тоннами данных?

Answer 1

sort keys %hash неэффективно для большого %hash в том, что касается памяти, его примерно эквивалентно:

my @keys = keys %hash;
@keys = sort @keys;

В этом случае во время сортировки необходимо хранить три копии ключей в памяти (одна в хеше, одна в списке ключей, одна в создаваемом отсортированном списке). foreach оптимизации памяти для итераторов не применяются.

Так как хеш очень большой, лучший вариант - полностью вывести его из памяти. Вставьте его в файл BerkeleyDB. И если вы хотите сохранить ключи в порядке, хеш не самый лучший вариант, дерево есть. Я бы предложил использовать файл Berkeley BTree. Деревья будут эффективно сохранять ваши данные отсортированными как массив, обеспечивая быстрый поиск как хеш.

Вот пример использования BerkeleyDB . DB_File проще и лучше документирован, но не использует преимущества современных функций BerkeleyDB. YMMV.

use BerkeleyDB;

my $db  = tie my %hash, 'BerkeleyDB::Btree',
              -Filename => "your.db",
              -Compare  => sub { $_[1] cmp $_[0] },
              -Flags    => DB_CREATE;

-Compare иллюстрирует, как предоставить собственную функцию сортировки. Связанный интерфейс будет вялым. Если вам не нужно, чтобы он действовал как хеш, используйте интерфейс объекта.

Answer 2

Если ваши ключи представляют собой целые числа, числа или строки небольшого максимального размера, вы можете использовать Sort :: Packed:

use Sort::Packed qw(sort_packed);

my $hash_size = keys %hash;
my $max_key_len = 4;  
my $packed_keys = '\0' x ($max_key_len * $hash_size);
my $ix = 0;
while (my ($key, $value) = each %hash) {
  my $key_len = length $k;
  $key_len <= $max_key_len or die "key $key is too big";
  substr($packed_keys, $ix, $key_len, $key);
  $ix += $max_key_len;
}

sort_packed("C$max_key_len", $packed_keys);

$ix = 0;
while ($ix < length $packed_keys) {
  my $key = substr($packed_keys, $ix, $max_key_len);
  $key =~ s/\0+$//;
  print "$key\n";
  $ix += $max_key_len;
}

По общему признанию, этот код довольно уродлив, но он сведет к минимуму использование памяти.

Answer 3

В Perl FAQ есть несколько примеров для сортировки хешей. Посмотрите на Как отсортировать хеш? , а вот Свежий взгляд на эффективную сортировку Perl .