7

grepPerlの機能がどのように機能するかについての詳細を探しています。私はこれをやっています：

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

@bar大きいと仮定します（数十万の要素）。私のデータでは、を並べ替える@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は、一致する要素の数に関係なく、配列全体を反復処理します。

この配列を並べ替えておくことができる場合は、バイナリ検索を使用して値を検索する方が高速です。また、配列をハッシュに変換し（keys = array elementを使用）、一定の時間でチェックを行うことができますが、これは追加のメモリを消費します。

于 2013-03-19T20:29:45.100 に答える
1

あなたの質問に関して

私のデータでは、@ barを並べ替えると、$fooの値が配列の最後の近くよりも最初の近くに表示される可能性が高くなります。これがパフォーマンスに役立つかどうか疑問に思います。

リストが番号順にソートされている場合は、次のように書くことができます

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 に答える