sid-searchを作り直してみた

経緯

  • http://oupo.xrea.jp/sid-search/で公開していたsid-searchだがこれはXREAの有料プランを使っていた。有料プランの期限が切れるというときにもう別に需要なさそうだからということで更新しなかった。それでずっと停止していた。
  • ふと、CGIを用意しなくとも表IDごとに分けたデータベースを用意して、あとはその中の1つを丸々ダウンロードして計算すればいいじゃないかと気づいた。Dropboxというオンラインストレージはレンタルサーバー代わりに使えると知ってこれを使おう！と思った
  • 手元に前のときのデーターベースが残っていなかったことと色々高速化のアイデアを試したかったので、データベースを作成するプログラムを作り直した
  • データベースができたので、Dropboxにアップロードしようとなったところで、新規ユーザーはもうレンタルサーバー代わりの機能が使えないということを知ってやる気ダウンorz
  • その代わり容量が2GBあるという無料のレンタルサーバーを使ってみることに

前バージョンとの違い

  • 前バージョンでは見つからなかったけど今回では見つかるということはない
  • くじ番号が2個であっても一通りに特定できた場合はそれを採用するようにした
  • 日替わり乱数のseedを1個1個さかのぼっていく方式をやめたのでとても高速。範囲に0x100000000 (=2^32)を指定してある表IDになるすべてのseedを列挙することも可能

技術的な話

1個1個さかのぼっていく方式をやめてどうしたかというと、日替わり乱数のseedが「0からいくつ進めたものか」を計算してそれを利用することにした。
二つのseedの「0からいくつ進めたものか」の値の差をとれば、二つのseedがいくら離れているかがわかる。

「0からいくつ進めたものか」を計算するのは、案外簡単である:

// daily_seed_consts[n]は-(2^n)個先のseedを計算するための定数(乗数と加数)であり、あらかじめ初期化してある
static u32 daily_seed_consts[32][2];

u32 daily_seed_step_minus_2_pow_n(u32 seed, u32 n) {
	return seed * daily_seed_consts[n][0] + daily_seed_consts[n][1];
}

u32 daily_seed_to_index0(u32 seed, int i) {
	if (i == 32) {
		return 0;
	} else if ((seed >> i) & 1) {
		return daily_seed_to_index0(daily_seed_step_minus_2_pow_n(seed, i), i + 1) * 2 + 1;
	} else {
		return daily_seed_to_index0(seed, i + 1) * 2;
	}
}

// seedが「0からいくつ進めたものか」を計算
u32 daily_seed_to_index(u32 seed) {
	return daily_seed_to_index0(seed, 0);
}

データベースの作成からJS上の検索まで簡単に流れをまとめると:

  • 全初期seedについて、トレーナーIDと日替わりseedのインデックスを計算して記録 (ここでインデックスとは「0からいくつ進めたものか」をいうものとする)
  • 順序対 (表ID, 日替わりseedのインデックス)をキーにしてソート
  • 各表IDのファイルに分ける。ただしこのとき初期seedのみを記録する。(そうしないとディスクスペース2GBじゃ足りない)
  • 結局、各表IDのファイルは、その表IDになる全初期seedを、日替わりseedのインデックスによってソートした結果になる(u32の配列をダンプしたバイナリ)
  • JS側では、該当する表IDのファイルを丸々ダウンロードし日替わりseedのインデックスによって二分探索を行う。そこから左へ左へ、日替わりseedインデックスの差が入力された範囲を超えるところまで読んでいき、それを結果とする

細かいところではデータベースを作成するところでは以下のような高速化をした

  • 全初期seedでの計算結果を出すところではOpenMPを使ってマルチコアを活用して高速化 (ここは別に全体からしたら時間のかかる場所じゃないのであまり意味なかった)
  • IOのバッファ領域を大きくとって高速化

データベースの作成の実行にかかった時間

全計算結果を出力 146.13 sec
あらかじめいくつかのブロックに
分けてそれぞれをクイックソート		 295.94 sec
マージソート 1720.69 sec
各表IDのファイルに分ける 400.45 sec

その他

  • JSでバイナリファイルを読み込む際、IEにだけ特別な処置が必要でさげぽよだった
  • JSのコードは最初、データベースから得た該当する表IDの初期seedすべてについて、あらかじめトレーナーIDと日替わり乱数seedを計算させていたのだけれど、Firefox (ver.16)だけ他のブラウザ(IE9, Opera 12, Google Chrome 23, Safari 5)よりずっと遅くてびっくり。なぜだろう
  • データベースのアップロードはFFFTPだと途中で失敗するのでWinSCPを使った
  • ところでこのレンタルサーバーではファイル置き場としての利用は禁止されているので凍結される可能性もなくはない
  • 全計算結果の出力がたったの146秒で済むとはびっくりだ。これならデータベースを使わずにローカルで動かすツールを作ってもぜんぜん実用レベルで動くだろう
筆者: oupo (連絡先: oupo.nejiki@gmail.com)