我正在学习“中级 Perl”,它非常酷。我刚刚完成了关于“施瓦兹变换”的部分,在它沉没之后,我开始想知道为什么变换不使用缓存。在具有多个重复值的列表中,转换会重新计算每个值的值,所以我想为什么不使用哈希来缓存结果。这是一些代码:
# a place to keep our results
my %cache;
# the transformation we are interested in
sub foo {
# expensive operations
}
# some data
my @unsorted_list = ....;
# sorting with the help of the cache
my @sorted_list = sort {
($cache{$a} //= &foo($a)) <=> ($cache{$b} //= &foo($b))
} @unsorted_list;
我错过了什么吗?为什么 Schwartzian 变换的缓存版本没有在书中列出并且通常只是更好地传播,因为乍一看我认为缓存版本应该更有效?
编辑 :daxim 在评论中指出这被称为 orcish maneuver .所以我并没有发疯,虽然我不太明白这个名字。
最佳答案
(许多其他评论已编辑)
在某种程度上,数组查找比哈希查找更有效(即 $a->[1]
比 $cache{$a}
快),规范形式可能比您的代码更有效,即使有很多重复。
基准测试结果:
这是我的基准测试代码:
# when does an additional layer of caching improve the performance of
# the Schwartzian transform?
# methods:
# 1. canonical Schwartzian transform
# 2. cached transform
# 3. canonical with memoized function
# inputs:
# 1. few duplicates (rand)
# 2. many duplicates (int(rand))
# functions:
# 1. fast
# 2. slow
use Benchmark;
use Math::BigInt;
use strict qw(vars subs);
use warnings;
no warnings 'uninitialized';
# fast_foo: a cheap operation, slow_foo: an expensive operation
sub fast_foo { my $x = shift; exp($x) }
sub slow_foo { my $x = shift; my $y = new Math::BigInt(int(exp($x))); $y->bfac() }
# XXX_memo_foo: put caching optimization inside call to 'foo'
my %fast_memo = ();
sub fast_memo_foo {
my $x = shift;
if (exists($fast_memo{$x})) {
return $fast_memo{$x};
} else {
return $fast_memo{$x} = fast_foo($x);
}
}
my %slow_memo = ();
sub slow_memo_foo {
my $x = shift;
if (exists($slow_memo{$x})) {
return $slow_memo{$x};
} else {
return $slow_memo{$x} = slow_foo($x);
}
}
my @functions = qw(fast_foo slow_foo fast_memo_foo slow_memo_foo);
my @input1 = map { 5 * rand } 1 .. 1000; # 1000 random floats with few duplicates
my @input2 = map { int } @input1; # 1000 random ints with many duplicates
sub canonical_ST {
my $func = shift @_;
my @sorted = map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, $func->($_)] } @_;
return;
}
sub cached_ST {
my $func = shift @_;
my %cache = ();
my @sorted = sort {
($cache{$a} //= $func->($a)) <=> ($cache{$b} //= $func->{$b})
} @_;
return;
}
foreach my $input ('few duplicates','many duplicates') {
my @input = $input eq 'few duplicates' ? @input1 : @input2;
foreach my $func (@functions) {
print "\nInput: $input\nFunction: $func\n-----------------\n";
Benchmark::cmpthese($func =~ /slow/ ? 30 : 1000,
{
'Canonical' => sub { canonical_ST($func, @input) },
'Cached' => sub { cached_ST($func, @input) }
});
}
}
和结果(草莓 Perl 5.12):
输入:很少重复
功能:fast_foo
-----------------
速率规范缓存
标准 160/s -- -18%
缓存 196/s 22% --
输入:很少重复
功能:slow_foo
-----------------
速率规范缓存
标准 7.41/s -- -0%
缓存 7.41/s 0% --
输入:很少重复
功能:fast_memo_foo
-----------------
速率规范缓存
标准 153/s -- -25%
缓存 204/s 33% --
输入:很少重复
功能:slow_memo_foo
-----------------
速率缓存规范
缓存 20.2/s -- -7%
标准 21.8/s 8% --
输入:许多重复
功能:fast_foo
-----------------
速率规范缓存
标准 179/s -- -50%
缓存 359/s 101% --
输入:许多重复
功能:slow_foo
-----------------
速率规范缓存
标准 11.8/s -- -62%
缓存 31.0/s 161% --
输入:许多重复
功能:fast_memo_foo
-----------------
速率规范缓存
标准 179/s -- -50%
缓存 360/s 101% --
输入:许多重复
功能:slow_memo_foo
-----------------
速率规范缓存
标准 28.2/s -- -9%
缓存 31.0/s 10% --
我对这些结果感到有些震惊——规范 Schwartzian 变换在最有利的条件下(昂贵的函数调用、很少重复或没有内存)只有轻微的优势,而在其他情况下则处于相当大的劣势。 OP 在
sort
中的缓存方案函数甚至优于内存之外 sort
.当我进行基准测试时,我并没有预料到这一点,但我认为 OP 正在发挥作用。
关于perl - 缓存施瓦兹变换,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4683669/