Czy sortowanie pomaga w wydajności grep w Perl

Question

Poszukuję informacji o tym, jak działa funkcja Perla grep. Robię to:

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

Załóżmy @bar jest duża (setki tysięcy elementów). Z moimi danymi, jeśli sortuję @bar, wartości $foo są bardziej prawdopodobne w pobliżu początku tablicy niż przy końcu. Zastanawiam się, czy to pomoże w osiągach.

Innymi słowy, z powyższym kodem, grep przesuwa się sekwencyjnie przez @bar sprawdzając, czy $foo == $_, a następnie natychmiast kończy działanie, gdy jakakolwiek wartość zostanie uznana za prawdziwą? A może faktycznie sprawdziłby każdy element @bar przed zwróceniem wartości?

Answer 1

grep nie powoduje zwarcia, więc zamawianie elementów nie ma znaczenia.

Podczas gdy lista :: MoreUtils first ma zwarcie, cała lista musi zostać umieszczona na stosie zanim zostanie wywołana.

To będzie najlepsze:

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

Updated: I początkowo potwierdził ciągu indeksów ponieważ używa O (1) pamięć, ale tak nie for (@bar) (w przeciwieństwie do for (LIST) w ogóle) jako ysth przypomnienia mnie.

Answer 2

Ponieważ twoje użycie grep jest w kontekście skalarnym, zwraca liczbę pasujących elementów. Aby to obliczyć, Perl musi odwiedzić każdy element w każdym razie, więc jest mało prawdopodobne, że sortowanie pomogłoby w osiągnięciu wydajności pod tym kątem.

Answer 3

W odniesieniu do Twojego pytania

z moimi danymi, jeśli rodzaj @bar, wartości $ foo jest bardziej prawdopodobne, aby pojawić się w pobliżu początku tablicy niż pod koniec. Zastanawiam się, czy to pomoże w osiągach.

Jeżeli lista jest sortowana w kolejności numerycznej następnie można napisać

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

some_code() if contains(\@bar, $foo); 

Answer 4

W przykładzie grep będzie iteracyjne cały szereg niezależnie ile elementy dopasowane.

Jeśli możesz uporządkować tę tablicę - szybciej będzie wyszukiwać wartości za pomocą wyszukiwania binarnego. Możesz także przekonwertować tablicę na hasz (za pomocą keys = element tablicy) i wykonywać kontrole ze stałym czasem, ale zajmie to dodatkową pamięć.

Answer 5

To zależy. A grep { $x == $_ } @a nie korzysta z przewidywania rozgałęzień, ale robi to 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".$/; 

Wyniki:

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 

Zobacz także Why is it faster to process a sorted array than an unsorted array?