检查数组中元素的更快方法？

Question

此函数exists与哈希相同.

我计划使用它很多.

它能以某种方式进行优化吗？

my @a = qw/a b c d/;

my $ret = array_exists("b", @a);

sub array_exists {
    my ($var, @a) = @_;

    foreach my $e (@a) {
        if ($var eq $e) {
            return 1;
        }
    }
    return 0;
}

Answer 1

如果必须在固定数组上执行此操作,请使用哈希:

 my %hash = map { $_, 1 } @array;

 if( exists $hash{$key} ) { ... }

有些人会选择智能匹配运算符,但这是我们需要从Perl中删除的功能之一.您需要确定它是否应匹配,其中数组包含具有键的哈希引用的数组引用b:

use 5.010;

my @a = (
    qw(x y z),
    [ { 'b' => 1 } ],
    );

say 'Matches' if "b" ~~ @a; # This matches

由于智能匹配是递归的,因此如果继续进入数据结构.我在重新思考智能匹配时写了一些内容.

Answer 2

您可以使用Perl 5.10及更高版本中提供的智能匹配:

if ("b" ~~ @a) {
    # "b" exists in @a
}

这应该比函数调用快得多.

Answer 3

我使用List :: MoreUtils :: any.

my $ret = any { $_ eq 'b' } @a;

Answer 4

由于StackOverflow上有许多类似的问题，其中不同的“正确答案”返回不同的结果，因此我尝试将它们进行比较。这个问题似乎是分享我的小基准的好地方。

在我的测试中，我使用了@test_set长度为10的1,000个元素（字符串）的测试集（），其中只有一个元素（$search_value）与给定的字符串匹配。

我采用以下语句来验证此元素是否存在100,000转。

_grep

grep( $_ eq $search_value, @test_set )

_哈希

{ map { $_ => 1 } @test_set }->{ $search_value }

_hash_premapped

$mapping->{ $search_value }

• 使用$mapping预先计算为的$mapping = { map { $_ => 1 } @test_set }（最终测量中包含的）

_ 正则表达式

sub{ my $rx = join "|", map quotemeta, @test_set; $search_value =~ /^(?:$rx)$/ }

_ regex_prejoined

$search_value =~ /^(?:$rx)$/

• 使用$rx预先计算为的正则表达式$rx = join "|", map quotemeta, @test_set;（包含在最终度量中）

_manual_first

sub{ foreach ( @test_set ) { return 1 if( $_ eq $search_value ); } return 0; }

_第一

first { $_ eq $search_value } @test_set

• 来自List::Util（1.38版）

_聪明

$search_value ~~ @test_set

_任何

any { $_ eq $search_value } @test_set

• 从List::MoreUtils（版本0.33）

在我的机器（Ubuntu，3.2.0-60通用，x86_64，Perl v5.14.2）上，我得到了以下结果。示出的值是秒，并通过返回gettimeofday和tv_interval的Time::HiRes（1.9726版本）。

元素$search_value位于数组中的位置0@test_set

_hash_premapped:    0.056211
_smart:             0.060267
_manual_first:      0.064195
_first:             0.258953
_any:               0.292959
_regex_prejoined:   0.350076
_grep:              5.748364
_regex:             29.27262
_hash:              45.638838

元素$search_value位于数组中的位置500@test_set

_hash_premapped:    0.056316
_regex_prejoined:   0.357595
_first:             2.337911
_smart:             2.80226
_manual_first:      3.34348
_any:               3.408409
_grep:              5.772233
_regex:             28.668455
_hash:              45.076083

元素$search_value位于数组中的位置999@test_set

_hash_premapped:    0.054434
_regex_prejoined:   0.362615
_first:             4.383842
_smart:             5.536873
_grep:              5.962746
_any:               6.31152
_manual_first:      6.59063
_regex:             28.695459
_hash:              45.804386

结论

检查数组中元素是否存在的最快方法是使用准备好的哈希。当然，您可以按一定比例的内存消耗来购买它，并且仅当您多次搜索集合中的元素时才有意义。如果您的任务只包含少量数据并且仅进行一次或几次搜索，则哈希甚至可能是最糟糕的解决方案。速度不一样快，但是类似的想法是使用预准备的正则表达式，看起来准备时间更短。

在许多情况下，没有准备好的环境是没有选择的。

令人惊讶的List::Util::first是，在比较没有准备好的环境的语句时，结果非常好。在开始时具有搜索值（也可以将其解释为较小集合中的结果），它非常接近收藏夹，~~ 并且any（甚至可能在测量误差范围内）。对于我较大的测试集中的中间或结尾处的项目，首先绝对是最快的。