Что самый легкий путь состоит в том, чтобы получить ключ с самым высоким значением от хеша в Perl?
Что самый легкий путь состоит в том, чтобы получить ключ с самым высоким значением от хеша в Perl?
7 ответов
Хотя решение с sort:
(sort {$hash{$a} <=> $hash{$b}} keys %hash)[0]
, найденное в некоторых других ответах, довольно элегантно, оно работает не так хорошо, как кажется. Во-первых, сортировка преобразует операцию поиска O (n) в операцию поиска O (n log n) . Во-вторых, решение сортировки имеет n log n просмотров хэшей. Поиск по хешу очень хорош для определенных операций, но при работе со всем хешем поиск будет медленнее, чем при использовании каждого , ключей или значений ] для перебора структуры данных. Это связано с тем, что итераторам не нужно вычислять хэши ключей, и им не нужно многократно проходить через ячейки, чтобы найти значения. И накладные расходы не постоянны, а увеличиваются по мере увеличения хэшей.
Вот несколько более быстрых решений:
use strict;
use warnings;
my %hash = (
small => 1,
medium => 5,
largest => 10,
large => 8,
tiny => 0.1,
);
Вот решение, использующее итератор каждый (операция 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% --
Как видите, если памяти не так много проблема, версия с внутренними массивами является самой быстрой, за ней следует итератор каждый , а в отдаленной трети ... sort
Ключи, отсортированные по значению, от самого низкого до самого высокого:
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 по вкусу.
Следующий вариант более экономичен и будет выполняться за 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 теперь будет ключом, соответствующим наивысшему значению.
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]
Не уверен, почему все делают это вручную ...
use List::Util qw( reduce );
my $max_val_key = reduce { $hash{$a} > $hash{$b} ? $a : $b } keys %hash;
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;
}
my $highest_val = (keys {$hash{$b} <=> $hash{$a}} keys %hash)[0];