Quel est le moyen le plus simple d'obtenir une clé avec la valeur la plus élevée d'un hachage en Perl?

Question

Quel est le moyen le plus simple d'obtenir une clé avec la valeur la plus élevée d'un hachage en Perl?

Answer 1

Alors que la solution avec tri:

(sort {$hash{$a} <=> $hash{$b}} keys %hash)[0] 

trouvé dans certaines des autres réponses est tout à fait élégant, il ne fonctionne pas aussi bien qu'il regarde. Tout d'abord, le tri transforme une opération de recherche par recherche O(n) en une opération O(n log n). Deuxièmement, la solution de tri a n log n recherches de hachage. Les recherches de hachage sont très bonnes pour certaines opérations, mais lorsque vous travaillez avec l'ensemble du hachage, les recherches seront plus lentes que celles effectuées avec each, keys ou values pour parcourir la structure de données. Cela est dû au fait que les itérateurs n'ont pas besoin de calculer les hachages des clés, ni de parcourir plusieurs fois les cases pour trouver les valeurs. Et les frais généraux ne sont pas constants, mais augmentent au fur et à mesure que les hachages grossissent.

Voici quelques solutions plus rapides:

use strict; 
use warnings; 

my %hash = (
    small => 1, 
    medium => 5, 
    largest => 10, 
    large => 8, 
    tiny => 0.1, 
); 

Voici une solution en utilisant la each iterator (un fait n fois l'opération O(1)):

sub largest_value (\%) { 
    my $hash = shift; 
    keys %$hash;  # reset the each iterator 

    my ($large_key, $large_val) = each %$hash; 

    while (my ($key, $val) = each %$hash) { 
     if ($val > $large_val) { 
      $large_val = $val; 
      $large_key = $key; 
     } 
    } 
    $large_key 
} 

print largest_value %hash; # prints 'largest' 

Ou une version plus rapide que les métiers mémoire pour vitesse (il fait une copie du hachage):

sub largest_value_mem (\%) { 
    my $hash = shift; 
    my ($key, @keys) = keys %$hash; 
    my ($big, @vals) = values %$hash; 

    for (0 .. $#keys) { 
     if ($vals[$_] > $big) { 
      $big = $vals[$_]; 
      $key = $keys[$_]; 
     } 
    } 
    $key 
} 

print largest_value_mem %hash; # prints 'largest' 

Voici les performances avec différentes tailles de hachage:

10 keys:    Rate largest_with_sort largest_value largest_value_mem 
largest_with_sort 111565/s    --   -8%    -13% 
largest_value  121743/s    9%   --    -5% 
largest_value_mem 127783/s    15%   5%    -- 

50 keys:    Rate largest_with_sort largest_value largest_value_mem 
largest_with_sort 24912/s     --   -37%    -40% 
largest_value  39361/s    58%   --    -6% 
largest_value_mem 41810/s    68%   6%    -- 

100 keys:   Rate largest_with_sort largest_value largest_value_mem 
largest_with_sort 9894/s     --   -50%    -56% 
largest_value  19680/s    99%   --    -12% 
largest_value_mem 22371/s    126%   14%    -- 

1,000 keys:   Rate largest_with_sort largest_value largest_value_mem 
largest_with_sort 668/s     --   -69%    -71% 
largest_value  2183/s    227%   --    -7% 
largest_value_mem 2341/s    250%   7%    -- 

10,000 keys:  Rate largest_with_sort largest_value largest_value_mem 
largest_with_sort 46.5/s     --   -79%    -81% 
largest_value  216/s    365%   --    -11% 
largest_value_mem 242/s    421%   12%    -- 

Comme vous pouvez le voir, si la mémoire est vraiment un problème, la version avec des tableaux internes est le plus rapide, suivi de près par le each iterator, et un troisième lointain ... sort

Answer 2

my $highest_val = (keys {$hash{$b} <=> $hash{$a}} keys %hash)[0]; 

Answer 3

Les touches triées par valeur, du plus bas au plus haut:

sort { $hash{$a} <=> $hash{$b} } keys %hash 

Les clés triées par valeur, du plus haut au plus bas:

reverse sort { $hash{$a} <=> $hash{$b} } keys %hash 

Et le premier élément

(reverse sort { $hash{$a} <=> $hash{$b} } keys %hash)[0] 

Remplacer le vaisseau par cmp au goût.

Answer 4

my $highest_val = (sort { $hash{$a} <=> $hash{$b} } keys %hash)[0]; 

est susceptible d'être ce que vous voulez.

Si vous avez un hachage très grand, vous pouvez utiliser quelque chose comme une Schwartzienne transform:

my @array = map {[$hash{$_},$_]} keys %hash; 
my $key_with_highest_value = (sort { $a->[0] <=> $b->[0] } @array)[0]->[1] 

Answer 5

Voici plus d'espace efficace et se déroulera en O (n) au lieu de O (n log n) par rapport aux autres réponses qui trient le hachage. Il suppose que les valeurs sont des entiers supérieurs à 0 et que le hachage n'est pas vide, mais devrait être facilement étendu pour votre cas.

my $key_for_max_value; 
my $max_value = -1; 
while ((my $key, my $value) = each %hash) { 
    if ($value > $max_value) { 
    $max_value = $value; 
    $max_key = $key; 
    } 
} 

key_for_max_value $ sera maintenant la touche correspondant à la valeur la plus élevée.

Answer 6

my ($max_key, $max_val) = each %hash or die "hash is empty"; 
while (my ($key, $val) = each %hash) { 
    $max_key = $key, $max_val = $val if $val > $max_val; 
} 

Answer 7

Je ne sais pas pourquoi tout le monde est en train de faire cela à la main ...

use List::Util qw(reduce); 
my $max_val_key = reduce { $hash{$a} > $hash{$b} ? $a : $b } keys %hash;