Schwartzian Transforms什么时候有用？

Question

在阅读" 中级Perl "一书的过程中,我注意到了Schwartzian变换的一个部分,并在练习中尝试了这个例子(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运行慢很多.输出虽然偏离了这一观察结果.我在这里错过了什么？

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()"的行为是未定义的.

啊哈!那么让我们再试一次:

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)

所以.回答您的问题:Schwartzian变换将在您以有意义的方式使用它时为您提供帮助.当您以有意义的方式进行基准测试时,基准测试将显示此信息.

Answer 2

有关此案例的彻底检查，请参阅我的Perlmonks帖子“浪费时间思考浪费时间”。我还在Mastering Perl的“基准测试”一章中对此进行了扩展。正如其他人已经指出的那样，问题在于基准测试代码，而不是转换。这是中级 Perl中的一个错误。

但是，为了回答您的问题，当排序键计算成本很高并且您必须多次计算时，缓存键转换非常有用。缓存排序键的额外工作和节省的周期之间需要权衡。通常，必须排序的元素越多，缓存键转换的执行效果就越好。

更新我还写了《施瓦茨变换的历史》，并提出了《施瓦茨变换的令人惊讶的紧张历史》。

Answer 3

除了Manni的优秀答案之外,另一个要考虑的因素是您的示例中可能会进行一些缓存,例如在文件系统级别.

如果多次访问同一文件,则FS可能会执行一些缓存,从而导致Schwartzian变换的时间节省不如预期.