6

首先，请原谅我生锈的 Perl。我正在尝试修改 Bugzilla 的“whine.pl”以生成按严重性排序的错误列表。

所以它给了我一个哈希引用数组。每个散列包含一堆关于特定错误的信息（id、受让人、严重性等）。我想按严重性对数组进行排序。最好的方法是什么？

我想出了几个可能性。一种是创建五个数组（每个严重级别一个），然后遍历数组并将哈希引用推送到适当的严重级别数组中。在此之后，我可以重新组装它们并用排序的数组替换原始数组。

我的朋友想出的另一种方法是将严重级别（存储为哈希中的文本）分配给一些 nummers，然后对它们进行 cmp。也许是这样的？

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

4 回答 4

7

为避免调用 getVal 次数过多，您可以使用“装饰、排序、取消装饰”。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;
于 2009-10-28T22:13:53.433 回答
4

您可以使用Schwartzian 变换：

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

解释：

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

将每个错误映射到一个数组引用，其第一个元素是查找表中的数字错误严重性。使用 Schwartzian 变换，您只需为@unsorted.

然后，

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

按第一个元素对该数组进行排序。最后，

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

从 . 返回的数组中提取原始错误sort。

getval当它所做的只是哈希查找时，真的没有必要。

对于自动生成高效的排序器，CPAN 模块Sort::Maker非常棒：

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 = {
          '名称' => 'baz',
          'bug_severity' => '非关键'
        };
$VAR1 = {
          '名称' => 'foo',
          'bug_severity' => '关键'
        };
$VAR1 = {
          '名称' => '酒吧',
          'bug_severity' => '严重'
        };

请注意，使用 naive 方法时需要进行的查找次数取决于@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
对 10 个元素进行排序需要 38 次查找

C:\Temp> tzt 100
对 100 个元素进行排序需要 978 次查找

C:\Temp> tzt 1000
对 1000 个元素进行排序需要 10916 次查找

C:\Temp> tzt 10000
对 10000 个元素进行排序需要 113000 次查找

因此，需要更多信息来确定朴素排序还是使用施瓦茨变换是合适的解决方案。

这是一个简单的基准，似乎与@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
               评价施瓦茨式的天真
施瓦茨 18842/s -- -29%
天真 26357/s 40% --

C:\Temp> tzt 100
              评价天真的施瓦茨安
天真 1365/s -- -11%
施瓦茨 1532/s 12% --

C:\Temp> tzt 1000
             评价天真的施瓦茨安
幼稚 121/s -- -11%
schwartzian 135/s 12% --
于 2009-10-28T22:15:11.463 回答
3

我喜欢您提出的解决方案：

my %sevs = (critical => 0, high => 1, ...);
my @sorted = sort { $sevs{$a->{bug_severity}} <=> $sevs{$b->{bug_severity}} } @unsorted
于 2009-10-28T22:09:57.730 回答
0

您可以使用查找表来确定 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'
          }
        ];
于 2009-10-28T22:25:35.623 回答