施瓦茨变换什么时候有用？

Question

在浏览“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 慢很多。 但输出与观察结果有所偏差。 我在这里缺少什么？

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)

所以。 回答您的问题：只要您以有意义的方式使用施瓦茨变换，它就会为您提供帮助。 当您以有意义的方式进行基准测试时，基准测试将显示这一点。

Answer 2

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

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

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

Answer 3

除了 Manni 的出色回答之外，另一个需要考虑的因素是您的示例中可能会进行一些缓存，例如在文件系统级别。

如果多次访问同一个文件，FS 可能会进行一些缓存，从而导致 Schwartzian 变换节省的时间比预期的要少。

Answer 4

我知道这在技术上已经得到了相当完整的回答，但我有一些相关的旁注。

首先，我通常更喜欢 cmpthese() 而不是 timethese()，因为它以人类可读和信息丰富的方式告诉您哪个更好，而不仅仅是呈现时间。

其次，对于像这样的理论问题，我通常会尽可能避免系统调用，因为如果内核愿意的话，它会让你永远等待——这并不是一个公平的测试。

第三，有趣的是，如果列表已经排序，则转换总是更昂贵：如果设置 $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;
}