sort時にキャッシュを仕込んで効率化する

PBP

最近はPerl Best Practiceを読んでいることが多いので、おもしろかった部分をまとめて書いておこうかと思う。ということで、本日はPerl Best Practice 8.1章 ソートからのネタ。

sortはブロックを渡すことでソート方法を柔軟にコントロールできる。ただ、そのブロック内での計算量が大きくなるとソートの効率が落ちる。ソート中に何度も比較を行うちに同じ計算を何度もすることになってしまうからだ。

そこで、いろいろな工夫が考えられているらしい。PBPで紹介されていたもを以下にまとめてみた。

工夫なしでそのまま

まず、一番ベタなソートが、以下のコード。

use Digest::SHA1 qw(sha1);
my @sorted_titles = sort { sha1($a) cmp sha1($b) } @titles;

このままだと、何度も同じ値のダイジェストを計算することになってしまって効率が悪い。

Orcish Maneuver

そこで、計算結果をハッシュにキャッシュして使う。Orcish Maneuverというアルゴリズムでは、キャッシュに値がすでに格納されていればそれを利用し、格納されていないときにだけ、計算を行う。

my %sha1_of;
my @sorted_titles
    = sort {
        ($sha1_of{$a} ||= sha1($a))
        cmp
        ($sha1_of{$b} ||= sha1($b))
    } @titles;

シュワルツ変換

ほかにも、シュワルツ変換というアルゴリズムがある。ソートに使う値と、実際にソートする値の組を事前に作ってソートして、そのあと組をもとの値のリストに戻す。

my @sorted_titles
    = map  { $_->[0] }
      sort { $a->[1] cmp $b->[1] }
      map  { [$_, sha1($_)] }
           @titles;

キャッシュを準備しておく

そもそも、事前にキャッシュを準備しておくこともできる。ソートが途中でとまれば、事前の計算の一部が無駄になるかも。ただし、わかりやすい。

my %sha1_of;
   @sha1_of{@titles} = map { sha1($_) } @titles;
my @sorted_titles
    = sort { $sha1_of{$a} cmp $sha1_of{$b} } @titles;

use Memoize;

Orcish Maneuverやシュワルツ変換だと、キャッシュ用のコードが目立ちすぎて、本来やろうとしている処理内容がわかりにくくなってしまう。そこで、Memoizeを使うと、サブルーチンにキャッシュ機能をもたせることができて、しかもコードがわかりやすいままにできる。

use Memoize;
memoize('sha1');
my @sorted_titles
    = sort { sha1($a) cmp sha1($b) } @titles;

ベンチマークしてみる

せっかくなので、これら各ソートの性能をベンチマークしてみた。はてなブックマーク - 人気エントリーのRSSからタイトルをとりだしてDigest::SHA1でダイジェストを計算し、その値でソートした。うちの環境では、結果は以下のようになった。

Benchmark: timing 10000 iterations of Orcish Maneuver, Prepared, Schwartzian Transform, Standard...
Orcish Maneuver: 14 wallclock secs (11.85 usr +  0.26 sys = 12.11 CPU) @ 825.76/s (n=10000)
  Prepared: 16 wallclock secs (13.58 usr +  0.28 sys = 13.86 CPU) @ 721.50/s (n=10000)
Schwartzian Transform: 14 wallclock secs (11.70 usr +  0.25 sys = 11.95 CPU) @ 836.82/s (n=10000)
  Standard: 31 wallclock secs (25.52 usr +  0.45 sys = 25.97 CPU) @ 385.06/s (n=10000)
Benchmark: timing 10000 iterations of Memoize...
   Memoize: 218 wallclock secs (153.54 usr +  3.50 sys = 157.04 CPU) @ 63.68/s (n=10000)

Memoizeは少し特殊だったので同時に計測せずにわけてやってる。Standardというのがキャッシングをせずにそのままソートした結果だ。どのアルゴリズムも、Standardの半分の時間でソートされていることがわかる。

ただ、なんかMemoizeの結果がおかしくて、普通にソートするよりも何倍も時間がかかってる。やり方がわるいのかなー？

ベンチマークに使ったコードは最後につけた。

まとめ

そういえば、Memoizeは前にPythonでやっていた。はこべにっき# - Pythonでもわりとたらい回せそう？あたり。もとねたは404 Blog Not Found:たらいを回すならHaskell。

これはsortにかぎらず、コストの高い関数はどんな場所でよばれるかをきちん把握しといた方がよさそうだな。

#!/usr/bin/env perl
use strict;
use warnings;
use Encode;
use XML::Feed;
use URI;
use YAML;
use Digest::SHA1 qw( sha1 );
use Benchmark;


my $feed_file = shift;

my $feed = XML::Feed->parse($feed_file);
our @titles = map { encode_utf8($_->title) } $feed->entries;

sub sort_standard {
    my @sorted_titles
        = sort { sha1($a) cmp sha1($b) } @titles;
}

sub sort_prepared {
    my %sha1_of;
       @sha1_of{@titles} = map { sha1($_) } @titles;
    my @sorted_titles
        = sort { $sha1_of{$a} cmp $sha1_of{$b} } @titles;
}

sub sort_by_orcish_maneuver {
    my %sha1_of;

    my @sorted_titles
        = sort {
            ($sha1_of{$a} ||= sha1($a))
            cmp
            ($sha1_of{$b} ||= sha1($b))
        } @titles;
}

sub sort_by_schwartzian_transform {
    my @sorted_titles
        = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, sha1($_)] }
               @titles;
}

Benchmark::timethese(10000, {
    'Standard'              => \&sort_standard,
    'Orcish Maneuver'       => \&sort_by_orcish_maneuver,
    'Schwartzian Transform' => \&sort_by_schwartzian_transform,
    'Prepared'              => \&sort_prepared,
});

use Memoize;
memoize('sha1');

Benchmark::timethese(10000, {
    'Memoize'              => \&sort_standard,
});