Come si ordina una matrice di riferimenti hash con uno dei valori hash?

Question

In primo luogo, per favore perdoni il mio arrugginito Perl. Sto cercando di modificare "whine.pl" di Bugzilla per generare liste di bug ordinati per gravità.

Quindi mi fornisce una serie di riferimenti hash. Ogni hash contiene una serie di informazioni su un particolare bug (id, assegnatario, severità, ecc.). Voglio ordinare l'array per gravità. Qual'è il miglior modo per farlo?

Mi piacerebbe venire con un paio di possibilità. Uno è quello di creare cinque array (uno per ciascun livello di gravità), quindi eseguire il loop sull'array e inserire i riferimenti hash nell'array di livello di gravità appropriato. Dopo questo, ho potuto riassemblarli e sostituire la matrice originale con quella ordinata.

Un altro modo in cui è venuto fuori il mio amico è stato quello di assegnare i livelli di gravità (memorizzati come testo negli hash) ad alcuni nubmers, e cmp loro. Forse qualcosa del genere?

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

Answer 1

Mi piace la tua soluzione proposta:

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

Answer 2

di evitare di chiamare GetVal più volte di quanto necessario, è possibile utilizzare "decorare, ordinare, undecorate". Decorare sta ottenendo le informazioni che in realtà si preoccupano per l'ordinamento:

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

Poi ordinare l'elenco decorato:

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

quindi ottenere le informazioni originali posteriore (undecorate):

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

O più il modo Perl-ish per farlo:

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

Answer 3

È possibile utilizzare il Schwartzian Transform:

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

Spiegazione:

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

associa ogni errore ad un riferimento array i cui primo elemento è la gravità insetto numerico dalla tabella di ricerca. Utilizzando la trasformazione di Schwartzian, , il valore viene rilevato una sola volta per ogni errore in @unsorted.

Poi,

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

ordinamenti che matrice dal primo elemento. Infine,

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

tira fuori gli insetti originali restituito da sort.

Non c'è davvero bisogno di getval quando tutto ciò che sta facendo è una ricerca hash.

per la generazione automatica sorter efficienti, modulo CPAN Sort::Maker è eccellente:

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

uscita:

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

noti che il numero di ricerche che devono essere fatte quando si utilizza il metodo naif dipende il numero di elementi in @unsorted. Siamo in grado di contarli utilizzando il semplice programma:

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

uscita:

 
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 

Pertanto, si avrebbe bisogno di più informazioni per decidere se l'ordinamento ingenuo o utilizzando la Trasformata di Schwartz è la soluzione appropriata.

E qui è un semplice punto di riferimento, che sembra essere d'accordo con l'argomento @ di Ether:

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

uscita:

 
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

Si potrebbe utilizzare una tabella di ricerca per determinare l'ordinamento dei rigori Bugzilla, come questo (utilizzando i dati di esempio per illustrare):

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

rese:

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