2012/04/24

乱択アルゴリズム

結城浩さんの『数学ガール／乱択アルゴリズム』、昨年日本に行った時に購入してたんだけどやっと読んだ。

フェルマーの巻やゲーデルの巻はわりと一直線だった印象があるけど、今回は前半いろんな話題が出てきて、つまみ食いみたいだなと思ってたら後半でそれらが見事に絡み合って収束し、読んでてとても楽しかった。身近な話題だったせいかもしれないけれど、扱うネタの分量としても良いバランスだったのではなかろうか。ゲーデルの巻の10章は説明がきつそうだったから。

ただ、ここまでシリーズ化されるとドラマ部分が少しづつしか進まないのが実にじれったい。数学でいろいろな分野の発展が思いがけず絡まるように、主人公の異なる連作短篇形式で、時々思いがけないつながりがあるような形のも読んでみたい気がする。

ま、次はガロアがテーマだそうで、ちょうど発売後に日本行きの予定があるので楽しみにしている。

★ ★ ★

ランダマイズは、近似解を求めたい時には平気で使うけど、厳密解が必要な時には使って来なかったな。多分、異常が起きた時に再現しにくいってところに心理的な不安があるんだと思う。でも考えてみたら並行プログラムだって再現しにくいという点では同様で、むしろ疑似乱数なら種を記録しとけば完全再現できる分、並行プログラムよりも楽かもしれん。

とりあえずGaucheのハッシュテーブルのコリジョン攻撃回避を考えないとな (少し前に複数の言語で問題になったやつ)。Gaucheは他の言語ほどハッシュテーブルを多用しないのでwebフレームワークの脆弱性とかいう形では出てきてないけど、本質的には同じ問題がある。Gaucheの組み込みのhash関数はCommon Lispのsxhashと同じで、プリミティブオブジェクトについてはハッシュ値が起動ごとに変わってはいけないという制約があるんだけど(永続的なストレージにハッシュ値を使うことを許すため)、そのハッシュ値で衝突した場合にセカンダリハッシュをかますことにすれば、それはテーブル毎にランダマイズできるはず。

Tags: 本, Programming, Gauche