Quando sono utili le Trasformazioni di Schwartz?

Question

Mentre passavo attraverso il libro "Intermediate Perl", ho notato una sezione su Schwartzian Transforms e ho provato l'esempio nell'esercizio (9.9.2), ma ho notato che più esecuzioni hanno portato la trasformazione a impiegare più tempo del normale. Il codice qui esegue una semplice sorta di file nella cartella Windows \ system32 dipende dalla sua dimensione -

#!/usr/bin/perl 
use strict; 
use warnings; 

use Benchmark; 

my $time = timethese(10, { 
      testA => sub { map $_->[0],  
         sort {$a->[1] <=> $b->[1]} 
         map [$_, -s $_], 
         glob "C:\\Windows\\System32\\*"; 
        }, 
      testB => sub { sort { -s $a <=> -s $b } glob "C:\\Windows\\System32\\*"; 
        }, 
      } 
     ); 

L'uscita è -

Benchmark: timing 10 iterations of testA, testB... 
    testA: 11 wallclock secs (1.89 usr + 8.38 sys = 10.27 CPU) @ 0.97/s (n=10) 
    testB: 5 wallclock secs (0.89 usr + 4.11 sys = 5.00 CPU) @ 2.00/s (n=10) 

La mia comprensione è che, poiché l'operazione di file (-s) deve essere ripetuto più volte nel caso di testB dovrebbe funzionare molto più lentamente di testA. L'output però si discosta da quell'osservazione. Cosa mi manca qui?

Answer 1

Per me, l'uscita sembra un po 'diversa:

testA: 1 wallclock secs (0.16 usr + 0.11 sys = 0.27 CPU) @ 37.04/s (n=10) 
     (warning: too few iterations for a reliable count) 
testB: 0 wallclock secs (0.09 usr + 0.02 sys = 0.11 CPU) @ 90.91/s (n=10) 
     (warning: too few iterations for a reliable count) 

Benchmarking questo con un discreto rapporto di iterazioni (io ho scelto 100.000), ottengo questo:

testA: 23 wallclock secs (12.15 usr + 10.05 sys = 22.20 CPU) @ 4504.50/s (n=100000) 
testB: 11 wallclock secs (6.02 usr + 5.57 sys = 11.59 CPU) @ 8628.13/s (n=100000) 

Uno sguardo al il codice mi dice che quei due sub probabilmente passano la maggior parte del loro tempo globbing dei file, così ho fatto questo:

my @files = glob "C:\\Windows\\System32\\*"; 
my $time = timethese(1_000_000, { 
       testA => sub { 
           map $_->[0], 
            sort {$a->[1] <=> $b->[1]} 
             map [$_, -s $_], 
              @files; 
         }, 
       testB => sub { 
          sort { -s $a <=> -s $b } @files; 
         }, 
       } 
     ); 

E ottenere:

testA: 103 wallclock secs (56.93 usr + 45.61 sys = 102.54 CPU) @ 9752.29/s (n=1000000) 
testB: -1 wallclock secs (0.12 usr + 0.00 sys = 0.12 CPU) @ 8333333.33/s (n=1000000) 
     (warning: too few iterations for a reliable count) 

Qualcosa puzza di pesce qui, non è vero?

Quindi, diamo uno sguardo ai documenti:

perldoc -f sorta

In un contesto scalare, il comportamento di "sort()" non è definito.

Aha! Così proviamo di nuovo:

testA: 12 wallclock secs (7.44 usr + 4.55 sys = 11.99 CPU) @ 8340.28/s (n=100000) 
testB: 34 wallclock secs (6.44 usr + 28.30 sys = 34.74 CPU) @ 2878.53/s (n=100000) 

So.:

my @files = glob "C:\\Windows\\System32\\*"; 
my $time = timethese(100_000, { 
       testA => sub { 
           my @arr= map $_->[0], 
            sort {$a->[1] <=> $b->[1]} 
             map [$_, -s $_], 
              @files; 
         }, 
       testB => sub { 
          my @arr = sort { -s $a <=> -s $b } @files; 
         }, 
       } 
     ); 

Questo mi dà Per rispondere alle tue domande: una trasformazione di Schwartz ti aiuterà ogni volta che la usi in modo significativo. Il benchmarking mostrerà questo quando si valuta in modo significativo.

Answer 2

A prescindere dall'eccellente risposta di Manni, un altro fattore da considerare è che nel tuo esempio potrebbe esserci del caching, ad es. a livello di file system.

Se si accede allo stesso file più volte, la FS potrebbe eseguire alcune operazioni di memorizzazione nella cache con conseguente risparmio di tempo meno drastico della trasformazione di Schwartzian del previsto.

Answer 3

So che questo è già tecnicamente già risposto piuttosto completamente, ma ho avuto un paio di note collaterali pertinenti.

In primo luogo, di solito preferisco cmpthese() a timethese() perché ti dice quale è meglio in un modo umano leggibile e informativo invece di presentare solo i tempi.

In secondo luogo, per problemi teorici come questo, di solito cerco di evitare syscalls interamente dove possibile, dal momento che il kernel può farti aspettare per sempre se è nell'umore di farlo - non è proprio un test equo.

Thrid, È interessante notare che la trasformazione è sempre più costosa se la lista è già ordinata: Se si imposta $ point_of_interest = 2, la trasformazione vince; ma se imposti $ point_of_interest = 1, l'ordinamento normale vincerà. Trovo che il risultato sia abbastanza interessante e degno di nota.

use strict; 
use Benchmark qw(cmpthese); 

my $point_of_interest = 2; 
my @f = (1 .. 10_000) x $point_of_interest; 
my @b; 

cmpthese(500, { 
    transform => sub { 
     @b = 
     map {$_->[0]} 
     sort {$a->[1] <=> $b->[1]} 
     map {[$_, expensive($_)]} 
     @f 
    }, 
    vanilla => sub { @b = sort { expensive($a) <=> expensive($b) } @f }, 
}); 

sub expensive { 
    my $arg = shift; 

    $arg .= "_3272"; 
    $arg += length "$arg"; 
    $arg = $arg ** 17; 
    $arg = sqrt($arg); 

    $arg; 
} 

Answer 4

Per un esame approfondito di questo caso, vedere il mio Perlmonks posta "Wasting Time Thinking about Wasted Time". Espanderò anche questo nel capitolo "Benchmarking" in Mastering Perl. Come altri hanno già notato, è il codice di benchmark che è il problema, non la trasformazione. È un errore in Intermediate Perl.

Tuttavia, per rispondere alla tua domanda, una trasformazione in chiave memorizzata è utile quando il calcolo della chiave di ordinamento è costoso e dovrai calcolarlo molte volte. C'è un compromesso tra il lavoro extra per mettere in cache la chiave di ordinamento e i cicli che si salvano facendolo. In genere, più elementi è necessario ordinare, migliore sarà la trasformazione della chiave memorizzata nella cache.