Kiedy są transformacje Schwartzian przydatne?

Question

Podczas przeglądania książki "Intermediate Perl" zauważyłem sekcję o Schwartzian Transforms i wypróbowałem przykład w ćwiczeniu (9.9.2), ale zauważyłem, że wiele przebiegów spowodowało, że transformacja zabiera więcej czasu niż zwykły sort. Kod tutaj dokonuje prostego sortowania plików w folderze Windows \ System32 na podstawie rozmiaru pliku -

#!/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\\*"; 
        }, 
      } 
     ); 

wyjście jest -

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) 

Moje zrozumienie, że od operacji pliku (-s) musi być powtarzany w kółko w przypadku testB, powinien działać znacznie wolniej niż testA. Wynik jednak odbiega od tej obserwacji. Czego tu mi brakuje?

Answer 1

Dla mnie wyjście wygląda nieco inaczej:

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 to z przyzwoitą wartość iteracji (wybrałem 100,000), otrzymuję to:

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) 

spojrzenie na Kod mówi mi, że te dwa subwoofery prawdopodobnie spędzają większość swojego czasu globowania pliki, więc zrobiłem to:

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; 
         }, 
       } 
     ); 

I zdobądź:

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) 

Coś tu pachnie, prawda?

Więc rzućmy okiem na docs:

perldoc -f rodzaj

W kontekście skalarnym, zachowanie "sort()" jest niezdefiniowany.

Aha! Więc spróbujmy jeszcze raz:

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; 
         }, 
       } 
     ); 

To daje mi:

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. Aby odpowiedzieć na twoje pytania: transformacja Schwartziana pomoże ci, gdy tylko użyjesz jej w znaczący sposób. Analiza porównawcza pokaże to, gdy będziesz porównywać wyniki w znaczący sposób.

Answer 2

Oprócz doskonałej odpowiedzi Manni, kolejnym czynnikiem, który należy wziąć pod uwagę, jest to, że w twoim przykładzie może zachodzić pewne buforowanie, np. na poziomie systemu plików.

Jeśli ten sam plik jest dostępny wiele razy, FS może wykonać buforowanie, powodując mniej drastyczne oszczędności czasu transformacji Schwartzian niż oczekiwano.

Answer 3

Wiem, że to technicznie już odpowiedziałem całkowicie, ale miałem kilka ważnych uwag bocznych.

Po pierwsze, zazwyczaj preferuję cmpthese() do timethese(), ponieważ mówi to, co jest lepsze w ludzkim czytelny i pouczający sposób, a nie tylko przedstawia czasy.

Po drugie, z powodu teoretycznych problemów, takich jak ten, zazwyczaj staram się unikać serwerów systemowych, gdy tylko jest to możliwe, ponieważ jądro może sprawić, że zaczekasz na zawsze, jeśli będzie to w nastroju - naprawdę nie jest to uczciwy test.

Thrid, Warto zauważyć, że transformacja jest zawsze droższa, jeśli lista jest już posortowana: Jeśli ustawisz $ point_of_interest = 2, transformacja wygra; ale jeśli ustawisz $ point_of_interest = 1, sortowanie zwykłe wygra. Uważam, że wynik jest dość interesujący i wart wspomnienia.

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

do dokładnego zbadania tej sprawy, zobacz moje Perlmonks słupek "Wasting Time Thinking about Wasted Time". Rozszerzam także o to w rozdziale "Benchmarking" w Mastering Perl. Jak już zauważyli inni, problemem jest kod testowy, a nie transformacja. To jest błąd w Intermediate Perl.

Jednak, aby odpowiedzieć na twoje pytanie, transformacja z kluczem w pamięci podręcznej jest przydatna, gdy obliczanie klucza sortowania jest kosztowne i trzeba je obliczać wiele razy. Istnieje kompromis pomiędzy dodatkową pracą polegającą na buforowaniu klucza sortowania i cyklami, które robisz, oszczędzając. Zwykle im więcej elementów trzeba sortować, tym lepiej będzie działać transformacja z kluczem w pamięci podręcznej.