algorithm - 部分排序算法

Question

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

Answer 1

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

sort正如我所描述的，我已经编写了一个 Perl 选择排序，虽然它比仅在整个列表中使用并选择前十名要快四倍以上，但top函数 fromSort::Key::Top再次快两倍以上。

这是我的代码和结果。AAAA它使用从to 到ZZZZ近半百万的四字符模式列表进行测试。

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)

Answer 2

出现快速搜索，Sort::Key::Top但可能还有其他选择。