Qual è il modo più semplice per ottenere una chiave con il valore più alto da un hash in Perl?

Question

Qual è il modo più semplice per ottenere una chiave con il valore più alto da un hash in Perl?

Answer 1

Mentre la soluzione con un ordine:

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

si trovano in alcune delle altre risposte è molto elegante, ma non esegue come bene come sembra. Prima di tutto, l'ordinamento trasforma un'operazione di ricerca di ricerca O(n) in uno O(n log n). In secondo luogo, la soluzione di ordinamento ha le ricerche di hash n log n. Le ricerche hash sono molto adatte per determinate operazioni, ma quando si lavora con l'intero hash, le ricerche saranno più lente dell'uso di each, keys o values per scorrere la struttura dei dati. Questo perché gli iteratori non hanno bisogno di calcolare gli hash delle chiavi, né hanno bisogno di passare ripetutamente attraverso i contenitori per trovare i valori. E l'overhead non è costante, ma aumenta man mano che gli hash diventano più grandi.

Ecco alcune soluzioni più rapide:

use strict; 
use warnings; 

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

Ecco una soluzione che utilizza il each iteratore (un'operazione O(1) fatto n volte):

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' 

o una versione più veloce che commercia memoria per velocità (fa una copia dell'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' 

Ecco le prestazioni con i vari formati hash:

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

Come si può vedere, se la memoria non è molto più di un problema, la versione con le matrici interne è più veloce, seguito da vicino dal each iteratore, e in un terzo lontana ... sort

Answer 2

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

Answer 3

Le chiavi ordinati per valore, dal più basso al più alto:

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

Le chiavi ordinati per valore, dal più alto al più basso:

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

E il primo elemento

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

Sostituire l'astronave con cmp a piacere.

Answer 4

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

è probabilmente quello che vuoi.

Se si dispone di un grande hash, si potrebbe desiderare di usare qualcosa come un Trasformata di Schwartz:

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

Answer 5

Quello che segue è più spazio-efficiente e verrà eseguito in O (n) invece di O (n log n) rispetto alle altre risposte che ordinano l'hash. Si assume che i valori siano numeri interi maggiori di 0 e che l'hash non sia vuoto, ma che dovrebbe essere facilmente esteso per il tuo caso.

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 sarà la chiave corrispondente al valore più alto.

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

Non so perché ognuno sta facendo tutto a mano ...

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