L'operatore segreto di Perl Goatse è efficiente?

Question

L'espressione "operatore goatse" o l'idioma =()= in Perl causa la valutazione di un'espressione nel contesto dell'elenco.

Un esempio è:

my $str = "5 and 4 and a 3 and 2 1 BLAST OFF!!!"; 
my $count =()= $str =~ /\d/g; # 5 matches... 
print "There are $count numbers in your countdown...\n\n"; 

Come ho Interprete l'uso, questo è ciò che accade:

1. $str =~ /\d/g soddisfa tutte le cifre. Lo switch g e il contesto elenco producono un elenco di tali corrispondenze. Lascia che questo sia l'esempio di "List Producer", e in Perl questo potrebbe essere molte cose.
2. il =()= causa un'assegnazione a una lista vuota, quindi tutte le corrispondenze effettive vengono copiate in una lista vuota.
3. L'assegnazione in contesto scalare a $ conteggio dell'elenco prodotta nel 2. dà il conteggio della lista o il risultato di 5.
4. Il conteggio di riferimento della lista vuota =()= va a zero dopo l'assegnazione scalare. La copia degli elementi della lista viene quindi cancellata da Perl.

Le domande in materia di efficienza sono questi:

1. Mi sbaglio nel modo in cui sto l'analisi di questo?
2. Se si dispone di un produttore di elenchi e tutto ciò di cui si è interessati è il conteggio, esiste un modo più efficiente per farlo?

Funziona alla grande con questa lista banale, ma cosa succede se la lista era centinaia di migliaia di partite? Con questo metodo stai producendo una copia completa di ogni partita, cancellandola solo per contarli.

Answer 1

Perl 5 è intelligente sulla copia di elenchi. Copia solo tanti oggetti quanti sono sul lato sinistro. Funziona perché l'assegnazione degli elenchi in contesto scalare produce il numero di elementi sul lato destro. Quindi, gli articoli n verranno creati dall'espressione regolare, ma non verranno copiati e scartati, semplicemente scartati. Puoi vedere la differenza che la copia extra fa nel caso di ingenuità nel benchmark qui sotto.

Per quanto riguarda l'efficienza, una soluzione iterativa è spesso più semplice per l'utilizzo della memoria e della CPU, ma questo deve essere valutato rispetto alla brevità dell'operatore segreto goatse. Ecco i risultati del benchmarking delle varie soluzioni:

naive: 10 
iterative: 10 
goatse: 10 

for 0 items: 
       Rate iterative goatse  naive 
iterative 4365983/s  --  -7%  -12% 
goatse 4711803/s  8%  --  -5% 
naive  4962920/s  14%  5%  -- 

for 1 items: 
       Rate  naive goatse iterative 
naive  749594/s  --  -32%  -69% 
goatse 1103081/s  47%  --  -55% 
iterative 2457599/s  228%  123%  -- 

for 10 items: 
       Rate  naive goatse iterative 
naive  85418/s  --  -33%  -82% 
goatse 127999/s  50%  --  -74% 
iterative 486652/s  470%  280%  -- 

for 100 items: 
      Rate  naive goatse iterative 
naive  9309/s  --  -31%  -83% 
goatse 13524/s  45%  --  -76% 
iterative 55854/s  500%  313%  -- 

for 1000 items: 
      Rate  naive goatse iterative 
naive  1018/s  --  -31%  -82% 
goatse 1478/s  45%  --  -75% 
iterative 5802/s  470%  293%  -- 

for 10000 items: 
      Rate  naive goatse iterative 
naive  101/s  --  -31%  -82% 
goatse 146/s  45%  --  -75% 
iterative 575/s  470%  293%  -- 

Qui è il codice che lo ha generato:

#!/usr/bin/perl 

use strict; 
use warnings; 

use Benchmark; 

my $s = "a" x 10; 

my %subs = (
    naive => sub { 
     my @matches = $s =~ /a/g; 
     return scalar @matches; 
    }, 
    goatse => sub { 
     my $count =()= $s =~ /a/g; 
     return $count; 
    }, 
    iterative => sub { 
     my $count = 0; 
     $count++ while $s =~ /a/g; 
     return $count; 
    }, 
); 

for my $sub (keys %subs) { 
    print "$sub: @{[$subs{$sub}()]}\n"; 
} 

for my $n (0, 1, 10, 100, 1_000, 10_000) { 
    $s = "a" x $n; 
    print "\nfor $n items:\n"; 
    Benchmark::cmpthese -1, \%subs; 
} 

Answer 2

Nel vostro esempio particolare, un punto di riferimento è utile:

my $str = "5 and 4 and a 3 and 2 1 BLAST OFF!!!"; 

use Benchmark 'cmpthese'; 

cmpthese -2 => { 
    goatse => sub { 
     my $count =()= $str =~ /\d/g; 
     $count == 5 or die 
    }, 
    while => sub { 
     my $count; 
     $count++ while $str =~ /\d/g; 
     $count == 5 or die 
    }, 
}; 

che resi:

  Rate goatse while 
goatse 285288/s  -- -57% 
while 661659/s 132%  -- 

Il $str =~ /\d/g nel contesto dell'elenco sta acquisendo la sottostringa corrispondente anche se non è necessaria. L'esempio while ha il regex nel contesto scalare (booleano), quindi il motore regex deve solo restituire true o false e non le corrispondenze effettive.

E, in generale, se si dispone di una lista di funzioni di produzione e la cura solo circa il numero di elementi, scrivendo una breve funzione di count è più veloce:

sub make_list {map {$_**2} 0 .. 1000} 

sub count {scalar @_} 

use Benchmark 'cmpthese'; 

cmpthese -2 => { 
    goatse => sub {my $count =()= make_list; $count == 1001 or die}, 
    count => sub {my $count = count make_list; $count == 1001 or die}, 
}; 

che dà:

  Rate goatse count 
goatse 3889/s  -- -26% 
count 5276/s 36%  -- 

mio indovinare perché il sub è più veloce perché le chiamate di subroutine sono ottimizzate per passare le liste senza copiarle (passate come alias).

Answer 3

Se è necessario eseguire qualcosa nel contesto dell'elenco, è necessario eseguirlo nel contesto dell'elenco. In alcuni casi, come quello che presenti, potresti essere in grado di aggirarlo con un'altra tecnica, ma nella maggior parte dei casi non lo farai.

Prima di eseguire il benchmark, tuttavia, la domanda più importante è "Ha importanza?". Profilo prima del tuo benchmark, e preoccupati solo di questo genere di cose quando non hai più problemi da risolvere. :)

Se stai cercando il massimo dell'efficienza, Perl è un po 'troppo alto. :)