Jak sortować tablicę odwołań hashowych według jednej z wartości mieszania?

Question

Po pierwsze, przepraszam mój zardzewiały Perl. Próbuję zmodyfikować "whine.pl" Bugzilli, aby wygenerować listę błędów posortowanych według ważności.

Daje mi to zestaw odniesień hashowych. Każdy skrót zawiera garść informacji o konkretnym błędzie (identyfikator, cesjonariusz, poziom ważności itd.). Chcę posortować tablicę według wagi. Jaki jest najlepszy sposób na zrobienie tego?

Wymyślę kilka możliwości. Jedną z nich jest utworzenie pięciu tablic (po jednej dla każdego poziomu istotności), a następnie przełożenie pętli przez tablicę i wypchnięcie znaków skrótu do odpowiedniej tablicy poziomu istotności. Następnie mogłem je ponownie złożyć i zastąpić oryginalną tablicę posortowaną.

Innym sposobem, w jaki wymyślił mój przyjaciel, byłoby przypisanie poziomu ważności (przechowywanego jako tekst w hashach) do niektórych nubmerów i wykonanie polecenia cmp. Może coś takiego?

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

Answer 1

Lubię swoje proponowane rozwiązanie:

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

Answer 2

Aby uniknąć wywoływania GETVAL więcej razy niż jest to konieczne, można użyć "ozdobić, sortowanie, undecorate". Udekoruj dostaje informacje, które rzeczywiście dbają o do sortowania:

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

Następnie sortować urządzone listę:

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

następnie dostać oryginalne informacje z powrotem (undecorate):

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

Lub bardziej Perl-owski sposób to zrobić:

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

Answer 3

Można użyć Schwartzian Transform:

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

Objaśnienie:

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

odwzorowuje każdy błąd w odniesieniu do tablicy, której pierwszym elementem jest numeryczna surowość bug z tabeli. Używając transformacji Schwartzian, możesz wyszukać wartość tylko raz dla każdego błędu w @unsorted.

Następnie

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

rodzaju, że tablica przez pierwszy element. Wreszcie

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

wyciąga oryginalne błędy z tablicy zwróconej przez sort.

Naprawdę nie ma potrzeby, aby getval, gdy wszystko, co robi, jest hash wyszukiwania.

Dla automatycznego generowania efektywnych sortowniki, CPAN moduł Sort::Maker jest doskonała:

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); 

wyjściowa:

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

Należy zauważyć, że liczba wyszukiwań, które muszą być wykonane przy użyciu metody naiwne zależy liczba elementów w @unsorted. Możemy liczyć je za pomocą prostego programu:

#!/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"; 

wyjściowa:

 
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 

Dlatego jednym potrzeba będzie więcej informacji, aby zdecydować, czy naiwny sortowania lub używając Transformacja Schwartza jest odpowiednim rozwiązaniem.

I tu jest prostym wyznacznikiem, który wydaje się zgodzić z argumentem @ eter za:

#!/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; 
    } 
}); 

wyjściowa:

 
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

Można użyć tabeli odnośników do określenia uporządkowania severities Bugzilla, w ten sposób (przy użyciu przykładowych danych do zilustrowania):

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); 

wydajność:

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