Làm cách nào để sắp xếp một mảng tham chiếu băm bằng một trong các giá trị băm?

Question

Trước tiên, xin hãy tha thứ cho Perl gỉ của tôi. Tôi đang cố gắng sửa đổi "whine.pl" của Bugzilla để tạo danh sách các lỗi được sắp xếp theo mức độ nghiêm trọng.

Vì vậy, nó cung cấp cho tôi một mảng tham chiếu băm. Mỗi băm chứa một loạt thông tin về một lỗi cụ thể (id, người được gán, mức độ nghiêm trọng, v.v.). Tôi muốn sắp xếp mảng theo mức độ nghiêm trọng. Cách tốt nhất để làm điều này là gì?

Tôi sẽ đưa ra một vài khả năng. Một là tạo ra năm mảng (một cho mỗi mức độ nghiêm trọng), sau đó lặp qua mảng đó và đẩy giá trị băm vào mảng mức độ nghiêm trọng thích hợp. Sau đó, tôi có thể tập hợp lại chúng và thay thế mảng ban đầu bằng mảng đã sắp xếp.

Một cách khác mà người bạn của tôi đã đưa ra là chỉ định mức độ nghiêm trọng (được lưu trữ dưới dạng văn bản trong băm) cho một số nubmers và cmp chúng. Có thể một cái gì đó như thế này?

sub getVal { 
    my $entry = $_[0]; 
    %lookup = ("critical" => 0, ...); 
    return $lookup(entry("bug_severity")); 
} 
@sorted = sort { getVal($a) <=> getVal($b) } @unsorted; 

Answer 1

Tôi thích giải pháp đề xuất của bạn:

my %sevs = (critical => 0, high => 1, ...); 
my @sorted = sort { $sevs{$a->{bug_severity}} <=> $sevs{$b->{bug_severity}} } @unsorted 

Answer 2

Để tránh gọi getVal nhiều lần hơn mức cần thiết, bạn có thể sử dụng "trang trí, sắp xếp, undecorate". Trang trí là nhận được thông tin mà bạn thực sự quan tâm đến cho các loại:

my @decorated = map { [ $_, getVal($_) ] } @unsorted; 

Sau đó, sắp xếp danh sách trang trí:

my @sortedDecorate = sort { $a->[1] <=> $b->[1] } @decorated; 

Sau đó lấy thông tin ban đầu trở lại (undecorate):

my @sorted = map { $_->[0] } @sortedDecorate; 

Hoặc cách Perl-ish hơn để làm điều đó:

@sorted = map { $_->[0] } 
      sort { $a->[1] <=> $b->[1] } 
      map { [ $_, getVal($_) ] } @unsorted; 

Answer 3

Bạn có thể sử dụng Schwartzian Transform:

