algorithm - 部分排序算法

Question

我对 perl 很陌生。所以，如果有明显的答案，我很抱歉。我的问题:对于 C++ 中的 std::partial_sort，Perl 中是否有内置的替代方案。或者至少你能给我推荐一个实现这个算法的 CPAN 模块吗？提前谢谢你。

Answer 1

看起来你想要的是Sort::Key::Top .

我已经按照我的描述写了一个 Perl 选择排序，虽然事实证明它比只使用 sort 快四倍以上。在整个列表中选择前十名，top来自 Sort::Key::Top 的函数又快了一倍多。

这是我的代码和结果。它使用来自 AAAA 的四字符模式列表进行测试。至 ZZZZ - 将近 50 万。

use strict;
use warnings;

use List::Util 'shuffle';
use Sort::Key::Top 'top';
use Benchmark 'timethese';

srand(0);
my @list = shuffle 'AAAA' .. 'ZZZZ';

timethese(100, {

  'Sort::Key::Top' => sub {
    my @topten = top 10 => @list;
  },

  'Pure Perl' => sub {

    my @topten;

    for my $item (@list) {
      if (@topten and $item lt $topten[-1]) {
        my $i = $#topten-1;
        --$i while $i >= 0 and $topten[$i] gt $item;
        splice @topten, $i+1, 0, $item;
        pop @topten if @topten > 10;
      }
      elsif (@topten < 10) {
        push @topten, $item;
      }
    }
  },

  'Perl sort' => sub {
    my @topten = (sort @list)[0..9];
  },
});

输出

Benchmark: timing 100 iterations of Perl sort, Pure Perl, Sort::Key::Top...
     Perl sort: 46 wallclock secs (45.76 usr +  0.11 sys = 45.86 CPU) @  2.18/s (n=100)
     Pure Perl: 11 wallclock secs (10.84 usr +  0.00 sys = 10.84 CPU) @  9.22/s (n=100)
Sort::Key::Top:  4 wallclock secs ( 3.99 usr +  0.13 sys =  4.12 CPU) @ 24.28/s (n=100)