後藤謙太郎 <URL://http://www.notwork.org/~gotoken/mag/cmagazine/>
註: この文書は『C MAGAZINE』2001年3月号に掲載された記事の元となるものに手を加えたものです．
記事中のプログラムを一つずつファイルにしたものもあります(→list)
間違いを見つけたら，gotoken@notwork.org宛に御連絡くださると喜びます。
Copyright(c) 2001 by GOTO Kentaro. All rights reserved.
インタプリタは遅いけど, いつでも通用する鉄則 (その高速化は本当に必要か?, アルゴリズムを見直す, いらないことはしない, 時間のかかっているところを探す, 組み込みの機能を使う, 余分なオブジェクトを作らない), いつでも通用する小技 (Benchmarkを仕入れておこう, 破壊的メソッドがあれば使う, ブロック変数は初期化しておく, call より yield, 配列の最初の要素の取り出し, 小技に関するまとめ), ケーススタディ: アナグラム探し お祭りの幕開け, Benchmark合戦開始, 組み込み機能の利用, アルゴリズムの改良, さらに大胆に, 祭りのおわり, ruby-talk へのお誘い), 参考資料, コラム ビッグオー記法
Rubyはインタプリタとして実現されています。これはある意味必然的なもので、 Rubyのようにevalを持っていたり、メソッドが実行時に決まったり、結果の型 (クラス)もやはり実行時に決まるようなオブジェクト指向言語には避けられないことなわけですが、インタプリタであることは決して悪いことばかりではありません。といってもソフトウェア工学的な部分はさておき、ここでは少し昔話をさせてもらいます。
筆者が最初に触れたプログラミング言語は1980年代の中ごろ、そのころ国産機といわれていたNECのPC-9801に標準でついてきたN88-BASICです(その前にインテルの8085のアセンブリを手でアセンブルしたり紙の上でLispの勉強をしたりしてましたが、アセンブリは言語というにはアレだし実際にLispを触ったのはもうちょっとあとなのでこの際おいておきます)。そのころは主に『サイエンス』誌(Scientific American 誌の翻訳がベース)にあったデュードニーさんの連載『コンピュータ・レクレーション』で遊びながらプログラミングをかじっていました。
今ではBSDやLinuxあるいはWindows 2000といった、ちゃんとしたOSを誰でも入手できるし言語処理系も選び放題なので、もうBASICには最初に学ぶメリットをまったく感じられなくなりましたが、それでも当時のパソコン環境はプログラミングという愉快な世界の入口としてはなかなか良かったと思います。ゲームで遊びたければ本や雑誌からBASICや16進ダンプで書かれたプログラムリストを打ち込んで実行するといったことは全然珍しいことではありませんでした。もっともパソコンを所有すること自体が珍しいことだったわけですが。おかげで当時はパソコンユーザなら「書いたことだけが実行される」という当たり前のことを誰でも知っていました。またN88-BASICは今でいえばデバッガのような環境でして、実行環境でありエディタでありモニタ環境でした。8086の派生であるV30などのCPU には保護機構もなかったので必要があれば実行中や実行後に実メモリの内容を直接見ることもできました。おかげで実行時にBASICインタプリタが何をやっているかを知ることもできたわけです。計算機を非常に生々しく感じられた時代だったといえるでしょう。
筆者がインタプリタの好きなところのBASICとRubyの共通点は、修正から再実行までのサイクルがとても短いことです。これは二つの意味でうれしいことだと思います。ひとつは、アイデアを実現するのに自分の頭の中のスタックを消費しない点です。つまり思ったことをすぐに書き留め試すことができます。筆者のようにスタックサイズの小さな人間には大変助かります。もう一つのメリットはライブラリや言語の機能の確認を早く行なえることです。例えば、String
のマニュアルを見ると scan メソッドの項目にはこう書かれています:
--
scan(re) {...}
reで与えられる正規表現を文字列に対して繰り返しマッチを行
い，正規表現中の括弧で括られた部分にマッチした文字列を配
列として返します．正規表現が括弧を含まない場合はマッチした
部分文字列の配列を返します．ブロックを指定して呼び出された
時には，括弧で括られた部分にマッチする部分文字列(括弧を含
まない場合はマッチ全体)をブロックのパラメータとします．
--
どれどれ早速試してみましょう。こんな時はワンライナで十分ですね。Fig1がその様子です。ふむふむ、確かに書いてある通りですね。
-- Fig1 String#scan を使ってみた
$ ruby -e '"00,02,18".scan(/\d+/){|i| p i}'
"00"
"02"
"18"
$ ruby -e '"00,02,18".scan(/(\d+)(,)?/){|i| p i}'
["00", ","]
["02", ","]
["18", nil]
こんな風に思ったことを試して挙動を把握することが素早く行なえるのは日常的に喜ばしいことのひとつです。腰を据えて助田さんのRubyUnitを使った単体テストでテストファーストすることも悪くはありませんが、この小気味よさも抜きには語れません。そして Ruby がもっと嬉しいのは、それなりに大きなプログラムも同じ言語で書けるという点です。また stat のようなシステムコールも手軽に呼び出せるので快適ですね。BASICの生々しさを思い出させますね。しかも昔よりずっとスマートです。
しかし、いいことばっかりも言ってはいられません。インタプリタのもつ短所として遅いということがしばしば挙げられます。動的なRubyがCなんかとくらべて遅いのはある意味仕方のないことだし、それを補って余りある楽しさを提供してくれるので別に構わない気もしますが、ちょっとした工夫で高速化できる場合があるのは知っておいた方がよいでしょう。そこで今回はRubyのプログラムを速くするためのコツを紹介します。その後でそれらが実際に試された実例を報告しましょう。
おそらく皆さんが楽しみにしているであろうRubyのtipsというか小技はあと回しにして、まずはどんな時でも通用するような大原則から述べていきます。まわりくどいと思われるかも知れませんが小技はしょせん小技、鉄則を知った上で使うべきなのです。
はじめてみれば分かりますがどんなものであれ高速化を狙った調整はとても楽しいものです。しかし、手間ヒマかけて高速化する必要が本当にあるかどうかは、あらかじめ考えておきましょう。そのコードをそう何度も使わないとか、実行時間が非常に短いなどの理由で別にちょっとくらい遅くてもいい場合はそのまま放っておくべきです。苦労に見合いません。また、高速化に伴ってコードに手を加えていくと読みにくくなるかも知れません。高速化が必要なコードは、たいていの場合長期に渡って使うことを予定しているのでしょうから、メンテナンスコストが上がらないようにたびたび読みやすさを考慮することも必要です。
まず可能ならアルゴリズムを改良しましょう。小手先の改良はそのあとです。とはいうもののなかなか難しいんですが。問題のサイズが可変の場合はとくにコストのオーダーに気をつけたいものです。問題のサイズに対するオーダーはビッグオー記法と呼ばれる書き方で表されます(コラム ビッグオー記法 参照)。
アルゴリズムの解析法についてはこの紙面では紹介しきれませんの参考文献をいくつか挙げておきますね。まず、アルゴリズムの勉強をしたことがなければ、『アルゴリズム』[Sed88]のような教科書で一度勉強されることをお薦めします。アルゴリズムの教科書はたくさんあるので購入する場合はWebなどで評判を調べてから買うのが良いと思います。また『C言語による最新アルゴリズム事典』[Oku91]のような便覧には効率が良いことが分かっているアルゴリズムもたくさん載っているので、ときどきめくってどの問題がどんな名前で呼ばれているかを知ることができます。
実践的な議論や効果的な事例が近ごろ改訂版の邦訳も出版された名著『珠玉のプログラミング』[Ben99]で取り上げられています。同時期に出版された『プログラミング作法』[KP99]も良いでしょう。これを機に本格的に勉強したい人には『The art of computer programming』[Knu78]や『ア ルゴリズムイントロダクション』[CLR90]のような定番の教科書がお薦めです。ちなみに筆者の場合は学部でAho-Hopcroft-Ullman[AHU83]と Mannaの教科書[Man74]とで学んだのが最初ですが、動的計画法などに関する高度な話題も含んでいる後者は残念ながら大学の図書館などにいかない限り現在では入手が困難です。
当たり前なんだけど、しなくていいことをしたら遅くなります。あからさまに要らない処理を書く人はいないと思いますが、紆余曲折を経た結果、ある部分が要らなくなってることはときどきああるものです。落ち着いたら一度点検してみてはどうでしょうか。
アルゴリズムの改良が終り、要らない処理も削った後は細かな工夫をするフェイズに入りましょう。工夫するには工夫すべきところを探すのが先決ですが時間のかかっているところを探すにはプロファイラを使うのが常套です。Ruby にも標準で profile.rb というプロファイラが添付されています。このライブラリは実行前に require することで使えます。典型的には、プログラムファイル foo.rb のプロファイルをとりたければ、次のように実行します。
$ ruby -r profile foo.rb
例としてRubyのソースについてくる sample/sieve.rb のプロファイルをとってみました(Fig2)。このプログラムはエラトステネスのふるいを使って素数を捜し出し、出力するものです。プロファイルの結果は本来の出力のあとに付加されます。profile.rbの行なうのは、メソッドが呼び出されたときに開始時刻をスタックに積み、メソッドから返ってきたときにスタックから下ろして引き算をすることでコストを計算するということです。ここでメソッドから入ってから出るまでの全体時間と、全体時間からそのメソッドのなかで呼ばれた別のメソッド呼び出しで費やした時間を差し引いた正味時間の二つの時間が計算されます。そして、最後に統計を出力します。出力される結果の項目は左から順に、次の7項目となります。
-- Fig2 sample/sieve.rb のプロファイル
$ ruby -r profile sample/sieve.rb 1000
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 (…以下略)
% cumulative self self total
time seconds seconds calls ms/call ms/call name
33.87 1.49 1.49 11 135.65 214.49 Fixnum#step
31.38 2.88 1.38 2410 0.57 0.57 Array#[]=
27.84 4.10 1.23 2 613.28 2070.31 Range#each
4.26 4.29 0.19 1 187.50 234.38 Array#join
1.06 4.34 0.05 168 0.28 0.28 Fixnum#to_s
0.35 4.35 0.02 31 0.50 0.50 Fixnum#+
0.35 4.37 0.02 30 0.52 0.52 Array#[]
0.18 4.38 0.01 31 0.25 0.25 Fixnum#<
0.18 4.38 0.01 1 7.81 7.81 Math.sqrt
0.18 4.39 0.01 1 7.81 7.81 Array#compact
0.00 4.39 0.00 1 0.00 0.00 Kernel.Integer
0.00 4.39 0.00 2 0.00 0.00 IO#write
0.00 4.39 0.00 1 0.00 0.00 Float#<=>
0.00 4.39 0.00 1 0.00 0.00 Array#shift
0.00 4.39 0.00 1 0.00 0.00 Float#coerce
0.00 4.39 0.00 1 0.00 0.00 Float#to_i
0.00 4.39 0.00 1 0.00 0.00 Fixnum#<=>
0.00 4.39 0.00 1 0.00 0.00 Kernel.puts
0.00 4.39 0.00 1 0.00 0.00 Array#clone
0.00 4.39 0.00 11 0.00 0.00 Fixnum#*
0.00 4.39 0.00 1 0.00 4406.25 #toplevel
ちなみに profile.rb は set_trace_func を用いて実現されています。この組み込み関数はインタプリタでメソッド呼び出しのようなイベントが発生したときに、実行されるProcオブジェクトを与えるものです。Rubyに標準でついてくるデバッガ(debug.rb)でも使われています。またAWKに由来する構文
BEGINとENDのうちENDを使うことで実行の最後にプロファイルを出力するということを実現しています。あっけないほど簡単なプログラムなので是非ソースを見てください。
時間のかかっている処理をRubyが組み込みのメソッドとして持っている機能で置き換えることは効果的です。こういう機能はないかな、と疑問に思ったらマニュアルを探してみましょう。案外あったりするものです。
高速化とは関係ない話ですが、ModuleやObjectのメソッドにはいろいろと便利なものが隠れて(?)います。ある程度Rubyに慣れたあとは、知らない機能を見つけたらマニュアルで小さな例で試して何に使うかを理解しておくとあとできっと役立つ機会があるはずです。
オブジェクトを作ることは比較的重い処理です。また、不要になったオブジェクトはGCによってゴミとして回収されますが、これが以外と時間を食います。再利用可能なオブジェクトは変数や定数に代入してとっておくのが良いでしょう。ゴミ問題はRubyインタプリタにとっても深刻なテーマなのです。
小技がどれくらい有効なのかは、実際に実行時間を計ってみるのが手軽でしょう。コード内の一部分の実行時間を調べるには Time::times が使えま
す。このクラスメソッドはC言語のtimes(3)に相当しインタプリタプロセスが使った時間を返すものです。返ってくる値は Time::Tms という
Struct オブジェクトで、ユーザ時間とシステム時間を utime、
stime というメソッドで得ることができます。また、子プロセスで費やした時間を cutime と cstime で得ることができます。
RAAにBenchmarkというのがあります。これは Time.times を使って実行時間を計測し、その結果を見やすく表示するためのライブラリです。tarball
を展開したら、
$ ./INSTALL install
インストール完了です。インストールするディレクトリを変える方法は
$ ./INSTALL
のように引数なしで実行すれば利用法が表示されます。さて、このライブラリは典型的にはList1のように使います。
-- List1 benchmarkdemo.rb: for と each はどっちが速い?
require "benchmark"
N = 1_000_000
a = Array.new(N)
i = nil
Benchmark::bmbm do |x|
x.report("for (#{N})"){ for i in a do end }
x.report("each (#{N})"){ a.each do |i| end }
end
List1を実行するとFig3のような結果が表示されます。数値はそれぞれ、ユーザ時間、システム時間、その和、および実際に経過した実時間です。ここで
Rehearsal(リハーサル)と書かれている部分は、測定する内容をあらかじめ1度実行している部分です。これによってインタプリタにある程度十分なメモリを確保させることで、測定する順序によるバラツキを押えています。そしてそのあとに続くのが本番の測定結果です。本番では各測定の直前にGCを行なうことで、直前に行なった測定の影響をできるだけ小さくしています。もし、2回行なう必要がなければBenchmark::bmというもっと原始的な関数もあります。こっちはGCを勝手に行なったりもしません。詳細はドキュメントを御覧下さい。
-- Fig3: List1の実行結果(Pentium 100MHz)
Rehearsal --------------------------------------------------
for (1000000) 3.187500 0.000000 3.187500 ( 3.229700)
each (1000000) 4.820312 0.000000 4.820312 ( 4.867853)
----------------------------------------- total: 8.007812sec
user system total real
for (1000000) 3.179688 0.000000 3.179688 ( 3.186160)
each (1000000) 4.710938 0.000000 4.710938 ( 4.732444)
Benchmarkはできるだけラクに測定が行うことをねらったツールですが、得られるのはあくまで実測値なのでその結果はさまざまな要因に左右されうることには御注意下さい。とくに複数のプロセスで行なった測定結果を比較するのは一般に間違っています。
また実測で得られた数パーセント程度の違いには意味がないことが多いものです。必ず何回か実行して傾向をつかみましょう。また問題のサイズを大きくしながら実行するとオーダーが見えてきます。数字をみてもピント来ない場合はグラフを描いてみるのも手です。予想したオーダーと違うなど意外な発見があるかも知れません。
破壊的メソッドがあればそちらを使いましょう。具体的には「!」を末尾にもつメソッドがある場合はそちらを使ってみましょう。これは余分なオブジェクトを作らないという原則から導かれるものです。ただし「!」のついたメソッドは変更がなかった場合に nil を返すので、メソッドチェーンの途中には使えないというアキラメが必要です。
たとえば辞書順にソートするには大文字か小文字に揃えてからソートすれば良いのですが、ここでメソッドチェーンと破壊的のトレードオフがあります。メソッドチェーンは読みやすいことが多いのですが速度を損なうこともあります。破壊的メソッドを使う場合は、コードがコマギレになるのですが、新たなオブジェクトを作らないので高速になります。Fig4は文字列の配列を辞書順にソートする実験です。結果からリハーサルは削ってあります。実際に測ってみると破壊的な方法の方が2倍近く速いことがわかります。
-- Fig4: メソッドチェーンと破壊的操作の比較
$ cat bm_sort.rb
require "benchmark"
def words
open(__FILE__).read.split
end
N = 10000
Benchmark::bmbm do |x|
x.report("Method-chain") {
N.times{ r = words.map{|s| s.upcase}.sort }
}
x.report("Destructive") {
N.times{
r = words
s = nil
r.each { |s| s.upcase! }
r.sort!
}
}
x.report("(common)"){
N.times { words }
}
end
$ ruby bm_sort.rb
…中略…
user system total real
Method-chain 40.125000 3.843750 43.968750 ( 45.314832)
Destructive 23.484375 3.250000 26.734375 ( 27.994759)
(common) 9.812500 3.375000 13.187500 ( 14.810195)
Rubyに欠かせない機能としてメソッドにブロックを渡せることが挙げられます。本連載の第2回で詳しく取り上げましたが、ブロック変数はブロックの外側で初期化しておくと速くなるということを書き忘れてしまいました。
eachの場合、この小技によっておおよそ繰返しそのものの実行は2倍ほど速くなるようです(Fig5)。ただし、この時に得をする時間はStringオブジェクトを一つ作るのにかかる時間とほぼ同じです。ですから、1回の繰返しが非常に軽い場合には有効といえます。ちょっとだけ注意が必要が必要なのは、ブロック変数をブロックの外側で初期化すると、その変数のスコープがブロックの外側まで広がることです。
-- Fig5 ブロック変数の初期化のメリット
$ cat bm_blockvar.rb
require "benchmark"
N = 100000
A = Array.new(N)
res = Benchmark::bmbm do |x|
x.report("not initialized (1)"){ A.each{|i|} }
x.report("not initialized (2)"){ i = nil; A.each{|i| j = i} }
x.report("initialized (1)") { i = nil; A.each{|i|} }
x.report("initialized (2)") { i=j=nil; A.each{|i| j = i} }
end
print "----------------------------------------\n"
print "init/non-init(1): ", res[0].real/res[2].real, "\n"
print "init/non-init(2): ", res[1].real/res[3].real, "\n"
$ ruby bm_blockvar.rb
…中略…
user system total real
not initialized (1) 1.312500 0.000000 1.312500 ( 1.310346)
not initialized (2) 1.593750 0.000000 1.593750 ( 1.605165)
initialized (1) 0.492188 0.000000 0.492188 ( 0.491133)
initialized (2) 0.812500 0.000000 0.812500 ( 0.814862)
----------------------------------------
init/non-init(1): 2.668006579
init/non-init(2): 1.969861129
ブロックといえばその実行方法も問題です。yieldはcallよりもずっと速いので、できる限り yield を用いましょう(Fig6)。
-- Fig6 yield 対 call
$ cat rb_yield.rb
require "benchmark"
def y; yield; end
def c; proc.call; end
P = lambda{}
N = 100000
Benchmark::bmbm do |x|
x.report("yield"){ N.times{y(&P)} }
x.report("call") { N.times{c(&P)} }
end
$ ruby rb_yield.rb
…中略…
user system total real
yield 3.562500 0.007812 3.570312 ( 3.606996)
call 9.937500 0.015625 9.953125 ( 10.639729)
配列の最初の要素を参照して、変数に代入するには多重代入を使うのが実は高速です。具体的には、次のようにします。
a, = array
効果のほどは自分で確かめてみて下さい。この方法のメリットは、単に速くなるだけでなく他に副作用がないので安心して使えるという点です。また打つのも楽ですね。カンマが目立たないのが心配ならば、カンマの前に空白をおくのは一つの手です。これによって先頭の要素を取り出しているんだということを少しは主張できるかも知れません。
a , = array
ところでこの例からもわかるように左辺にカンマが現れる代入文は多重代入として扱われます。そして、左辺がカンマで終る代入文もアリなのです。このような多重代入は、ブロック変数でもしばしば使われるものです。次の例は1と3 を表示します。
[[1,2],[3,4]].each{|i,| p i}
いっぽう次の例は [1,2] と [3,4] を表示します。
[[1,2],[3,4]].each{|i| p i}
なお、この連載の第3回でメソッド間の依存関係を示しましたが、そこで多重代入には to_a が使われると書きました。実はRubyが1.6になってから、多重代入に使われるのは to_ary になりました。ちょうど to_s
に対する to_str のような位置づけです。to_ary はデフォルトでは定義されていませんので自分で定義したクラスを多重代入で用いたい場合はこのメソッドも定義する必要があります。
小技はやっぱり小技なのですが、うまく用いれば効果的な場合も案外少なくないでしょう。しかし漫然と使ったのでは活かされません。やはり、プロファイルなどを経て時間のかかっているところを探し、その上で使うのがベストです。もっとも、上に挙げた小技は常用しても構わないと思います。その中でもオブジェクトを作り過ぎないというのは、Rubyに限らずGCを備えたインタプリタにとってはいつも通用するものです。
ところで、もしこれらの技を駆使しても実用には速度が足りず、しかしRubyで問題を征服したい場合は拡張ライブラリを書くと言う方法があります。これは数値実験のようにCで書くことでオブジェクト生成を抑えられる問題には特に有効な方法です。Rubyは拡張ライブラリが極めて書きやすい言語の一つなので機会があれば取り上げたい話題です。
世紀の変わり目に英語のメーリングリスト ruby-talk でちょっと面白いコンペがありました。それは1週間で80通のメールが飛び交ったなかなかホットなスレッドです。よい機会ですのでここでその顛末を紹介しますね。
課題はアナグラム探しを高速化しようというものです。アナグラムとは、文の文字を並べ変えて作られる別の文のことです。一番簡単な場合は単語の中の文字を並べ変えて別の単語に仕立てるもので、今回扱われたのもこの問題です。例えば「ともさかりえ」のアナグラムには「さかもとえり」があります。しかし、何が単語で何が単語でないかは難しい問題ですから、与えられた単語集からアナグラムを抜き出すというのが課題です。多くの人は単語集として /usr/share/dict/words ファイルを用いたようです。FreeBSD の heir(7) によればこのファイルは common words からなる辞書ということになっていて、具体的には1行に1単語が辞書順に書かれたテキストファイルです。
コンペの発端は Joseph McDonald からの質問でした[8142]*1(以下敬称略)。 Ben Tilly が perlmonks に書いたアナグラム探しをRubyで書き直したのだけど、もっと速くするアイデアはありますか? というものです。
JoshephのコードはList2の通りです。このプログラムは次のように使います。
ruby find_anagram0.rb < /usr/share/dict/words
-- List2 ruby-talk-8142.rb: Josephの叩き台[ruby-talk:8142]
#!/usr/local/bin/ruby
# Takes a list or words, finds all anagrams in it
def find_anagrams(words)
anagrams = {}
words.each do |word|
word.chomp!
key = word.downcase.to_s.split('').sort
anagrams[key] ||= Array.new
anagrams[key].push(word)
end
anagrams.values.each do |lst|
puts lst.join(" ") if lst.length > 1
end
end
words = $stdin
find_anagrams(words);
find_anagrams のアルゴリズムは次のようなものです。Enumerableな単語集オブジェクトを引数 words として渡すと最初に each を使って各要素 word を小文字に揃えて、1文字ごとに分解した配列を作り、その配列をソートした結果である key を使って単語を anagrams
というハッシュに格納します。この key は作り方から分かるようにアナグラムごとに一意になっています。そしてすべての単語の登録が終ったら、
anagrams の値だけからなる配列 values の各要素のうち2個以上の単語を含むものだけを空白で join して puts するわけです。
さて、これに対して、筆者がちょうどこの記事に書いていることを手短に述べ、それを実践してみせました[8145]。しかしその実践があまりに不十分だったため(笑)、David Alan Black [8152]と Dave Thomas [8160]から小技を徹底した改善案が出されました。アルゴリズムは変わっていません。ただし Dave は最後の出力の部分で Hash#values をkeys で置き換えた繰返しにしました(List3)。values はわりと大きな配列を1つ生成するので、このコストを抑えたわけです。また、each を for で置き換えています。ここまでで最初の叩き台から比べると3.6倍ほど速くなりました。
-- List3 ruby-talk-8160.rb: David と Dave の改良
def fa6(words, out = STDOUT)
anagrams = {}
keys = {}
word, key = nil
for word in words do
word.chomp!
word.downcase!
key = word.split('')
key.sort!
key = key.join
if anagrams[key]
anagrams[key] << word
keys[key] = 1
else
anagrams[key] = [ word ]
end
end
for key in keys.keys
out.puts anagrams[key].join(' ')
end
end
次のブームは一番時間がかかっていそうな、一意なキーを作り出すところで組み込み機能を活用するためのメソッド置換えのバリエーションです。ここまでの様子をみていた Joe (Joseph) が、組み込みの機能の利用を考え、
split でなく each_byte を使った方法を発表しました[8163]。文字列より整数の方が軽いことを利用したのです。一方 David は
unpack を使いました[8169]。また David は word.downcase! が辞書のエントリと違うものを出力する原因になることを指摘しました。彼らのキーの生成はそれぞれ次のようになっています:
word.downcase!
key = []
word.each_byte {|s| key.push(s)}
key.sort!
key = word.dup
word.downcase!
key = key.unpack('c*')
key.sort!
この二つは叩き台とおなじアルゴリズム(文字の配列をソートしたものをキーとする)を使ったものではおそらく最速のものと思われます。叩き台から比べると約倍速くなっています。
ところで、Joe が最初に指摘したのですが Guy Decoux から測定方法に関する注意[8164]が出されました。メモリ確保にかかる時間があるので、最初に一回は全部の方法を実行し、プロセスを十分に太らせてから測定しないと公平な測定は行なえないというものです。bmbm はこの意見を取り込んで2パスとして作ったものです。それ以前は bm という1パスのユーティリティしかありませんでした。
さて、Barry Shultz は素因数分解の一意性を利用した注目すべき方法[8287] を出してきました。初等的な数学を用いてアルゴリズムそのものの見直しを図ったという点で画期的です。それまでのアプローチと違い文字配列のソートを使いません。
Barry の方法はアルファベットの各文字に一意な素数をそれぞれ割り当て、単語のキーとしてその単語の中に含まれる文字に対応する素数をすべて掛け合わせたものを用います。素数の積を因数分解すればどの素数をいくつ掛けたかを知ることができます。つまり掛け合わせた素数と文字が対応し素数の個数と文字の個数が対応しているのです。これは任意に大きな整数を扱うことのできる
Ruby ならでは方法といえるでしょう*2。ただし、この方法は長い単語に対しては大変大きな数を割り当てることになるので、遅くなってしまいます。例えば David[8163]の
unpack には負けてしまいます。
これに対して叩き台の元になったPerl版を書いた Ben は、英文で頻度の高い文字から順に小さな素数を割り当てれば良いのではないかという提案をしました[8468]。David はこれを実行しみずから upcase が敗れたことと宣言しました[8475]。キーの実装は次のような具合です。
key = 1
word.each_byte {|s| key *= asc2prime[s]}
ところでこの改良には明らかにヒューリスティックが入っています。つまり「平均的な文字の分布」を使っているのです。これ以前の方法は一切仮定をしないものでした。これはある意味現実的ではありません。実際は「いつでも速い」ものは存在しないけれど、「たいてい速い」ものは存在するわけです。アナグラムに限らず、現実的にはこういった仮定をするのは自然なことです。
ただし現実的な最適化というのは一般には非常に難しい問題です。なぜなら入力の分布を得られることがマレだからです。たとえばクイックソートの「平均」計算量は、よく知られているように O(n log n) ですが、だからといってあなたがソートしたいデータに対しても同じ平均計算量を持つとは限りません。ソートされるデータの分布によって平均は変わってしまうからです。
Barry は正月を使って自分の方法をさらに一歩進め、文字に素数を割り当てるかわりにその素数の対数をとって何倍かして丸めて整数にしたものを割り当てることで掛け算を足し算で置き換えるという方法を出してきました[8508]。これは、log(ab) = log(a)+log(b) という関係に基づいた戦略です。このように対数を使うと掛け算を足し算に置き換えることができるので対数表は中世の天文学者の寿命を伸ばしたといわれています。一見もっともらしいこのアイデアは、しかし丸め誤差があるではないかという指摘を David
や Jean から食らうことになります。Jean は欠点を指摘するだけでなく足し算による真っ当なインデックスの作り方を示しました。それは1単語中に現れる各文字 ch の最大数 occ[ch] を仮定しするという方法です。例えば、文字 a、b、c にそれぞれ 1 と 10 と 100 を割り当てた場合、二つの単語 abc と cab はどちらも key == 111 となります。この場合、a
は最大10回出現できます。ここでは底を10にとっていますが、もっと小さな値にしてもいいかも知れません。これに対するコメントとして Dave はBloomフィルター[Fis]のような統計を使うことを提案をしました[8528]。Jean によって単語中の文字のヒストグラムを26要素の配列として作り pack してキーにするという単純な方法が試されましたが、思いのほか遅いものになりました[8544]。
この一連のお祭り騒ぎはいろいろな教訓を再確認させてくれたという意味で非常に有意義なものでした。これだけ含蓄のあるスレッドはニュースを毎日眺めていてもなかなかお目にかかれないものです。とりわけ印象的だったのはアルゴリズムが勝ったことです。また upcase を使って文字列をバイトを要素とした配列へ分解するのもときどき使われる技法なので覚えておきたいですね。
ちなみに David は最後に反則技も使いました。文字列をバイトに関してソートするというメソッドをCで実装したのです[8551]。これは単なる笑いごとではありません。時間のかかかっているところを探してそこをギンギンに高速化したわけですから実に現実的です。こういうハイブリッドな方法を必要に応じて柔軟に使えることはむしろ見習うべきだと思います。ただ、ここではレギュレーション違反ですけどね :-)
一つ残念だったのは、筆者以外の日本人がこのお祭りに参加しなかったことです。このあとで個人的なメールのやりとりを何通か交わしましたが、海の向うのRubyistたちは一様に日本人が参加してくることを期待していると筆者に告げました。そう、Ruby は日本発なので日本の Rubyist はとても需要があるのです。
確かに、よほど必要にかられていない限り英語のメールを書くのはためらわれます。筆者だって comp.* にコメントすることはほとんどありません。必要にかられているときというのは多分質問をしたい時でしょう。質問するときは余計に自分の英語が気になるものです。この英語で分かってもらえるだろうか、読んでもらえるだろうか等々。一方、質問に答えるときは少し余裕をもって書くことができます。これは大きな違いです。相手に読んでもらえることが分かっているとかなり気が楽になります。そして ruby-talk には、この連載を読んでいらっしゃる方なら答える質問がきっと1週間にいくつもあるはずです。
Dr. Dobb's Journal にRubyの記事が出て以来、 ruby-talk はめっきりアクティブになり、その流量の多さから逃げ出してしまう人も多いようですが、自分が関わったスレッドというのは案外ついていけるものです。もっとも、筆者は今でもこっぱずかしい勘違いをすることも多々ありますが。またアナグラム対決で使われた Benchmark は筆者が書いたものだったというのも個人的には嬉しいことでした。気に入ったものができたら英語のドキュメントをつけてRAAに登録しておくとこういう楽しい体験に恵まれることもあります。
筆者はこの冬休みに結構な数の英語のメールを書いたのですが、これはとても勉強になりました。読むだけでは見落としていた自分の英語に関する無知がコミュニケーションを通じて明らかになることを改めて実感した次第です。ですから、みなさんにも ruby-talk に参加することを強くお薦めします。最初は質問に答えるのがいいでしょう。ぶっきらぼうと思われても構わずに簡潔にポイントだけを答えればいいと思います。逆に無理に簡潔にする必要はありません。言葉が足りなければコードで補って、意味を理解してもらうことを念頭に置く必要はあります。ただ、コードだけ示すのは英語を書く勉強にはなりませんので、短くてもいいからなるたけ英語でコメントをつけてコードを示すのが良いでしょうね。みんなでRubyの楽しみを共有しましょう。海の向うではみなさんの参加を心待ちにしている人が大勢いますよ。
A.V. エイホ, J.E. ホップクロフト, J.D. ウルマン, 『データ構造とアルゴリズム』, 大野義男訳, 培風館 (1987)
T. コルメン, C. ライザーメン, R. リベスト, 『アルゴリズムイントロダクション』(全3巻), 浅野哲夫ほか訳, 近代科学社 (1995)
ジョン・ベントリー, 『珠玉のプログラミング』, 小林健一郎訳, ピアソン・エデュケーション (2000)
Mark Fischer, ``Coding Bloom Filters'', <URL:http://www.flipcode.com/tutorials/tut_bloomfilter.shtml>
D.E. Knuth, 『The art of computer programming』(既刊4巻), 広瀬健ほか訳, サイエンス社 (1978)
B.W. カーニハン, R. パイク, 『プログラミング作法』, 福崎俊博訳, アスキー (2000)
Zohar Manna, ``Mathematical Theory of computation'', McGraw-Hill (1974)
奥村晴彦, 『C言語による最新アルゴリズム事典』, 技術評論社 (1991)
R. セジウィック, 『アルゴリズム』(全3巻), 野下浩平ほか訳, 近代科学社 (1990)
Gotoken, ``Benchmark'', <URL:http://www.ruby-lang.org/en/raa-list.rhtml?name=Benchmark>
Joseph McDonald, ``speedup of anagram finder'', <URL:http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/8142>, およびここから始まるスレッド
問題のサイズ n に対する時間コストを関数 T(n) と表すとき、このコストについて T(n) = O(f(n)) であることの数学的な定義は次の通りです。
「N<n ならば c T(n) < f(n)」となるような定数 c と N が存在する。
たとえば、
ならば次の4つはいずれも成立します。
この場合一般には、T(n) = O(n^2) と表します。
このO(f(n))の定義の気持ちは次のように考えると理解しやすいかも知れません。関数 f はアルゴリズムによって決まり、 c に相当する量は実装にも依存する量です。そして、どんな実装をされたとしてもアルゴリズムを変えなければ、その実行時間を上から押えるような関数を表すのがオーダー f(n) です。 N は c で決まるので結果的に N も実装で決まります。いいかえれば、アルゴリズムを実装することは定数を変える程度の違いしかありません。10倍速いプログラムは確かに優れていますが、オーダーを小さくするプログラムに比べるとある程度の大きさN 以上の問題には決してかなわないわけです。
ただ、Nの大きさが現在の処理系も含めた実装で決まるcに対してどの程度有意義であるかは現実的に考えなければならない問題ではあります。もし、あるアルゴリズムA1が別の O(n) であるような標準的アルゴリズムA2よりずっとオーダーが小さくて O(log n) であったとしても、実装上の都合で c がとてつもなく大きなためにA1がA2に勝てる大きさ N が10の100乗だった場合には、残念ですが今のところ手に追えません。たとえば、組み込みメソッドとユーザが定義したメソッドは定数 c が全然違います。そういう意味でビッグオーは万能ではありません。
そうはいっても、このようなコストに関するオーダーの議論はCPUのスピードアップが激しい今日も全く色あせることはありません。むしろ計算機が速くなることによって、現実的に手が届く N の大きさは上がっていくので、優れたアルゴリズムが威力を発揮する場面はますます増えていくでしょう。そんなわけでオーダーを直観的に掴むセンスを磨いていきたいですね。