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

InformationsquelleAutor syker | 2010-05-22

8 Comentarios

  1. 34

    Mientras que la solución con orden:

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

    se encuentran en algunas de las otras respuestas es muy elegante, no funciona tan bien como parece. En primer lugar, el tipo transforma una O(n) búsqueda de operación búsqueda en un O(n log n) uno. En segundo lugar, el tipo de solución ha n log n hash mirada-ups. Hash mirada-ups son muy buenos para ciertas operaciones, pero cuando se trabaja con todo el hash, mira-ups será más lento que el uso de each, keys, o values para iterar a través de la estructura de datos. Esto es debido a que los iteradores no es necesario para calcular los valores hash de las claves, ni necesitan repetidamente a pie a través de los contenedores para encontrar los valores. Y la sobrecarga no es constante, sino que aumenta a medida que el hash de tamaño.

    Aquí están algunas más rápidas soluciones:

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

    Aquí es una solución que utiliza el each iterator (un O(1) operación realizada 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 la de los oficios de la memoria para la velocidad (se hace una copia de los 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 varios hash tamaños:

    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 mucho de un problema, la versión interna de matrices es el más rápido, seguido de cerca por el each iterador, y en un lejano tercer lugar… sort

    • +1 gran y completa respuesta!
    • Respuesta detallada. Uno de los comentarios, sin embargo: la amortizado complejidad de un hash de búsqueda es O(1) O(log n).
    • comparando mundo real velocidades de hash de búsqueda de la matriz de búsqueda todavía muestra una relación no lineal. con 10 elementos, una matriz es %50 más rápido que un hash, con 10000 elementos es un 100% más rápido, con 1.000.000 de elementos es de 210% más rápido…
  2. 9

    No sé por qué todo el mundo está haciendo esto por la mano…

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

    El siguiente es más eficiente con el espacio y se ejecutará en O(n) en lugar de O(n log n) en comparación con las otras respuestas que tipo de hash. Se asume que los valores son enteros mayores que 0 y 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 va a ser la clave correspondiente al valor más alto.

    • Hay un supuesto en el código que los valores del hash no son todos los números negativos menores que -1. Usted sólo debe hacer $max_value el valor de la primera cosa que ve o algo.
    • Bueno saber que alguien allí todavía se aprecia la eficiencia a corto imparcialidad. Buena explicación, demasiado.
    • Y que se puede hacer con algo como my $max_value = undef; y más tarde, cambiar el if a if (! defined $max_value || $value > $max_value).
    • para un tamaño razonable conjuntos de datos, esta solución es muy probable que sea más lento que el de utilizar sort.
    • ¿cómo es exactamente lo que usted hace O(n log n) ir más rápido que O(n) ?
    • por tener un menor factor constante. Sea f(n) = n * log(n) / log(10) y g(n) = n * 1000000. f(n) = O(n log n) y g(n) = O(n). Ahora vamos n = 10. f(10) es de diez, y g(10) diez millones de dólares. Por otra parte, f(n) será menor que g(n) cuando n es menor que diez a la millonésima potencia. Esto a pesar del hecho de que f(n) domina g(n).
    • (Debe tenerse en cuenta que, dado que log n se considera bastante lento crecimiento de la función, O(n) y O(n log n) son por lo tanto «no es muy diferente», lo que significa que no tome un gran factor constante ventaja para un O(n) en función de batir a cabo una operación O(n log n) de uno en pequeña n.)
    • No creo que esta solución siempre será más lento que uno que implican la ordenación. Su argumento es válido en general (constante de factores que pueden hacer O(n log n) preferible para los pequeños de n), pero en este caso el factor constante en la O(n) la solución es pequeño: nos fijamos en cada elemento exactamente una vez y hacer una cantidad muy pequeña de cálculo con ella. Finalmente, el verdadero triunfo de esta solución es el ahorro de espacio. La clasificación se toma O(n) en el espacio, mientras que esta solución toma O(1) espacio. Ver a @Eric Strom respuesta para otra discusión y números de rendimiento.
    • bien puesto. Por supuesto, no que ser casos particulares donde O(n log n) es menor que O(n) (para valores pequeños de n), pero este no es uno de ellos!
    • Poner un corto-circuito operador para definir $max_value en el primer paso: $max_value ||= $value;. De esa manera usted puede deshacerse de la -1 asunción

  4. 4

    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]

    Reemplazar la nave espacial con cmp a gusto.

    • Por qué no usar simplemente values en lugar de keys?
    • Porque él quiere que la clave, no el valor. El valor es lo que a la ordenación, la clave es qué volver. A menos que yo sea una lectura errónea de la pregunta.
    • Ah, OK, lo siento, me perdí.
    • -1 para el uso de la inversa, cuando sólo quieren un elemento
    • uso $hash{$b} <=> $hash{$a} en lugar de reverse
  5. 3
    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;
    }
  6. 1
    my $highest_val = (sort { $hash{$a} <=> $hash{$b} } keys %hash)[0];

    es probable que lo que usted desea.

    Si usted tiene un hash muy grande, usted podría querer usar algo como un Schwartzian transformar:

    my @array = map {[$hash{$_},$_]} keys %hash;
    my $key_with_highest_value = (sort { $a->[0] <=> $b->[0] } @array)[0]->[1]
    • Esto es más escribir, pero es O(n) en lugar de O(n log n), que es generalmente una buena cosa. Si la lista es grande.
    • El Schwartzian transformar aquí sólo sirve para reducir el número de búsquedas en una tabla hash, y no no cambiar la complejidad de la búsqueda: sigue siendo O(n log n). El enfoque iterativo de @jkasnicki es superior.
  7. 1
    my $highest_val = (keys {$hash{$b} <=> $hash{$a}} keys %hash)[0];
    • Que devuelve la llave que el valor más alto. Supongo que quiere que la clave que se asigna al valor más alto. De lo contrario, la pregunta es demasiado simple para ser preguntando 🙂 (Y en ese caso, ¿por qué no simplemente «inversa llaves %hash»?)
    • Depende de lo que quieres decir con «valor» aquí. Generalmente un hash es el pensamiento de como pares clave/valor, así que me gustaría asumir la misma cosa como jrockway. Pero también podría significar lo que amphetamachine dijo. El interrogador debe aclarar.
    • en ese caso, ¿por qué no simplemente «inversa llaves %hash»? – Porque es un tipo de léxico, y sort {$b <=> $a} golpea a dos pájaros con una piedra en la que es tanto una ordenación numérica Y se trata de invertir.
    • pero usted está comparando con las teclas de sí mismos, no en los valores se asignan a la.

Dejar respuesta

Please enter your comment!
Please enter your name here