my @sorted = map { $_->[1] } 
      sort { $a->[0] <=> $b->[0] } 
      map { [ $lookup{$_->{bug_severity}, $_ ] } 
      @unsorted; 

Giải thích:

map { [ $lookup{$_->{bug_severity}, $_ ] } @unsorted; 

bản đồ mỗi lỗi cho một tham chiếu mảng mà các yếu tố đầu tiên là lỗi số mức độ nghiêm trọng từ các bảng tra cứu. Sử dụng Chuyển đổi Schwartz, bạn chỉ tìm giá trị một lần cho mỗi lỗi trong @unsorted.

Sau đó,

sort { $a->[0] <=> $b->[0] } 

loại mà mảng bởi các yếu tố đầu tiên. Cuối cùng,

@sorted = map { $_->[1] } 

kéo ra các lỗi ban đầu từ các mảng trả về bởi sort.

Có thực sự không cần thiết cho getval khi tất cả nó đang làm là một tra cứu băm.

Đối với tự động tạo ra máy phân loại hiệu quả, CPAN mô-đun Sort::Maker là tuyệt vời:

use strict; use warnings; 

use Sort::Maker; 

my @bugs = (
    { name => 'bar', bug_severity => 'severe' }, 
    { name => 'baz', bug_severity => 'noncritical' }, 
    { name => 'foo', bug_severity => 'critical' }, 
); 

my $sorter = make_sorter('ST', 
    name  => 'severity_sorter', 
    init_code => 'my %lookup = (
        critical => 0, 
        severe => 1, 
        noncritical => -1);', 
    number => [ code => '$lookup{$_->{bug_severity}}' ], 
); 

use Data::Dumper; 
print Dumper $_ for severity_sorter(@bugs); 

Output:

 
$VAR1 = { 
      'name' => 'baz', 
      'bug_severity' => 'noncritical' 
     }; 
$VAR1 = { 
      'name' => 'foo', 
      'bug_severity' => 'critical' 
     }; 
$VAR1 = { 
      'name' => 'bar', 
      'bug_severity' => 'severe' 
     }; 

Lưu ý rằng số lượng tra cứu mà cần phải được thực hiện khi sử dụng phương pháp ngây thơ phụ thuộc vào số lượng các phần tử trong @unsorted. Chúng ta có thể đếm chúng sử dụng chương trình rất đơn giản:

#!/usr/bin/perl 

use strict; 
use warnings; 

my ($n_elements) = @ARGV; 

my @keys = qw(a b c); 
my %lookup = map { $keys[$_-1] => $_ } 1 .. @keys; 

my @unsorted = map { $keys[rand 3] } 1 .. $n_elements; 

my $n_lookups; 

my @sorted = sort { 
    $n_lookups += 2; 
    $lookup{$a} <=> $lookup{$b} 
} @unsorted; 

print "It took $n_lookups lookups to sort $n_elements elements\n"; 

Output:

 
C:\Temp> tzt 10 
It took 38 lookups to sort 10 elements 

C:\Temp> tzt 100 
It took 978 lookups to sort 100 elements 

C:\Temp> tzt 1000 
It took 10916 lookups to sort 1000 elements 

C:\Temp> tzt 10000 
It took 113000 lookups to sort 10000 elements 

Do đó, người ta sẽ cần thêm thông tin để quyết định xem các loại ngây thơ hoặc sử dụng Schwartzian Biến đổi sự là giải pháp thích hợp.

Và đây là một chuẩn mực đơn giản mà dường như đồng ý với lập luận @ Ether của:

#!/usr/bin/perl 

use strict; 
use warnings; 

use Benchmark qw(cmpthese); 

my ($n_elements) = @ARGV; 

my @keys = qw(foo bar baz); 
my %lookup = map { $keys[$_] => $_ } 0 .. $#keys; 

my @unsorted = map { {v => $keys[rand 3]} } 1 .. $n_elements; 

cmpthese(-1, { 
    naive => sub { 
     my @sorted = sort { 
      $lookup{$a->{v}} <=> $lookup{$b->{v}} 
     } @unsorted; 
    }, 
    schwartzian => sub { 
     my @sorted = map { $_->[1] } 
        sort { $a->[0] <=> $b->[0] } 
        map { [$lookup{$_->{v}}, $_] } 
        @unsorted; 
    } 
}); 

Output:

 
C:\Temp> tzt 10 
       Rate schwartzian  naive 
schwartzian 18842/s   --  -29% 
naive  26357/s   40%   -- 

C:\Temp> tzt 100 
       Rate  naive schwartzian 
naive  1365/s   --  -11% 
schwartzian 1532/s   12%   -- 

C:\Temp> tzt 1000 
      Rate  naive schwartzian 
naive  121/s   --  -11% 
schwartzian 135/s   12%   -- 

Answer 4

Bạn có thể sử dụng một bảng tra cứu để xác định thứ tự của thử thách gay go bugzilla, như thế này (sử dụng dữ liệu mẫu để minh họa):

use strict; use warnings; 
use Data::Dumper; 

my @bugInfo = (
       { id => 1, 
        assignee => 'Bob', 
        severity => 'HIGH' 
       }, 
       { id => 2, 
        assignee => 'Anna', 
        severity => 'LOW' 
       }, 
       { id => 3, 
        assignee => 'Carl', 
        severity => 'EXTREME' 
       }, 
      ); 
my %severity_ordering = (
    EXTREME => 0, 
    HIGH => 1, 
    MEDIUM => 2, 
    LOW => 3, 
); 
sub byseverity 
{ 
    $severity_ordering{$a->{severity}} <=> $severity_ordering{$b->{severity}} 
} 

my @sortedBugs = sort byseverity @bugInfo; 
print Dumper(\@sortedBugs); 

sản lượng:

$VAR1 = [ 
      { 
      'assignee' => 'Carl', 
      'id' => 3, 
      'severity' => 'EXTREME' 
      }, 
      { 
      'assignee' => 'Bob', 
      'id' => 1, 
      'severity' => 'HIGH' 
      }, 
      { 
      'assignee' => 'Anna', 
      'id' => 2, 
      'severity' => 'LOW' 
      } 
     ];