在Perl中，从哈希表中获取键值最大的键的最简单方法是什么？
8个回答
41
使用排序的解决方案:
(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
- Eric Strom
2
3回答详尽。不过需要说明的是：哈希查找的摊销复杂度为 O(1)，而不是 O(log n)。 - jkasnicki
1将哈希查找和数组查找的真实速度进行比较仍然显示非线性关系。当元素数量为10时，数组比哈希快50%，当元素数量为10000时，数组比哈希快100%，当元素数量为1,000,000时，数组比哈希快210%... - Eric Strom
11
不确定为什么每个人都要手动完成这个操作...
use List::Util qw( reduce );
my $max_val_key = reduce { $hash{$a} > $hash{$b} ? $a : $b } keys %hash;
- Dave Sherohman
6
以下代码比其他排序哈希方法更节省空间，并且运行时间为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;
}
}
- jkasnicki
10
4你的代码中有一个假设，即散列值的值不全为小于-1的负数。你应该将$max_value$设置为第一个出现的值或其他值。 - user181548
4很高兴知道仍有人看重效率而非缺乏人手。解释得也很好。 - amphetamachine
2通过减小常数因子，@Alnitak 可以让算法表现更高效。令 f(n) = n * log(n) / log(10) 和 g(n) = n * 1000000。f(n) = O(n log n)，而 g(n) = O(n)。现在令 n = 10。f(10) 等于十，g(10) 等于一千万。此外，只要 n 小于一百万的十次方，f(n) 就会小于 g(n)。这尽管 f(n) 支配着 g(n)。 - hobbs
1需要注意的是，由于log n被认为是一个相当缓慢增长的函数，因此O(n)和O(n log n)因此“并没有太大的区别”，这意味着在较小的n时，一个O(n)函数只需要具有很小的常数因子优势就能击败一个O(n log n)函数。 - hobbs
2@hobbs 我不认为这个解决方案会比涉及排序的解决方案慢。你的论点在一般情况下是有效的（对于小的 n，常数因素可能使 O(n log n) 更可取），但在这种情况下，O(n) 解决方案的常数因子很小：我们仅查看每个元素一次，并对其进行了非常少量的计算。最后，这个解决方案的真正优势在于节省空间。排序将占用 O(n) 的空间，而这个解决方案只需要 O(1) 的空间。请参考 @Eric Strom 的答案以获取另一个讨论和性能数字。 - jkasnicki
显示剩余5条评论
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以适应需求。
- jrockway
4
为什么不直接使用
values 而不是 keys？ - user181548因为他想要键，而不是值。值是用来排序的，键是要返回的。除非我误读了问题。 - jrockway
啊，好的，抱歉，我漏掉了那个。 - user181548
1请使用
$hash{$b} <=> $hash{$a} 替代 reverse。 - knittl3
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;
}
- salva
1
my $highest_val = (keys {$hash{$b} <=> $hash{$a}} keys %hash)[0];
- amphetamachine
4
返回具有最高值的键。我认为他想要映射到最高值的键。否则，这个问题太简单了，不需要询问 :) (如果是这样，为什么不只是“反向排序键%哈希”？) - jrockway
2这取决于你在这里所说的“value”的含义。通常哈希被认为是键/值对，因此我会假设与jrockway相同的事情。但它也可能意味着amphetamachine所说的内容。提问者应该澄清。 - user181548
@jrockway - “那么在这种情况下，为什么不只是使用
reverse sort keys %hash？”- 因为那是一种词法排序，而sort {$b <=> $a}却一举两得，既是数值排序又是反向排序。 - amphetamachine1但是你正在比较键本身，而不是它们映射到的值。 - Vynce
1
my $highest_val = (sort { $hash{$a} <=> $hash{$b} } keys %hash)[0];
这可能是你想要的。
如果你有一个非常大的哈希表，你可能想使用类似于 Schwartzian 变换的东西：
my @array = map {[$hash{$_},$_]} keys %hash;
my $key_with_highest_value = (sort { $a->[0] <=> $b->[0] } @array)[0]->[1]
- David M
2
这样做需要打字更多，但时间复杂度为O(n)，而不是通常的O(n log n)，这是一个好事情。如果你的列表很大的话。 - jrockway
1Schwartzian变换仅用于减少哈希表查找的次数，并且不会改变搜索的复杂度 - 它仍然是O(n log n)。@jkasnicki提出的迭代方法更优。 - Alnitak
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接