Когда полезны преобразования Шварца?

Question

Просматривая книгу " Intermediate Perl ", я заметил раздел о преобразованиях Шварца и попробовал пример в упражнении (9.9.2), но заметил, что несколько прогонов привели к тому, что преобразование заняло больше времени, чем нормальный вид. Код здесь выполняет простую сортировку файлов в каталоге windows \ system32 в зависимости от размера файла -

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

Выход -

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)

Насколько я понимаю, поскольку файловая операция (-ы) должна повторяться снова и снова в случае testB, она должна выполняться намного медленнее, чем testA. Вывод, однако, отклоняется от этого наблюдения. Что мне здесь не хватает?

Answer 1

Для меня вывод выглядит немного иначе:

 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)

Сравнивая это с приличным значением итераций (я выбрал 100 000), я получаю это:

 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)

Взгляд на код говорит мне, что эти две субмарины, вероятно, проводят большую часть своего времени, копаясь в файлах, поэтому я сделал это:

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

и получите:

 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)

Что-то пахнет здесь, не так ли?

Итак, давайте посмотрим на документы:

perldoc -f sort

В скалярном контексте поведение "sort ()" не определено.

Aha! Итак, давайте попробуем еще раз:

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

Это дает мне:

 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)

Итак. Чтобы ответить на ваши вопросы: преобразование Шварца поможет вам всякий раз, когда вы используете его осмысленно. Бенчмаркинг покажет это, когда вы сравните результаты значительным образом.

Answer 2

Помимо превосходного ответа Манни, еще одним фактором, который следует учитывать, является то, что в вашем примере может происходить некоторое кеширование, например на уровне файловой системы.

Если к одному и тому же файлу обращаются несколько раз, FS может выполнить некоторое кэширование, что приведет к меньшей экономии времени преобразования Шварца, чем ожидалось.

Answer 3

Подробное рассмотрение этого случая см. В моем Perlmonks посте "Потеря времени, думая о потраченном времени" . Я также подробно остановлюсь на этом в «Бенчмаркинге» глава Освоение Perl . Как уже отмечали другие, проблема заключается в коде тестирования, а не в преобразовании. Это ошибка в Промежуточном Perl .

Однако, чтобы ответить на ваш вопрос, преобразование с кэшированным ключом полезно, когда вычисление ключа сортировки стоит дорого, и вам придется вычислять его много раз. Существует компромисс между дополнительной работой по кешированию ключа сортировки и циклами, которые вы сохраняете, делая это. Как правило, чем больше элементов нужно отсортировать, тем лучше будет работать преобразование кэшированного ключа.

Answer 4

Я знаю, что на это технически уже достаточно полные ответы, но у меня было несколько важных замечаний.

Во-первых, я обычно предпочитаю cmpthese (), а не timethese (), потому что он говорит вам, что лучше для человека читать и информативно, а не просто представлять времена.

Во-вторых, для теоретических проблем, подобных этой, я обычно стараюсь избегать системных вызовов полностью, где это возможно, поскольку ядро ​​может заставить вас ждать вечно, если у него есть такое желание - не совсем честный тест.

Thrid, Интересно отметить, что преобразование всегда дороже, если список уже отсортирован: если вы установите $ point_of_interest = 2, преобразование выиграет; но если вы установите $ point_of_interest = 1, победит обычная сортировка. Я нахожу этот результат довольно интересным и заслуживающим упоминания.

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