L'ordinamento aiuta l'efficienza di grep in Perl

Question

Sto cercando alcuni dettagli su come funziona la funzione grep di Perl. Sto facendo questo:

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

Supponiamo @bar è grande (centinaia di migliaia di elementi). Con i miei dati, se ordino @bar, è più probabile che i valori di $foo appaiano vicino all'inizio dell'array piuttosto che vicino alla fine. Mi chiedo se questo aiuterà le prestazioni.

altre parole, con il codice di cui sopra, fa grep spostare sequenzialmente attraverso @bar verificare se $foo == $_ e quindi uscire immediatamente dopo ogni valore è stato trovato per essere vero? O controllerebbe effettivamente ogni elemento di @bar prima di restituire un valore?

Answer 1

grep non cortocircuito, quindi l'ordine degli elementi non ha importanza.

Mentre List :: MoreUtils's first esegue un cortocircuito, l'intera lista deve essere posizionata nello stack prima che venga chiamata.

Questo sarà migliore:

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

Aggiornato: Originariamente ho ripetuti sugli indici in quanto che utilizza O (1) di memoria, ma così fa for (@bar) (al contrario di for (LIST) in generale) come ysth ricordato me.

Answer 2

Poiché l'utilizzo di grep è in contesto scalare, restituisce il numero di elementi corrispondenti. Per calcolare questo, Perl deve visitare ogni elemento in ogni caso, quindi è improbabile che l'ordinamento possa aiutare le prestazioni da questo punto di vista.

Answer 3

Per quanto riguarda la tua domanda

Con i miei dati, se I sorta @pluto, valori di $ foo hanno più probabilità di comparire vicino all'inizio della matrice rispetto verso la fine. Mi chiedo se questo aiuterà le prestazioni.

Se la lista è ordinata in ordine numerico, allora è possibile scrivere

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

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

Answer 4

Nel tuo esempio grep itererà tutta una serie indipendentemente quanti elementi abbinati.

Se è possibile mantenere ordinato questo array, è più veloce cercare i valori utilizzando la ricerca binaria. Inoltre puoi convertire il tuo array in hash (con keys = array element) e fare i tuoi controlli a tempo costante, ma questo mangerà memoria aggiuntiva.

Answer 5

Dipende. A grep { $x == $_ } @a non beneficia della previsione filiale, ma grep { $x < $_ } @a sì!

#!/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".$/; 

I risultati:

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 

Vedi anche Why is it faster to process a sorted array than an unsorted array?