<tl;dr><optimizations>ソース バージョン管理の差分パッチの生成において、差分パッチを作成するために diff の私の Ruby 実装で、
この記事の一番下に記載されている最適化 (「参考文献」を参照) を使用する価値はありますか?
</tl;dr>
<introduction>
私は今までにやったことがないことをプログラミングしています。私がプログラミングしていることとまったく同じことを行うためのツールがすでに存在しているかもしれませんが、現時点では気にするのはあまりにも楽しいので、それでも最初からやり直すつもりです。これにはツールがあります。
とにかく、私は Ruby on Rails アプリに取り組んでおり、特定の機能が必要です。基本的に、たとえばビデオゲームのテーブルなど、私のテーブルの各エントリに、そのテーブルエントリのレビューなどを表すテキストのチャンクを保存する必要があります。ただし、このテキストを登録ユーザーが編集できるようにし、バージョン管理システムでさまざまな送信を追跡できるようにしたいと考えています。私が考えることができる最も簡単な解決策は、テキスト本文とテキスト本文のさまざまなバージョンの差分パッチ履歴を Ruby のオブジェクトとして追跡し、できれば人間が読める形式でシリアル化するソリューションを実装することです (したがって、私はほとんどの場合、これには YAML を使用します) ソフトウェアのバグによる破損や、管理者がバージョン編集を行う際のミスにより、必要に応じて編集します。
そのため、最初はこの機能に頭を突っ込んでみましたが、差分パッチを生成する問題は、私が効率的に行うと思っていたよりも難しいことがわかりました。そこで私はいくつかの調査を行い、いくつかのアイデアに出くわしました。すでに実装したものと実装していないものがあります。ただし、diff または diff に似た機能を使用して何かを既に行っているかどうか、およびそれを解決する関数を最適化したことがあるかどうかはすでにわかっているため、すべてが最も長い一般的なサブシーケンスの問題を中心に展開しています。
現在、私はそれを持っているので、一致しない行が見つかるまで、テキスト本文の比較されたバージョンを最初と最後から切り捨てます。次に、比較行列を使用して問題を解決しますが、例を見た最も長い一般的なサブシーケンスアルゴリズムのように一致する行が見つかったときにセルに格納されている値をインクリメントする代わりに、一致しない行があるときにインクリメントするので、最長共通部分列の代わりに編集距離を計算するように。私が知る限り、この 2 つのアプローチは同じコインの裏表であるため、どちらを使用しても答えを導き出すことができます。次に、比較マトリックスをバックトレースし、インクリメントが発生した時期と隣接セル (西、北西、または北) を記録して、その行の diff エントリを決定し、他のすべての行が変更されていないと想定します。
通常はそのままにしておきますが、これはスタンドアロンの Ruby スクリプトだけでなく、Rails 環境にも適用されるため、少なくとも十分に最適化する必要があるのではないかと心配し始めました。システムを制御し、私の最悪のシナリオのエントリがサーバーにそれほどヒットできないことを知っていました. インターネットを介して研究論文や記事を検索して読んだ後、まともなように見えるがすべてに長所と短所があるように見えるいくつかに出くわしました。アウト。ここにリストされているものはそれだけの価値がありますか？それらを既知の長所と短所とともにリストしました。
</introduction>
<optimizations>
行が変更されていない場所で分割し、各セクションの最初と最後で変更されていない行の各セクションを切り捨てることにより、比較されたシーケンスを複数のサブシーケンスにチョップします。次に、各サブシーケンスの編集距離を解決します。
長所: 変更された領域が大きくなるにつれて、時間の増加を 2 次増加から線形増加に近いものに変更します。
短所：分割する場所を特定することは、編集距離を解決する必要があるように思えますが、今ではそれがどのように変更されたかは気にしません。これがハミング距離の解決に近いプロセスで解決できる場合は問題ありませんが、1 回の挿入ではこれが失敗します。
暗号化ハッシュ関数を使用して、すべてのシーケンス要素を整数に変換し、一意性を確保します。次に、シーケンス要素自体ではなく、ハッシュ整数を比較して編集距離を解決します。
長所: 2 つの整数を比較する操作は、2 つの文字列を比較する操作よりも高速であるため、比較のたびにパフォーマンスがわずかに向上します。
短所: 暗号化ハッシュ関数を使用すると、すべてのシーケンス要素を変換するのに時間がかかり、整数比較から得られる変換を行うためにより多くの時間がかかる可能性があります。文字列に組み込みのハッシュ関数を使用できますが、一意性は保証されません。
遅延評価を使用して、比較行列の中心にある 3 つの対角線のみを計算し、必要に応じて追加の対角線のみを計算します。また、このアプローチを使用して、ここで説明したように、隣接する 3 つのセルすべてを比較する必要がなくなる可能性があります。
長所: 常に O(n * m) 時間かかるアルゴリズムを変更して、最悪のシナリオのみがその時間であり、最良のケースは実質的に線形になり、平均的なケースは 2 つの間のどこかにあるようにすることができます。
短所：関数型プログラミング言語でしか実装されていないアルゴリズムであり、上記のリンク先のサイトで説明されている方法に基づいて、これをRubyに変換する方法を理解するのに苦労しています。
C モジュールを作成し、C のネイティブ レベルで大変な作業を行い、そのための Ruby ラッパーを作成するだけで、Ruby は必要なすべての呼び出しを行うことができます。
Pro : このようなものを評価すると、はるかに高速になる可能性があると想像する必要があります。
短所: Rails が C 拡張を持つ Ruby コードを使用したアプリをどのように処理するのかわかりません。また、アプリの移植性が損なわれます。
これは、編集距離の解決後の最適化ですが、アイデアは、各バージョンによって生成された差分を組み合わせて追加の差分を保存し、最近作成された差分をツリーのルート ノードとしてデルタ ツリー データ構造を作成することです。どのバージョンでも、O(n) ではなく O(log n) の最悪のケースの時間がかかります。
長所: 古いバージョンに戻るのがずっと速くなります。
短所：新しいコミットのたびに、デルタツリーが新しいルートノードを取得することを意味します。これは、言うまでもなく、バージョンを戻すよりもはるかに頻繁に実行される操作のためにデルタツリーを再編成するのに時間がかかります古いバージョンである可能性は低いです。
</optimizations>
では、これらのことは努力する価値があるのでしょうか?