4

「Intermediate Perl」を試していますが、かなりクールです。「The Schwartzian Transform」のセクションを終えたところですが、それが沈んだ後、なぜ変換がキャッシュを使用しないのか疑問に思い始めました。いくつかの繰り返し値を持つリストでは、変換によってそれぞれの値が再計算されるため、結果をキャッシュするためにハッシュを使用しない理由を考えました。ここにいくつかのコードがあります：

# 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操作として知られているコメントで指摘しました。だから、名前はよくわからないけど、頭がおかしくなったわけじゃない。

4

2 に答える 2

5

(他の多くのコメントは編集されています)

配列ルックアップがハッシュ ルックアップよりも効率的である (つまり、$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) }
             });
  }
}

結果 (Strawberry Perl 5.12):

入力: 重複が少ない
関数: fast_foo
-----------------
           レート正規キャッシュ
正準 160/秒 -- -18%
キャッシュ 196/秒 22% --

入力: 重複が少ない
関数: slow_foo
-----------------
            レート正規キャッシュ
標準 7.41/秒 -- -0%
キャッシュ 7.41/秒 0% --

入力: 重複が少ない
関数: fast_memo_foo
-----------------
           レート正規キャッシュ
正準 153/秒 -- -25%
キャッシュ 204/秒 33% --

入力: 重複が少ない
関数: slow_memo_foo
-----------------
            レート キャッシュされたカノニカル
キャッシュ 20.2/秒 -- -7%
標準 21.8/秒 8% --

入力: 多くの重複
関数: fast_foo
-----------------
           レート正規キャッシュ
正準 179/秒 -- -50%
キャッシュされた 359/秒 101% --

入力: 多くの重複
関数: slow_foo
-----------------
            レート正規キャッシュ
標準 11.8/秒 -- -62%
キャッシュ 31.0/秒 161% --

入力: 多くの重複
関数: fast_memo_foo
-----------------
           レート正規キャッシュ
正準 179/秒 -- -50%
キャッシュされた 360/秒 101% --

入力: 多くの重複
関数: slow_memo_foo
-----------------
            レート正規キャッシュ
標準 28.2/秒 -- -9%
キャッシュ 31.0/秒 10% --

私はこれらの結果に少し驚いています. 標準シュワルツ変換は、最も好ましい条件 (高価な関数呼び出し、重複が少ない、またはメモ化なし) ではわずかな利点しかなく、他の場合にはかなり不利です. 関数内の OP のキャッシュ スキームは、sort外部のメモ化よりも優れていsortます。ベンチマークを行ったときはこれを期待していませんでしたが、OP は何かに取り組んでいると思います。

于 2011-01-13T18:36:27.043 に答える
2

foo()Schwartzian Transform のキャッシュは、複数の変換を呼び出す場合に役立ちます。

@sorted1 = map { $_->[0] }
           sort { $a->[1] cmp $b->[1] }
           map  { [$_, foo($_)] }
           @unsorted1;
@sorted2 = map { $_->[0] }
           sort { $a->[1] cmp $b->[1] }
           map  { [$_, foo($_)] }
           @unsorted2;

@unsorted1との値がほぼ同じである場合、同じ値を 2 回@unsorted2呼び出すことになります。foo()この関数の計算コストが高い場合は、おそらく結果をキャッシュする必要があります。

これを行う最も簡単な方法は、Memoizeモジュールを使用することです。

use Memoize;
memoize('foo');

この 2 行を追加すると、foo()自分でキャッシュを設定する必要がなくなり、自動的にMemoize処理されます。

編集:あなたの並べ替えがシュワルツ変換を行わないことに気付きました。ST の背後にある要点は、コストのかかる関数をリストのメンバーごとに 1 回だけ実行することです。これが、構造全体を実行する理由ですmap sort map。おそらくあなたが行ったように手書きのキャッシングを行うこともできますが、それは非標準のPerlになります(誰かがSTを見ることを期待し、そこに座ってコードが何であるかを理解しなければならないという意味で)している)、すぐにメンテナンスの悪夢になる可能性があります。

しかし、はい、リストに値が繰り返される場合、キャッシュを使用すると (ハンドロールまたは を使用してMemoize)、シュワルツ変換が高速になる可能性があります。私が「可能性がある」と言ったのは、実際には、ハッシュ ルックアップを実行する方が呼び出すよりもコストがかかる場合があるためですfoo()(Memoizeドキュメントsub foo { my $x = shift; return $x * $x }では、これらのインスタンスの 1 つの例として使用されています)。

于 2011-01-13T18:49:03.203 に答える