テキストファイルでバイナリサーチ
2005.11.12 Saturday 00:30
行の長さは様々なので，ファイルサイズから中間点を決めて探す．
中間点を求めた後で改行コードを探して後ろへたどるので，次の探索点をそこにとりたくなるが，それだと分布によっては無限ループに入ってしまう．範囲の最後の行がそれより前の行の合計より長い場合に中間値→最後の値となって範囲が狭まらないから．
ファイル上のオフセットを位置x, その直後の改行の次の値をxに対応するf(x)と考えると階段関数となり，その階段関数に対してバイナリサーチを行うと考えればよい．
でもまだ実装して試してません．
- もし最初の要素と一致した場合には，そこでおしまい．
- ファイルの先頭と末尾にポインタを設定．先頭の値は1行目から決める．末尾はわからないので最大値を設定．
- ファイルサイズで中央にシーク．普通は行の途中と思われるので，次の改行を探し，その後ろの値を得る．
- そこでヒットしなかった場合には，最初のファイルサイズを探索範囲先頭（または末尾）に，今読んだ値を対応する値としてバイナリサーチを続行．
- 範囲両端の値が等しくなったら発見できずに検索終了．
中間点を求めた後で改行コードを探して後ろへたどるので，次の探索点をそこにとりたくなるが，それだと分布によっては無限ループに入ってしまう．範囲の最後の行がそれより前の行の合計より長い場合に中間値→最後の値となって範囲が狭まらないから．
ファイル上のオフセットを位置x, その直後の改行の次の値をxに対応するf(x)と考えると階段関数となり，その階段関数に対してバイナリサーチを行うと考えればよい．
でもまだ実装して試してません．
Comments