Каков самый простой способ получить ключ с самым высоким значением из хеша в Perl?

Ответ 1

Пока решение с сортировкой:

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

найденный в некоторых других ответах, довольно изящный, он не работает так хорошо, как кажется. Во-первых, сортировка преобразует операцию поиска O(n) поиска в O(n log n). Во-вторых, решение сортировки имеет n log n хэш-образы. Взгляды на хеширование очень хороши для определенных операций, но при работе со всем хэшем поисковые запросы будут медленнее, чем использование each, keys или values для итерации по структуре данных. Это связано с тем, что итераторам не нужно вычислять хэши ключей, и им не нужно многократно ходить через бункеры, чтобы найти значения. И накладные расходы не постоянны, а возрастают по мере увеличения хешей.

Вот несколько более быстрых решений:

use strict;
use warnings;

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

Вот решение, использующее итератор each (операция O(1), выполненная n раз):

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'

Или более быстрая версия, которая торгует память для скорости (она делает копию хэша):

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'

Вот производительность с различными размерами хэша:

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

Как вы можете видеть, если память не очень важна, версия с внутренними массивами выполняется быстрее всего, за ней следует итератор each, а в третьей части... sort

Ответ 2

Не знаю, почему все это делают вручную...

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

Ответ 3

Ниже приведено более эффективное пространство и будет выполняться в O (n) вместо O (n log n) по сравнению с другими ответами, сортирующими хэш. Он предполагает, что значения являются целыми числами больше 0, а хеш не пуст, но должен быть легко расширен для вашего случая.

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 теперь будет ключом, соответствующим наивысшему значению.

Ответ 4

Ключи отсортированы по значению, от самого низкого до самого высокого:

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

Ключи отсортированы по значению, от самого высокого до самого низкого:

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

И первый элемент

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

Замените космический корабль на cmp по вкусу.

Ответ 5

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

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

Ответ 7

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

скорее всего будет тем, что вы хотите.

Если у вас очень большой хэш, вы можете использовать что-то вроде преобразования Шварца:

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