Le tri aide-t-il l'efficacité de grep en Perl?

Question

Je cherche des détails sur le fonctionnement de la fonction grep de Perl. Je fais ceci:

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

Suppose @bar est grande (des centaines de milliers d'éléments). Avec mes données, si je trier @bar, les valeurs de $foo sont plus susceptibles d'apparaître près du début du tableau que vers la fin. Je me demande si cela aidera la performance.

En d'autres termes, avec le code ci-dessus, est-ce que grep se déplace séquentiellement à travers @bar en vérifiant si $foo == $_ et puis quittez immédiatement une fois que toute valeur a été trouvée comme étant vraie? Ou vérifierait-il réellement chaque élément de @bar avant de renvoyer une valeur?

Answer 1

grep ne court-circuite pas, donc l'ordre des éléments n'a pas d'importance.

Alors que List :: MoreUtils first est en court-circuit, la liste entière doit être placée sur la pile avant d'être appelée.

Ce sera mieux:

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

Mise à jour: Au départ, j'Iterated sur les indices depuis utilise O (1) la mémoire, mais si for (@bar) (par opposition à for (LIST) en général) ysth rappelé moi.

Answer 2

Puisque votre utilisation de grep est dans un contexte scalaire, elle renvoie le nombre d'éléments correspondants. Pour calculer cela, Perl doit visiter chaque élément de toute façon, il est donc peu probable que le tri puisse améliorer les performances sous cet angle.

Answer 3

En ce qui concerne votre question

Avec mes données, si je sorte @bar, les valeurs de foo $ sont plus susceptibles d'apparaître près du début du tableau que près de la fin. Je me demande si cela aidera la performance.

Si la liste est triée par ordre numérique, vous pouvez écrire

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

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

Answer 4

Dans votre exemple grep itérera tableau entier quel que soit le nombre d'éléments appariés.

Si vous pouvez conserver ce tableau trié, il est plus rapide de rechercher vos valeurs à l'aide de la recherche binaire. Vous pouvez également convertir votre tableau en hash (avec keys = array element) et faire vos contrôles avec un temps constant, mais cela va manger de la mémoire supplémentaire.

Answer 5

Cela dépend. Un grep { $x == $_ } @a ne bénéficie pas de prédiction de branche, mais grep { $x < $_ } @a fait!

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

Les résultats:

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 

Voir aussi Why is it faster to process a sorted array than an unsorted array?