¿Cuándo son útiles las transformaciones de Schwartz?

Question

Mientras repasaba el libro "Intermediate Perl", noté una sección sobre Transformaciones de Schwartz y probé el ejemplo en el ejercicio (9.9.2), pero me di cuenta de que varias ejecuciones daban como resultado que la transformación tomara más tiempo que el tipo normal. El código aquí realiza una especie simple de los archivos en el directorio windows \ system32 basa en el tamaño del archivo -

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

La salida es -

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) 

Mi entendimiento es que ya que la operación de archivo (-s) debe repetirse una y otra vez en el caso de testB, debe ejecutarse mucho más lento que testA. El resultado, sin embargo, se desvía de esa observación. ¿Que me estoy perdiendo aqui?

Answer 1

Para mí, la salida se ve un poco diferente:

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) 

Evaluación comparativa de esto con un valor digno de iteraciones (elegí 100.000), me sale esto:

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) 

Una mirada a la El código me dice que esos dos subs probablemente pasen la mayor parte de su tiempo comprimiendo los archivos, así que hice esto:

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

Y obtenga:

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) 

Algo huele a pescado aquí, ¿no?

lo tanto, vamos a echar un vistazo a los documentos:

perldoc -F tipo

En contexto escalar, el comportamiento de "sort()" no está definido.

Aha! Así que vamos a intentarlo de nuevo:

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

Esto me da Para responder a sus preguntas: una transformación Schwartzian lo ayudará siempre que lo use de una manera significativa. La evaluación comparativa mostrará esto cuando comparta de una manera significativa.

Answer 2

Aparte de la excelente respuesta de Manni, otro factor a tener en cuenta es que algo de caché puede estar sucediendo en su ejemplo, p. en el nivel del sistema de archivos.

Si se accede al mismo archivo varias veces, el FS puede hacer algo de almacenamiento en caché, lo que resulta en un ahorro de tiempo menos drástico que el esperado de la Transformada Schwartzian.

Answer 3

Sé que técnicamente ya se ha respondido completamente, pero tenía un par de notas secundarias relevantes.

En primer lugar, prefiero cmpthese() a timethese() porque te dice cuál es mejor de una manera legible e informativa para los humanos en lugar de simplemente presentar los tiempos.

En segundo lugar, para problemas teóricos como este, por lo general trato de evitar las llamadas de sistema cuando sea posible, ya que el kernel puede hacerte esperar para siempre si está de humor para hacerlo, realmente no es una prueba justa.

Thrid, es interesante observar que la transformación siempre es más cara si la lista ya está ordenada: si configura $ point_of_interest = 2, la transformación gana; pero si establece $ point_of_interest = 1, ganará el tipo regular. Me parece que el resultado es bastante interesante y vale la pena mencionarlo.

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

Para un examen detallado de este caso, véase mi Perlmonks posterior "Wasting Time Thinking about Wasted Time". También amplío eso en el capítulo "Benchmarking" en Mastering Perl. Como otros ya han notado, el problema es el código de evaluación comparativa, no la transformación. Es un error en Intermediate Perl.

Sin embargo, para responder a su pregunta, una transformación de clave en caché es útil cuando el cálculo de la clave de clasificación es costoso y tendría que calcularlo muchas veces. Hay una compensación entre el trabajo adicional para almacenar en caché la clave de clasificación y los ciclos que ahorras al hacerlo. Normalmente, cuantos más elementos tenga que ordenar mejor será la transformación de la clave en caché.