¿Cómo puedo ordenar una matriz de referencias hash por uno de los valores hash?

Question

En primer lugar, perdón por favor mi oxidado Perl. Estoy tratando de modificar el "whine.pl" de Bugzilla para generar listas de errores ordenados por gravedad.

Me da una variedad de referencias hash. Cada hash contiene un montón de información sobre un error en particular (id, asignatario, gravedad, etc.). Quiero ordenar la matriz por gravedad. ¿Cuál es la mejor manera de hacer esto?

Me gustaría tener un par de posibilidades. Una es crear cinco matrices (una para cada nivel de gravedad), luego recorrer la matriz e insertar las referencias hash en la matriz de niveles de gravedad apropiada. Después de esto, podría volver a montarlos y reemplazar la matriz original con la ordenada.

Otra forma en que mi amigo se acercó sería asignar los niveles de gravedad (almacenados como texto en los hashes) a algunos nubmers, y cmp ellos. Tal vez algo como esto?

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

Answer 1

me gusta la solución propuesta:

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

Answer 2

para evitar llamar GETVAL más veces de lo necesario, puede utilizar "decorar, clasificar, Undecorate". Decorar está recibiendo la información que realmente se preocupan por el tipo:

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

Luego, ordenar la lista decorado:

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

a continuación, obtener la información original de nuevo (Undecorate):

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

O la forma más Perl-ish de hacerlo:

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

Answer 3

Puede utilizar el Schwartzian Transform:

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

Explicación:

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

mapea cada insecto a una referencia a un array cuyo primer elemento es la gravedad de errores numéricos de la tabla de consulta. Con la Transformada de Schwartz, , busca el valor solo una vez para cada error en @unsorted.

Entonces,

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

tipo que array por el primer elemento. Por último,

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

saca los errores originales de la matriz devuelta por sort.

Realmente no hay necesidad de getval cuando todo lo que hace es una búsqueda hash.

para generar automáticamente clasificadores eficientes, módulo CPAN Sort::Maker es excelente:

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

de salida:

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

Nota que el número de búsquedas que necesitan ser realizado cuando se utiliza el método ingenuo depende de la cantidad de elementos en @unsorted. Podemos contar con ellos utilizando el programa simple:

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

Salida:

 
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 

Por lo tanto, se necesitaría más información para decidir si el tipo ingenuo o utilizando la Transformada Schwartzian es la solución adecuada.

Y aquí es un punto de referencia simple que parece estar de acuerdo con el argumento @ de Éter:

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

Salida:

 
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

Se podría utilizar una tabla de búsqueda para determinar el orden de los niveles de gravedad de Bugzilla, así (usando datos de muestra para ilustrar):

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

rendimientos:

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