Как отсортировать массив ссылок на хеш по одному из значений хеша? - PullRequest
Новая
       21

Как отсортировать массив ссылок на хеш по одному из значений хеша?

6 голосов
/ 29 октября 2009

Во-первых, прошу прощения за мой ржавый Perl. Я пытаюсь изменить "whine.pl" в Bugzilla, чтобы генерировать списки ошибок, отсортированных по серьезности.

Так что это дает мне массив ссылок на хеш. Каждый хеш содержит кучу информации о конкретной ошибке (идентификатор, правопреемник, серьезность и т. Д.). Я хочу отсортировать массив по степени серьезности. Какой лучший способ сделать это?

Я бы придумал пару возможностей. Один из них заключается в создании пяти массивов (по одному для каждого уровня серьезности), затем циклически перебирает массив и помещает ссылки на хэш в соответствующий массив уровней серьезности. После этого я могу собрать их и заменить исходный массив отсортированным.

Другим способом, который придумал мой друг, было бы назначить уровни серьезности (хранящиеся в виде текста в хешах) некоторым nubmers и cmp их. Может быть, что-то вроде этого? 

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

Ответы [ 4 ]

7 голосов
/ 29 октября 2009

Чтобы не вызывать getVal чаще, чем необходимо, вы можете использовать "decorate, sort, undecorate". Decorate - это информация, которая вам действительно нужна, для сортировки: 

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

Затем сортируйте оформленный список: 

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

Затем верните оригинальную информацию (неукрашенную): 

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

Или более Perl-иш способ сделать это: 

@sorted = map { $_->[0] }
          sort { $a->[1] <=> $b->[1] }
          map { [ $_, getVal($_) ] } @unsorted;
4 голосов
/ 29 октября 2009

Вы можете использовать Преобразование Шварца : 

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

Пояснение: 

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

отображает каждую ошибку в ссылку на массив, первым элементом которой является числовая серьезность ошибки из таблицы поиска. Используя преобразование Шварца, , вы ищите значение только один раз для каждой ошибки в @unsorted.

Тогда 

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

сортирует этот массив по первому элементу. Наконец, 

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

извлекает исходные ошибки из массива, возвращаемого sort.

На самом деле нет необходимости в getval, когда все, что он делает - это поиск по хешу.

Для автоматического создания эффективных сортировщиков модуль CPAN Сортировка :: Производитель отлично: 

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

Выход: 

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

Обратите внимание, что количество поисков, которые необходимо выполнить при использовании наивного метода, зависит от количества элементов в @unsorted. Мы можем посчитать их, используя простую программу: 

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

Выход: 

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

Следовательно, потребуется больше информации, чтобы решить, является ли наивная сортировка или использование преобразования Шварца подходящим решением.

А вот простой тест, который, кажется, согласуется с аргументом @ 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;
    }
});

Выход: 

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%          --
3 голосов
/ 29 октября 2009

Мне нравится ваше предложенное решение: 

my %sevs = (critical => 0, high => 1, ...);
my @sorted = sort { $sevs{$a->{bug_severity}} <=> $sevs{$b->{bug_severity}} } @unsorted
0 голосов
/ 29 октября 2009

Вы можете использовать справочную таблицу, чтобы определить порядок серьезностей bugzilla, например так (используя примеры данных для иллюстрации): 

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

Выходы: 

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