[Perl]散列的效率出人意料

那天和人讨论一个简单的应用：集合减法，即给定集合 A 和 B ，计算 C = A - B，也就是说求属于A但不属于B的元素。集合A和B使用数组来存储，元素仅限于整数。求计算方法。

Perl自身没有集合运算函数，为了这一个功能也犯不上去安装CPAN模块，所以我们考虑了以下几个方案：

利用foreach作最直白的循环来判断
利用grep代替foreach
将元素用逗号连接之后用正则表达式匹配
将数组转化成散列之后判断

四种方法都能实现，但效率如何？本以为使用foreach应该是最快的，没想到测试之后发现散列居然是最快的。

              Rate    use grep  use regexp use foreach    use hash
use grep     359/s          --        -58%        -63%        -90%
use regexp   861/s        140%          --        -11%        -77%
use foreach  965/s        169%         12%          --        -74%
use hash    3769/s        950%        338%        291%          --

如果元素不是整数而是随机的字符串，正则表达式的效率会急剧下降，而散列依然能保证领先的地位。看来Perl的散列算法不可小觑啊。

附源代码如下：

use Benchmark qw(:all);

@a =  (1..100);
@b = (10..200);

sub use_grep {
  my ($a, $b) = @_;
  my @result;
  
  @result = grep {
    my $tmp = $_; 
    !grep{$_ eq $tmp} @$b;
  } @$a;
  
  return \@result;
}
  
sub use_foreach {
  my ($a, $b) = @_;
  my @result;
  
  foreach my $x (@$a){
    my $not_exist = 1;
    foreach my $y (@$b){
      if($x eq $y){
        $not_exist = 0;
        last;
      }
    }
    push @result, $x if ($not_exist);
  }
  
  return \@result;
}

sub use_regexp {
  my ($a, $b) = @_;
  my @result;

  my $str = ',' . (join ',', @$b) . ',';
  foreach (@$a) {
    push @result, $_ unless $str =~ ",$_,";
  }

  return \@result;
}


sub use_hash {
  my ($a, $b) = @_;
  my @result;
  my %hash;

  foreach (@$b) { $hash{$_} = 1; }
  foreach (@$a) { push @result, $_ unless $hash{$_}; }

  return \@result;
}

#print "use grep: " . (join ',', @{&use_grep(\@a, \@b)}) . "\n";
#print "use foreach: " . (join ',', @{&use_foreach(\@a, \@b)}) . "\n";
#print "use regexp: " . (join ',', @{&use_regexp(\@a, \@b)}) . "\n";
#print "use hash: " . (join ',', @{&use_hash(\@a, \@b)}) . "\n";

#__END__
cmpthese(3000, {
    'use grep' => sub { &use_grep(\@a, \@b) },
    'use foreach' => sub { &use_foreach(\@a, \@b) },
    'use regexp' => sub { &use_regexp(\@a, \@b) },
    'use hash' => sub { &use_hash(\@a, \@b) },
});

charlee.li