¿Cuál es la forma más fácil de obtener una clave con el valor más alto de un hash en Perl?

Question

¿Cuál es la forma más fácil de obtener una clave con el valor más alto de un hash en Perl?

Answer 1

Si bien la solución con una especie:

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

encontrado en algunas de las otras respuestas es bastante elegante, no funciona tan bien como se ve. En primer lugar, el género transforma una operación de búsqueda de búsqueda O(n) en una O(n log n). En segundo lugar, la solución de clasificación tiene n log n hash ups. Las búsquedas de hash son muy buenas para ciertas operaciones, pero cuando se trabaja con todo el hash, las búsquedas serán más lentas que con each, keys o values para iterar a través de la estructura de datos. Esto se debe a que los iteradores no necesitan calcular los hash de las claves, ni necesitan recorrer repetidamente los contenedores para encontrar los valores. Y la sobrecarga no es constante, sino que aumenta a medida que los hash aumentan.

Estas son algunas soluciones rápidas:

use strict; 
use warnings; 

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

que aquí hay una solución utilizando el iterador each (una operación O(1) hecho n veces):

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 versión más rápida que comercia memoria para velocidad (hace una copia del 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' 

Aquí es el rendimiento con diferentes tamaños de 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%    -- 

Como se puede ver, si la memoria no es un gran problema, la versión con arreglos internos es el más rápido, seguido de cerca por el iterador each, y en un distante tercer lugar ... sort

Answer 2

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

Answer 3

Las claves ordenados por valor, de menor a mayor:

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

Las claves ordenados por valor, de mayor a menor:

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

y el primer elemento

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

Reemplace la nave espacial con cmp al gusto.

Answer 4

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

es probable que sea lo que quiere.

Si usted tiene una muy grande de hash, es posible que desee utilizar algo así como un Schwartzian transformar:

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

Answer 5

El siguiente es más eficiente con el espacio y se ejecutarán en O (n) en lugar de O (n log n) en comparación con las otras respuestas que ordenan el hash. Asume que los valores son enteros mayores que 0 y que el hash no está vacío, sino que debe ampliarse fácilmente para su 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 ahora será la clave correspondiente al valor más 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

No

seguro de por qué todo el mundo está haciendo esto a mano ...

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