18

我想重复搜索不变的数组中的值。

到目前为止，我一直在这样做：我将值放在一个哈希中（所以我有一个数组和一个内容基本相同的哈希），然后我使用exists.

我不喜欢有两个不同的变量（数组和哈希）都存储相同的东西；但是，散列的搜索速度要快得多。

我发现~~Perl 5.10 中有一个 (smartmatch) 运算符。在数组中搜索标量时效率如何？

4

3 回答 3

39

如果要在数组中搜索单个标量，可以使用List::Util的first子例程。它一知道答案就停下来。如果您已经拥有 hash ，我不希望这比哈希查找更快，但是当您考虑创建哈希并将其保存在内存中时，只搜索您已经拥有的数组可能会更方便。

至于 smart-match 算子的聪明，如果你想看看它有多聪明，那就测试一下吧。:)

您至少要检查三个案例。最坏的情况是你想找到的每个元素都在最后。最好的情况是您要查找的每个元素都位于开头。可能的情况是您要查找的元素平均位于中间。

现在，在我开始这个基准测试之前，我希望如果智能匹配可以短路（它可以；它记录在perlsyn中），那么尽管数组大小，最佳情况时间将保持不变，而其他情况会变得越来越糟. 如果它不能短路并且每次都必须扫描整个阵列，那么时间应该没有差异，因为每个案例涉及的工作量相同。

这是一个基准：

#!perl
use 5.12.2;
use strict;
use warnings;

use Benchmark qw(cmpthese);

my @hits = qw(A B C);
my @base = qw(one two three four five six) x ( $ARGV[0] || 1 );

my @at_end       = ( @base, @hits );
my @at_beginning = ( @hits, @base );

my @in_middle = @base;
splice @in_middle, int( @in_middle / 2 ), 0, @hits;

my @random = @base;
foreach my $item ( @hits ) {
    my $index = int rand @random;
    splice @random, $index, 0, $item;
    }

sub count {
    my( $hits, $candidates ) = @_;

    my $count;
    foreach ( @$hits ) { when( $candidates ) { $count++ } }
    $count;
    }

cmpthese(-5, {
    hits_beginning => sub { my $count = count( \@hits, \@at_beginning ) },
    hits_end       => sub { my $count = count( \@hits, \@at_end ) },
    hits_middle    => sub { my $count = count( \@hits, \@in_middle ) },
    hits_random    => sub { my $count = count( \@hits, \@random ) },
    control        => sub { my $count = count( [], [] ) },
  }
);

以下是各个部分的作用。请注意，这是两个轴上的对数图，因此下降线的斜率并不像看起来那么接近：

智能匹配速度

所以，看起来智能匹配运算符有点聪明，但这并不能真正帮助你，因为你可能仍然需要扫描整个数组。您可能事先不知道在哪里可以找到您的元素。我希望散列的性能与最佳情况智能匹配相同，即使您必须为此放弃一些内存。

好的，所以智能匹配是智能乘以 2 很棒，但真正的问题是“我应该使用它吗？”。另一种方法是哈希查找，一直困扰着我，我没有考虑过这种情况。

与任何基准测试一样，我在实际测试之前开始考虑结果可能是什么。我希望如果我已经有了哈希值，那么查找一个值会很快。那个案子没问题。我对我还没有哈希的情况更感兴趣。我可以多快使散列和查找成为键？我预计它的表现不会那么好，但它仍然比最坏情况下的智能匹配更好吗？

但是，在您查看基准之前，请记住，仅通过查看数字几乎没有足够的信息来说明您应该使用哪种技术。问题的上下文选择最好的技术，而不是最快的、无上下文的微基准。考虑几个可以选择不同技术的案例：

  • 你有一个数组，你会重复搜索
  • 你总是得到一个只需要搜索一次的新数组
  • 你得到非常大的数组，但内存有限

现在，记住这些，我添加到我之前的程序中：

my %old_hash = map {$_,1} @in_middle; 

cmpthese(-5, {
    ...,
    new_hash       => sub { 
        my %h = map {$_,1} @in_middle; 
        my $count = 0;
        foreach ( @hits ) { $count++ if exists $h{$_} }
        $count;
        },
    old_hash       => sub { 
        my $count = 0;
        foreach ( @hits ) { $count++ if exists $old_hash{$_} }
        $count;
        },
    control_hash   => sub { 
        my $count = 0;
        foreach ( @hits ) { $count++ }
        $count;
        },
    }
);

这是情节。颜色有点难以区分。最低行是您必须在任何时候想要搜索它时创建散列的情况。可以说是很可怜了。最高的两行（绿色）是散列控制（实际上没有散列）和现有散列查找。这是一个日志/日志图；这两种情况甚至比智能匹配控制（只调用一个子程序）还要快。

智能匹配 v. 哈希

还有一些其他的事情需要注意。“随机”案例的行有点不同。这是可以理解的，因为每个基准测试（因此，每个数组规模运行一次）将命中元素随机放置在候选数组中。有些运行将它们放早一点，有些放慢一点，但是由于我@random每次运行整个程序只创建一次数组，所以它们会移动一点。这意味着生产线上的颠簸并不重要。如果我尝试了所有位置并取平均值，我希望“随机”线与“中间”线相同。

现在，看看这些结果，我想说智能匹配在最坏的情况下比哈希查找在最坏的情况下要快得多。这就说得通了。要创建散列，我必须访问数组的每个元素并生成散列，这需要大量复制。智能匹配没有复制。

这是另一个我不会检查的案例。哈希何时变得比智能匹配更好？也就是说，什么时候创建散列的开销在重复搜索中分散得足够多，以至于散列是更好的选择？

于 2010-10-17T21:29:23.747 回答
10

对少量潜在匹配快速，但不比散列快。哈希确实是测试集合成员的正确工具。由于哈希访问是 O(log n) 并且数组上的 smartmatch 仍然是 O(n) 线性扫描（尽管是短路，不像 grep），在允许的匹配中具有较大数量的值，smartmatch 变得相对更差。

基准代码（匹配 3 个值）：

#!perl
use 5.12.0;
use Benchmark qw(cmpthese);

my @hits = qw(one two three);
my @candidates = qw(one two three four five six); # 50% hit rate
my %hash;
@hash{@hits} = ();

sub count_hits_hash {
  my $count = 0;
  for (@_) {
    $count++ if exists $hash{$_};
  }
  $count;
}

sub count_hits_smartmatch {
  my $count = 0;
  for (@_) {
    $count++ when @hits;
  }
  $count;
}

say count_hits_hash(@candidates);
say count_hits_smartmatch(@candidates);

cmpthese(-5, {
    hash => sub { count_hits_hash((@candidates) x 1000) },
    smartmatch => sub { count_hits_smartmatch((@candidates) x 1000) },
  }
);

基准测试结果：

             Rate smartmatch       hash
smartmatch  404/s         --       -65%
hash       1144/s       183%         --
于 2010-10-17T03:10:01.430 回答
9

“智能匹配”中的“智能”与搜索无关。这是关于根据上下文在正确的时间做正确的事情。

循环遍历数组还是索引到哈希中是否更快的问题是您必须进行基准测试的问题，但总的来说，它必须是一个非常小的数组才能比索引到哈希中更快地浏览.

于 2010-10-17T03:31:58.153 回答