Comment trier un hachage Perl contenant des tonnes de données?

Question

Je suis en train de trier un hachage en Perl. Je rencontrais une erreur de dépassement de mémoire lors de l'exécution de mon script Perl:

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

Comment trier une table de hachage qui a des tonnes de données?

Answer 1

sort keys %hash est inefficace pour un grand %hash en ce que la mémoire sage, son à peu près équivalent à:

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

Dans ce, il doit conserver trois copies des clés en mémoire tout en faisant le tri (une dans la hash, un dans la liste des clés, un dans la liste triée en cours de création). foreach Les optimisations de mémoire pour les itérateurs ne s'appliquent pas.

Étant donné que le hachage est si volumineux, la meilleure option consiste à l'extraire entièrement de la mémoire. Collez-le dans un fichier BerkeleyDB. Et si vous voulez garder les clés dans l'ordre d'un hachage n'est pas la meilleure option, un arbre est. Je suggère d'utiliser un fichier Berkeley BTree. Les arbres conserveront efficacement vos données triées comme un tableau tout en fournissant une recherche rapide comme un hachage.

Voici un exemple utilisant BerkeleyDB. DB_File est plus simple et mieux documenté mais ne tire pas parti des fonctionnalités modernes de BerkeleyDB. YMMV.

use BerkeleyDB; 

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

-Compare illustre comment fournir votre propre fonction de tri. L'interface liée sera lente. À moins que vous en ayez besoin pour agir comme un hachage, utilisez l'interface de l'objet.

Answer 2

Perl FAQ a quelques exemples pour trier un hachage. Regardez How do I sort a hash? et voici A Fresh Look at Efficient Perl Sorting.

Answer 3

Si vos clés sont des nombres entiers, des nombres ou des chaînes d'une petite taille maximale, vous pouvez utiliser Trier :: Emballé:

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

Certes, ce code est assez laid, mais il gardera utilisation de la mémoire à la le minimum.