Was ist der einfachste Weg, um einen Schlüssel mit dem höchsten Wert von einem Hash in Perl zu bekommen?

Question

Was ist der einfachste Weg, um einen Schlüssel mit dem höchsten Wert von einem Hash in Perl zu bekommen?

Answer 1

Während die Lösung mit sort:

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

in einigen der anderen Antworten gefunden sehr elegant ist, ist es nicht wie schön, wie es aussieht. Zunächst wandelt die Sortierung eine O(n) Suche Suchoperation in eine O(n log n) eins. Zweitens hat die Sortierlösung n log n Hash-Lookups. Hash-Look-Ups sind sehr gut für bestimmte Operationen, aber wenn mit dem gesamten Hash gearbeitet wird, sind Look-Ups langsamer als die Verwendung von each, keys oder values, um die Datenstruktur zu durchlaufen. Dies liegt daran, dass die Iteratoren weder die Hashwerte von Schlüsseln berechnen müssen, noch wiederholt durch Bins gehen müssen, um die Werte zu finden. Und der Aufwand ist nicht konstant, sondern steigt mit zunehmender Größe der Hashes.

Hier sind ein paar schnelleren Lösungen:

use strict; 
use warnings; 

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

Hier ist eine Lösung, die den each Iterator (ein O(1) Betrieb n mal gemacht):

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' 

Oder eine schnellere Version, die Speicher tauscht Geschwindigkeit (es macht eine Kopie des Hash):

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' 

Hier ist die Leistung mit verschiedenen Hash-Größen:

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%    -- 

Wie Sie sehen können, wenn der Speicher nicht viel ein Problem ist, ist die Version mit internen Arrays ist am schnellsten, dicht gefolgt von der each Iterator gefolgt, und in ein dritter Stelle ... sort

Answer 2

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

Answer 3

Die Schlüssel nach Wert geordnet, von den niedrigsten zum höchsten:

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

Die Schlüssel nach Wert geordnet, vom höchsten zum niedrigsten:

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

und das erste Element

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

Ersetzen Sie das Raumschiff durch cmp nach Geschmack.

Answer 4

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

ist wahrscheinlich, was Sie wollen.

Wenn Sie einen sehr großen Hash haben, möchten Sie vielleicht so etwas wie ein Schwartzian verwenden verwandeln:

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

Answer 5

Hier finden Sie mehr Platz sparende und in O (n) anstelle von O laufen (n log n) im Vergleich zu den anderen Antworten, die den Hash sortieren. Es nimmt an, dass Werte ganze Zahlen größer als 0 sind und der Hashwert nicht leer ist, aber für Ihren Fall leicht erweitert werden sollte.

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 ist jetzt der Schlüssel, der dem höchsten Wert entspricht.

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

Nicht sicher, warum alle diese von Hand tut ...

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