最速インターフェース研究会

JavaScriptを使ったやや高速なDiff概要

多分もっとちゃんとしたアルゴリズムがあるんだろうけど
適当に思いついたので書いてみる。

配列new_lineとold_lineの比較。
まず、先頭キャラ1文字をキーにした連想配列を作っておく。
例えばAで始まる行の行番号が2,4,6だったとすると。
AのcharCodeが65なので。

old_first_char[65][0] = 2
old_first_char[65][1] = 4
old_first_char[65][2] = 6

こんな具合の配列ができる。
同様に、新しい配列のAで始まる行も調べておく。
互いの「A」で始まる行のうち0～3番目の行番号の内容を比較する。

old_line[old_first_char[65][0]] と new_line[new_first_char[65][0]] を比較する。
old_line[old_first_char[65][1]] と new_line[new_first_char[65][1]] を比較する。

new_first_char[65] = [2, 4, 6]だったとしたら、たった3回の比較で終了する。
文書が殆ど変更されていない場合は、n回のループで比較が終了することになる。

典型的な富豪的スクリプターなのでオーダーlogだのnmだのn^2だのとか
良くわかってないが、多分こんな感じ。
単純にループさせると9行の場合はループ回数9*9で81回。
先頭文字がAAABBBCCCなら最大(3*3)*3で27回ですむ。

短い文章の場合はonkeyupで処理しても負担は少ない。インクリメンタルDiffだ。
テキストエリアの編集の場合、エンター押すたびDiff取るのが良いかもしれない。
ただ、JavaScriptは大きな配列を扱おうとすると、とたんに遅くなるのが困り所。

まだアップしてないネタがたまってきた。
アップするのが面倒くさい。

A quick preview will be rendered here when you click "Preview" button.