Wie sortiere ich ein Array von Hash-Referenzen durch einen der Hash-Werte?

Question

Zuerst verzeihen Sie bitte meine rostige Perl. Ich versuche, Bugzillas "whine.pl" zu modifizieren, um Buglisten nach Schweregrad zu erstellen.

So gibt es mir eine Reihe von Hash-Referenzen. Jeder Hash enthält eine Reihe von Informationen über einen bestimmten Fehler (ID, Bearbeiter, Schweregrad usw.). Ich möchte das Array nach Schweregrad sortieren. Was ist der beste Weg, dies zu tun?

Ich hätte mir ein paar Möglichkeiten ausgedacht. Eine besteht darin, fünf Arrays zu erstellen (eines für jede Ebene des Schweregrads), dann eine Schleife über das Array zu legen und die Hash-Referenzen in das entsprechende Array des Schweregrads zu schieben. Danach konnte ich sie wieder zusammensetzen und das ursprüngliche Array durch das sortierte ersetzen.

Eine andere Möglichkeit, die mein Freund gefunden hat, wäre es, die Schweregrade (die als Text in den Hashes gespeichert sind) einigen Nubmern zuzuweisen und sie zu Cmp zu machen. Vielleicht so etwas?

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

Answer 1

Ich mag Ihre vorgeschlagene Lösung:

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

Answer 2

getVal mehr Zeit als nötig Aufruf zu vermeiden, können Sie "dekorieren, sortieren, undecorate". Dekorieren ist immer die Informationen, die Sie über tatsächlich Sorge für die Art:

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

dann die eingerichtete Liste sortieren:

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

Dann wieder die ursprünglichen Informationen erhalten (undecorate):

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

Oder die mehr Perl-Weise, es zu tun:

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

Answer 3

können Sie die Schwartzian Transform verwenden:

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

Erläuterung:

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

jeden Fehler auf ein Array Referenzkarten, deren erstes Element der numerische Fehler Schwere aus der Lookup-Tabelle. Mit der Schwartzian Transformation, , suchen Sie den Wert nur einmal für jeden Fehler in. Dann

,

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

Sortiervorgänge, die Anordnung durch das erste Element. Schließlich

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

zieht die ursprünglichen Fehler aus dem Array von sort zurückgegeben.

Es gibt wirklich keine Notwendigkeit für getval, wenn alles, was es tut, ein Hash-Lookup ist.

zur automatischen Generierung effizienter Sortierer, Sort::Maker CPAN-Modul ist ausgezeichnet:

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

Ausgang:

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

Beachten Sie, dass die Anzahl der Abfragen, die gemacht werden müssen, wenn die naive Methode hängt davon ab, die Anzahl der Elemente in @unsorted. Wir können sie mit dem einfachen Programm zählen:

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

Ausgang:

 
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 

Daher würde eine weitere Informationen benötigen, um zu entscheiden, ob die naive Art oder mit der Schwartzian Trans die geeignete Lösung ist.

Und hier eine einfache Benchmark ist, die mit @ Ether Argumente zustimmen scheint:

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

Ausgang:

 
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

Sie eine Lookup-Tabelle verwenden, könnten die Reihenfolge der Bugzilla severities, um zu bestimmen, wie folgt (unter Verwendung von Beispieldaten zur Veranschaulichung):

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

ergibt:

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