切出第n个元素的倍数

Question

我有一个超过10k元素的列表.我想删除每个第三个元素.

例如,

@testlists = qw (helloworld sessions first.cgi login localpcs depthhashes.cgi search view macros plugins ...) ; 

我想删除first.cgi,depthhashses.cgi,macros从原来的阵列等.Grep功能稍慢一点.请建议我更快的grep搜索或任何其他类似的子程序.任何帮助将受到高度赞赏

Answer 1

我可以想到几个解决方案:

• 关于指数可分性的Grep

  my $i = 0;
  @testlist = grep { ++$i % 3 } @testlist;
  

• 重复拼接

  for (my $i = 2; $i < $#testlist; $i += 2) {
    splice @testlist, $i, 1;
  }
  

• 复制跳过

  my @output;
  # pre-extend the array for fewer reallocations
  $#output = @testlist * 2/3;
  @output = ();
  
  # FIXME annoying off-by one errors at the end that can add one undef
  for (my $i = 0; $i < @testlist; $i += 3) {
    push @output, @testlist[$i, $i+1];
  }
  

Ikegami在他非凡的答案中纠正并优化了复制解决方案.

具有1,000个元素列表的基准声明拼接明显的赢家:

         Rate  slice   grep   copy splice
slice   790/s     --   -10%   -18%   -37%
grep    883/s    12%     --    -8%   -29%
copy    960/s    22%     9%     --   -23%
splice 1248/s    58%    41%    30%     --

(slice是暴民的解决方案)

这可能是因为它将大部分实际工作卸载到C级实现中,并避免了分配和昂贵的Perl级操作.

拥有10,000个元素的列表,优势转向其他解决方案.实际上,拼接解决方案的算法复杂度非常差,因为它会在所有拼接位置之后移动所有元素,这意味着最后一个元素移动了近3333次:

         Rate splice  slice   grep   copy
splice 42.7/s     --   -35%   -42%   -49%
slice  65.3/s    53%     --   -12%   -23%
grep   74.2/s    74%    14%     --   -12%
copy   84.4/s    98%    29%    14%     --

这是我用于基准测试的脚本.