Cách dễ nhất để lấy chìa khóa có giá trị cao nhất từ ​​băm trong Perl là gì?

Question

Cách dễ nhất để lấy khóa có giá trị cao nhất từ ​​băm trong Perl là gì?

Answer 1

Trong khi các giải pháp với sắp xếp:

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

tìm thấy trong một số các câu trả lời khác là khá thanh lịch, nó không hoạt động như độc đáo vì nó trông. Trước hết, sắp xếp biến đổi hoạt động tìm kiếm tìm kiếm O(n) thành một số O(n log n). Thứ hai, giải pháp sắp xếp có số lần xem băm n log n. Hash look-up rất tốt cho các hoạt động nhất định, nhưng khi làm việc với toàn bộ băm, tra cứu sẽ chậm hơn sử dụng each, keys hoặc values để lặp qua cấu trúc dữ liệu. Điều này là do các trình vòng lặp không cần tính toán các băm khóa, cũng như chúng không cần phải lặp đi lặp lại thông qua các thùng để tìm các giá trị. Và chi phí không phải là không đổi, nhưng tăng khi băm trở nên lớn hơn.

Dưới đây là một số giải pháp nhanh hơn:

use strict; 
use warnings; 

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

Đây là một giải pháp sử dụng các each iterator (một hoạt động O(1) làm n lầ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' 

Hoặc một phiên bản nhanh hơn trao đổi mua bán bộ nhớ cho tốc độ (nó tạo một bản sao của băm):

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' 

Đây là hiệu suất với các kích cỡ khác nhau băm:

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

Như bạn có thể thấy, nếu bộ nhớ là không nhiều của một vấn đề, phiên bản với mảng nội bộ là nhanh nhất, theo dõi chặt chẽ bởi các each iterator, và trong một phần ba xa ... sort

Answer 2

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

Answer 3

Các phím được sắp xếp theo giá trị, từ thấp nhất đến cao nhất:

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

Các phím được sắp xếp theo giá trị, từ cao nhất đến thấp nhất:

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

Và phần tử đầu tiên

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

Thay thế tàu vũ trụ bằng cmp để nếm thử.

Answer 4

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

có thể là những gì bạn muốn.

Nếu bạn có một hash rất lớn, bạn có thể muốn sử dụng một cái gì đó giống như một Schwartzian transform:

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

Answer 5

Sau đây là nhiều không gian hiệu quả và sẽ chạy trong thời gian O (n) thay vì O (n log n) so với các câu trả lời khác sắp xếp băm. Nó giả định giá trị là số nguyên lớn hơn 0 và hàm băm không trống, nhưng nên dễ dàng mở rộng cho trường hợp của bạn.

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 giờ sẽ là khóa tương ứng với giá trị cao nhất.

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

Không chắc lý do tại sao tất cả mọi người đang làm điều này bằng tay ...

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