9

「Intermediate Perl」の本を読んでいるときに、Schwartzian Transforms のセクションに気付き、演習 (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)

私の理解では、ファイル操作 (-s) は testB の場合に何度も繰り返す必要があるため、testA よりもはるかに遅く実行する必要があります。ただし、出力はその観察から逸脱しています。ここで何が欠けていますか？

4

4 に答える 4

15

私にとって、出力は少し異なって見えます：

 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)

コードを見ると、これら2つの潜水艦はおそらくほとんどの時間をファイルのグロブに費やしていることがわかります。そのため、私はこれを行いました。

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（）」の動作は定義されていません。

あはは！では、もう一度試してみましょう。

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)

それで。質問に答えるには：シュワルツ変換は、意味のある方法で使用する場合はいつでも役立ちます。ベンチマークは、意味のある方法でベンチマークを行うときにこれを示します。

于 2009-02-27T11:15:45.180 に答える
4

このケースの徹底的な調査については、私のPerlmonksの投稿「Wasting Time Thinking about Wasted Time」を参照してください。それについては、 Mastering Perlの「ベンチマーク」の章でも詳しく説明しています。他の人がすでに指摘しているように、問題は変換ではなく、ベンチマーク コードです。Intermediate Perlの間違いです。

ただし、あなたの質問に答えるために、キャッシュされたキー変換は、ソートキーの計算が高価で、何度も計算する必要がある場合に役立ちます。ソートキーをキャッシュするための余分な作業と、それを実行して節約するサイクルとの間にはトレードオフがあります。通常、並べ替える必要のある要素が多いほど、キャッシュされたキーの変換のパフォーマンスが向上します。

于 2009-02-27T19:57:39.230 に答える
3

私はこれが技術的にはすでにかなり完全に答えられていることを知っていますが、私はいくつかの関連するサイドノートを持っていました。

まず、私は通常、timethese（）よりもcmpthese（）を好みます。これは、時間を表示するだけでなく、人間が読みやすく有益な方法でどちらが優れているかを示すためです。

第二に、このような理論上の問題については、カーネルがそうする気になっている場合、カーネルはあなたを永遠に待たせることができるので、私は通常、可能な限りシステムコールを完全に避けようとします-実際には公正なテストではありません。

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;
}
于 2009-02-27T15:59:37.633 に答える