diff

…Thebe上に実装してみたのはいいんですが、困ったのがeditgraphの管理。
Dで書けばint[int]、これをどう表現するか。

KeyとValueをレコードにして、その動的配列でバイナリサーチとか。
↓
挿入が遅すぎ。待っても待っても終わりません。

なら…。

普通に二分木。
↓
まだ遅い。

なら…。

まずハッシュで1/$10000(0x10000)に絞りこんでから二分木。
↓

…小さなファイルではうまくいってるようだが…！？…メモリ食い過ぎです。
170KB弱のVariants.pas(のD6のそれとD7のそれの比較)すらメモリ256MBでは足りません。
スワップしまくりでも足りません。

二分木の要素はKey,Value,Left,Rightで16バイトを1MB分束にして、VirtualAllocでがさっと確保して独自に切り分けて…要するに簡単な固定長メモリアロケータまで書いたのですが。

足りません。
絶望的に足りません。

どうしよう。
そもそもdiffってこんなにメモリを食うのが正しいのか？
ふたつのファイルサイズの積に比例して食ってる気がしますよ！？
テキストdiffなら行単位なので、一行平均10文字としても1/100で済むんでしょうね。
…って1/100でも結構食うような…ホントSubVersionとかどうやってんですか？

…そもそもeditgraphって必要なのか…？fpに情報が残らないのか…？
と思って値を確認したりしてたのですが、片方の挿入分のみ残ってる様子。でも、ならばとふたつのバッファを入れ換えて再実行して挿入分と削除分を得ようとしても、どちらを主とするかで、差分の取り方が異なってしまい、違う結果になってしまいます。

うー…。

http://pukiwiki.sourceforge.jp/dev/?PukiWiki%2F1.4%2FDiff

PukiWikiの方法は、オリジナルは配列なのですが、効率悪そうでしたのでリンクリストにして、メモリの節約になりました。X,Y,Prevで12バイトなので3/4。
しかし精度がよろしくない。がさっと大きい範囲を不一致にされることがあります。

どうしたもんか。

結局、PukiWikiのデータ記録方式改リンクリストバージョンを基本に、simple-diff.rb*1のcountの使い方をハイブリッドにして、今日のところは妥協しておきます。
メモリ使用量はX,Y,Count,Prevでeditgraphと変わりませんが、二分木もハッシュも要らなくなりましたので速度面はまんずまんず？まだ遅いか。

*1:simple-diff.rbのfpの+2は間違いで、viviのサイトにありましたように+3じゃないとバグります