7

我正在寻找有关 Perlgrep功能如何工作的一些细节。我正在这样做：

if ( grep{ $foo == $_ } @bar ) {
  some code;
}

假设@bar很大（数十万个元素）。对于我的数据，如果我 sort @bar，值$foo更可能出现在数组的开头附近而不是结尾附近。我想知道这是否有助于提高性能。

换句话说，使用上面的代码，是否通过检查是否grep顺序移动，然后在发现任何值为真后立即退出？或者它会在返回值之前检查每个元素吗？@bar$foo == $_@bar

4

5 回答 5

10

grep不会短路，因此元素的顺序无关紧要。

虽然 List::MoreUtilsfirst确实会短路，但整个列表必须在调用之前放入堆栈。

这将是最好的：

for (@bar) {
   if ($foo == $_) {
      some code;
      last;
   }
}

更新：我最初迭代索引，因为它使用 O(1) 内存，但正如 ysth 提醒我的那样for (@bar)（与一般情况相反）。for (LIST)

于 2013-03-19T18:37:35.833 回答
6

由于您的使用grep是在标量上下文中，因此它返回匹配元素的数量。为了计算这个，Perl 无论如何都必须访问每个元素，因此从这个角度来看，排序不太可能有助于提高性能。

于 2013-03-19T18:20:03.773 回答
2

在您的示例中， grep将迭代整个数组，无论匹配多少元素。

如果您能够保持此数组排序 - 使用二进制搜索来搜索您的值会更快。您也可以将数组转换为哈希（使用键 = 数组元素）并以恒定时间进行检查，但这会占用额外的内存。

于 2013-03-19T20:29:45.100 回答
1

With regard to your question

With my data, if I sort @bar, values of $foo are more likely to appear near the beginning of the array than near the end. I'm wondering if this will help performance.

If the list is sorted in numerical order then you can write

sub contains {
  my ($list, $item) = @_;
  for (@$item) {
    return $_ == $item if $_ >= $item;
  }
  return !1;
}

some_code() if contains(\@bar, $foo);
于 2013-03-19T19:52:58.830 回答
0

这取决于。Agrep { $x == $_ } @a不会从分支预测中受益，但grep { $x < $_ } @a可以！

#!/usr/bin/env perl

use strict;
use warnings;

use Time::HiRes qw( clock_gettime CLOCK_MONOTONIC );

use constant MIN => 0;
use constant MAX => 1000;
use constant AVG => int(MIN  + (MAX - MIN) / 2);
use constant N_LOOPS => 40000;
use constant ARRAY_LEN => 10000;

## is grep faster for sorted arrays?

##
## RANDOM ARRAY VALUES
##
my $n = 0;
my @a = map { int(rand() * (MAX - MIN) + MIN) } 1 .. ARRAY_LEN;
my $duration = -clock_gettime ( CLOCK_MONOTONIC );
for(my $i = 0; $i < N_LOOPS; $i++) {
    $n += grep { AVG < $_ } @a;
}
$duration += clock_gettime ( CLOCK_MONOTONIC );
print "duration: $duration secs, n = $n".$/;

##
## PREDICTABLE ARRAY VALUES
##
$n = 0;
@a = sort {$a <=> $b} @a;
$duration = -clock_gettime ( CLOCK_MONOTONIC );
for(my $i = 0; $i < N_LOOPS; $i++) {
    $n += grep { AVG < $_ } @a;
}
$duration += clock_gettime ( CLOCK_MONOTONIC );
print "duration: $duration secs, n = $n".$/;

## and now we try to eliminate side effects by repeating

##
## RANDOM ARRAY VALUES
##
$n = 0;
@a = map { int(rand() * (MAX - MIN) + MIN) } 1 .. ARRAY_LEN;
$duration = -clock_gettime ( CLOCK_MONOTONIC );
for(my $i = 0; $i < N_LOOPS; $i++) {
    $n += grep { AVG < $_ } @a;
}   
$duration += clock_gettime ( CLOCK_MONOTONIC );
print "duration: $duration secs, n = $n".$/; 

##
## PREDICTABLE ARRAY VALUES
##
$n = 0;
@a = sort {$a <=> $b} @a;
$duration = -clock_gettime ( CLOCK_MONOTONIC );
for(my $i = 0; $i < N_LOOPS; $i++) {
    $n += grep { AVG < $_ } @a;
}   
$duration += clock_gettime ( CLOCK_MONOTONIC );
print "duration: $duration secs, n = $n".$/;

结果：

duration: 27.7465513650095 secs, n = 199880000 <-- unsorted
duration: 26.129752348992 secs, n = 199880000  <-- sorted
duration: 28.3962040760089 secs, n = 202920000 <-- unsorted
duration: 26.082420132996 secs, n = 202920000  <-- sorted

另请参阅为什么处理排序数组比处理未排序数组更快？

于 2013-03-20T05:42:51.610 回答