たつをの日記 - 1999年3月10日

遠出はやめます宣言

OBのひらちゃん来る。で、一週間ぶりに研究室に行ってみる。が、腰にきたので退散。 せっかく来たのに何のおかまいもできませんで。 さてさて、健康上の理由から、 来週に東京である言語処理学会の全国大会には行かないことにしました。 新幹線で何時間も座りっぱなしはしんどいし、 実家(神奈川)に帰ったところでまた悪化してもしょうがないし。 再来週に徳島での学会でデモする予定だったけど、J氏に全部まかせて、 これも行かないことにしました。 無理はしないという方針により、今月はもう遠出はしません。

メモリ不足のときの SUFARY のインデックス作成速度

ちょっと専門的な話です。

SUFARY ホームページの伝言版で、suffix array のインデックス作成速度が遅 いという書き込みがありましたのでちょっと解説。2月後半に、suffix array でのインデックス作成速度の向上作業にちょっと手を染めていました。 結局、スワッピングをどれだけ押えることができるかというのがポイント。日 本語テキストだと、テキストサイズの約2倍の大きさのインデックスが必要に なります。例えば、200M のテキストだと、インデックスは 400M といった具 合。手順として、この 400M のインデックスを 200M のテキストを参照しなが らソート(クイックソート)するという作業が必要になります。ここで、1G く らいメモリのあるマシンだと、600M 全部がメモリ載るのでかなり高速に処理 ができます。でも、メモリ 200M くらいだとスワッピングが起こりまくり(ハー ドディスクがかたかたうるさくなる)、いつまでたっても処理が終わらなくなっ てしまいます。200M のメモリで、400M の long int をクイックソートすると いうのが、スワッピングの元凶です。そこで、400M の long int を数十個に 分割して、それぞれに対してクイックソートして(サイズが小さくなるのでス ワッピングもかなり押えられます)、最後にマージするようにしました。これ で、何とか使える速度になりました。実はそこでいろいろ面白いことをやって いるんですけど、そこらへんは SUFARY の解説書にでも書くつもりです。

失敗事例。 最初、クイックソートの代わりにマージソートなら速くなるかなと 思って実装してみたんだけど、だめだった。 前半のマージは良いんだけど、 ある段階のマージでスワッピングが起こり始め、 その後はスワッピングだらけで使い物にならない。 まあ、アルゴリズムの性質上そうなりそうではあったけど。残念。