置換・ソート機能は鬼門
今回は置換・ソートについて考えてみたいと思います。
なぜこの２つをまとめて考えるかというと、「保存処理を中断した後、再開できるようにする」でもちらっと書きましたが、管理データが爆発的に増えていくからですね。
Rope / PieceTable方式の管理データは、何らかの編集動作をする場合、Pieceが2分割されたり、挿入されたりします。
削除は管理データが減るかそのままなのでいいのですが、挿入だと一度の操作で一つ増えるわけではなく、Pieceの途中に文字を挿入する場合、まず分割して、新しいPieceを入れるので、２個いっぺんに増えます。
ちょうど切れ目でなら１個で済むのですが、そんなのは512kバイト単位のブロックなら512k分の1の確率。まず期待できません。
ソートの場合は最悪のケースだと3分割して、その真中の1行分だけを別のPieceデータを2分割した真ん中に入れてあげないといけません。
行のあるPieceは3分割、挿入先は2分割されますので、1行入れ替えで計5分割、3つの管理データが増えることになります。
ほとんどランダムに並んでいるデータですと、ほぼ全行が並べ替えられるわけで、これでは1行1管理データということになり、改行しか無いようなデータが大量に有ればあっという間に元データを遥かに超えるサイズになってしまいます。
一応解決方法としては、小さなブロックはいったん大きなブロックにまとめることで、管理データを小さくしていくことはできますが、今度は更新データが大きくなっていきます。
まとめたデータは更新データとして保存しておく必要がありますので。
逆順で並んでいるデータをソートすれば、全行入れ替えになるので、少なくとも元データと同じ大きさの更新データが出来上がることになるでしょう。
何段階かに分けて小さなブロックをまとめるなんてことをしていたら、更に数倍とかになるかもしれません。
これはあまりよろしくない。
ただでさえHDDを圧迫する巨大ファイル。
更新データと、さらには上書き保存時は.bakファイルも作らなければなりません。
とすると編集するためには元ファイルの2倍以上の空きエリアが必要になるということです。
通常のファイルであれば問題にならないことも、巨大ファイルになれば大問題。
しかしこれを解消するのはなかなかに困難です。
一つの手としては、更新データを別のHDDなどに作成することですね。
今のところ、元ファイルと同じドライブに更新データや保存用管理データなどを保存するか、保存時に空きエリアが足りなければ名前をつけて保存で、別ドライブに保存するなどとする必要があるでしょう。
また、更新データも場合によっては複数のドライブに分割して保存する必要があるかもしれません。
まあ、管理データにはファイルハンドルのようなものが入っているので、更新データファイルがいくつに分解されようと、最終的にはリンクを辿ってひとつのファイルにできるので問題ないといえば問題ないのですが、結構めんどくさいです。
この場合、全く使われなくなった管理データファイルというものができる可能性があります。
そうなった時不要となった管理データファイルは削除できたほうがいいでしょう。
これまためんどくさいですが。
このあたりは仮想記憶を自前で組んでいるのとほぼ同じですからねぇ。
面倒になるのもうなずけるというもの。
なんか素直に64ビット化して普通にシステムの仮想記憶使ったほうがいい気がしてきましたｗ
システムの仮想記憶なら勝手に増えていきますからねー。
手の平くるくるー。
しかしこれだと、「巨大な仮想記憶、その他作業用バッファを使用しない、あるいは最小限に留めること」の要件が達成できません。
もう少し考えてみましょう。
方法としては使わなくなった領域の再利用でしょうか。
Rope / PieceTable方式では更新データは常に追加ですので、ソート時に細かなPieceを合体させるとそこへ合体したあとのデータを追記していく必要があります。
統合された元のPieceは不要になりますから、当然そこに空きができます。
その空きができたところへ、合体させた更新データを書き込むという寸法ですね。
この方法であれば、うまくすれば、元データとほぼ同じだけの更新データ量で収まるはずです。
いっそのこと管理データは使わないほうが良いかもしれません。
どうせ更新データにどんどん書き加えられていくのであれば、それはもう管理データをソートするのではなく、元データをソートしているのと同じことですからねぇ。
どういうことかといえば、まずソートする時、マージソートというアルゴリズムを使います。
細かいアルゴリズムの説明は省きますが、テープに保存されたデータをソートするときなどに使われる方法で、元ファイルとワークファイル最低2個を使って、連続したデータならどんどん一方のワークファイルに追記して行って、前後関係が逆転していたら別のワークファイル追記してソートしていく方法です。
それで全データを読みだしたら、今度は2つのデータをマージ（合体）して、一つのファイルにします。
上記を繰り返し、ソートが終わった時点で、また512kバイトとかに分割して管理データを作り直すわけです。
この時点で、元ファイルはいらなくなるんですが、保存はしていないので、元ファイルを消すわけにはいきません。
.bakファイルも残っていれば、元ファイル3個分のデータがHDDに残っていることになり、結構無駄です。
ここからさらに上書き保存とかすると、保存用のテンポラリファイルも作られることになり、元ファイル4個分が一時的に作成されることになります。
なので、ソートして保存のような機能があるといいかもしれません。
これならば3個分で収まりますし、.bakファイルを作らないのであれば2個分で済みます。
とはいえ全行ソートならこれでもいいんですが、ソート対象が数行であれば、いかにも無駄が多い方法です。
しきい値を設けて、管理データの個数がどの程度増えたかで、実データソートにするか、管理データソートにするか切り替える必要があるかもしれません。
この辺は実装段階で、管理データがどの程度の大きさまで実用性があるかで、しきい値を決める必要があるでしょう。
まあ、ソートはこれでいいとして、置換はどうしましょうか。
これも場合によっては管理データが爆発的に増えていきますので、ソートと同じようにする必要があるかもしれません。
置換して保存、みたいな機能ですね。
しかしここまで来るとSEDみたいなコマンドラインツールを起動すればいい気もしますけどｗ
コマンドラインツールだとパラメータ書くのめんどいから、GUIでパラメータセットして、別プロセスで処理ってのに意味がないわけではないんですが。
この辺は実装段階でスレッドにするか別プロセスにするか要検討ですね。
スレッドはスレッドで、別プロセスは別プロセスでめんどくさいんですが。
どちらかといえば別プロセスのほうがめんどくさくはないかな。
スレッドだとリソースの競合とかおこるともう、どこでそれが起こっているのか突き止めるだけでも大変ですし、タイミングの問題とかになると、現象を再現するだけでも大変なので、スレッド関係のデバッグは地獄ですｗ
呼んでいる関数がスレッドセーフなのか確かめ、競合している変数がないかと、ひとつひとつ虱潰しにしていかないといけないので、一度ハマると大変なことに！
自分もハマって解消に数ヶ月かかったこともｗ
笑い事じゃないんですが。
そこまでしても、ひょんなときに競合する時があって、また一から見直すことにｗ
笑いしか出てきません。
ごくごく偶にしか競合しないと、なんか調子悪いなくらいにしか思いませんからねぇ。
とりあえずスレッドで組んで、ダメそうなら別プロセスにするか。
もし完成版が別プロセスになってたら、スレッドも組めないでやんのｗ と笑ってやってくださいｗ
市販のソフトでも何もしていないのに意味不明のエラーはいて止まることがあれば、そのへんの処理がうまく行っていない可能性があります。
そういえばc++builderも起動しただけで意味不明のエラーはいて止まることがあるなｗ
10.xのバージョンですけど、プロパティを変更しても値が変わらないという謎のバグに遭遇して、大変難儀したこともあります。
IDEでトレースしながら代入後に値を確認したのに値が変わっていない。
いま変数に代入しただろ！ なんで値が反映されていないんだ！？
とIDEに文句行ってもしょうがないですし、バグ事例探すのも大変だし、最小の再現方法探してバグ報告したりするのもめんどくさい。
プロパティ経由じゃなく、直接アクセスにしてバグ回避しましたけど。
でもc++builderってバグ修正遅いんですよねぇ。
サイトも一部死んだままなかなか回復しないし。
とりあえずこれにて要件定義は終了です。
次回からは実装編にいきたいと思いますが、しばらくあきそうなので、一旦締めて、書きたいことができましたら実装編を別途開始したいと思います。
ここまで読んでいただきありがとうございます。
