独自のゲームでdiffを破ることはできますか？
https://stackoverflow.com/questions/1020925
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2つのファイルを比較するために使用する適切なアルゴリズムを探しています。いくつかの制約が追加されているため、 diff よりもうまくやれると思います。
ファイルのリストを含む2つのテキストファイルがあります。これらは、2つの異なる時間に撮影されたシステム上のすべてのファイルのスナップショットです。 2つのスナップショットの間に追加または削除されたファイルを把握したい。
diff を使用してこれらのファイルを比較することもできますが、次の理由でそうしたくありません。
-
diffは、変更をグループ化して、ファイル内のどのチャンクが変更されたかを見つけようとします。変更された行のリストのみを探しています。これは、最長共通サブシーケンスまたはそのようなものを見つけるよりもはるかに簡単な問題です。 -
一般化されたdiffアルゴリズムは、ランタイムまたはスペースで O（mn）です。時間的には O（m + n）や空間では O（1）のようなものを探しています。
問題の制約は次のとおりです。
-
ファイルのリストは、両方のファイルで同じ順序になっています。それらは必ずしもアルファベット順ではありませんが、相対的の順序と同じです。
-
ほとんどの場合、リスト間に違いはありません。違いがある場合、通常、少数の新規/削除されたファイルのみが存在します。
-
「このディレクトリ全体が削除されました」などのように、結果をグループ化する必要はありません。または「100-200行目は新規」です。異なる各行を個別にリストできます。
これは、ソートされた2つのリストを持ち、2つのリストの違いを把握しようとする問題に相当すると考えています。問題は、リスト項目が必ずしもアルファベット順にソートされているわけではないため、1つの項目が「より大きい」かどうかわからないことです。別より。両方のリストにあるファイルが同じ順序になることを知っているだけです。
その価値については、以前に投稿したこの質問< a href = "http://ask.metafilter.com/" rel = "noreferrer">メタフィルターに質問を数年前に。いくつかの潜在的な回答に事前に対応させてください。
回答：この問題は最長共通サブシーケンスと呼ばれます。
応答：単純なアルゴリズムは O（mn）時間/空間で実行され、より優れたものは複雑でより多くの＆quot; heuristical＆quot;。私の直感では、制約が追加されたために線形時間アルゴリズムがあることがわかりました。
回答：アルファベット順に並べ替えてから比較します。
応答：それは O（m log m + n log n）であり、 O（m + n）よりも悪い。
解決
これは、 O（1）メモリではなく、変更の数の順に必要なメモリですが、 O（m + n）ランタイムです。
本質的には、バッファリングされたストリーミングアルゴリズムであり、特定の行で前のすべての行の違いを認識します。
// Pseudo-code:
initialize HashMap<Line, SourceFile> changes = new empty HashMap
while (lines left in A and B) {
read in lineA from file A
read in lineB from file B
if (lineA.equals(lineB)) continue
if (changes.contains(lineA) && changes.get(lineA).SourceFile != A) {
changes.remove(lineA)
} else {
changes.add(lineA, A)
}
if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
changes.remove(lineB)
} else {
changes.add(lineB, B)
}
}
for each (line in longerFile) {
if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
changes.remove(line)
} else {
changes.add(line, longerFile)
}
}
Lines in the HashMap from SourceFile == A have been removed
Lines in the HashMap from SourceFile == B have been added
これは、ファイルが同じ相対順序でリストされているという事実に大きく依存しています。それ以外の場合、メモリ要件は変更の数よりもはるかに大きくなります。ただし、この順序のため、このアルゴリズムは2 * numChangesよりも多くのメモリを使用しないでください。
他のヒント
1つのファイルを読み取り、各ファイル名を HashSet のような O（1） addおよび O（1）が実装されたデータ構造。
次に、秒のファイルを読み取り、各ファイル名をHashSetと照合します。
ファイル1の長さが m で、2番目のファイルの長さが n である場合の合計アルゴリズムは、必要に応じて O（m + n）です。
注：このアルゴリズムは、データセットが高速で物理メモリに快適に収まることを前提としています。
データセットがメモリに簡単に収まらない場合は、のバリエーションを使用してルックアップを実装できます。ディスクページングを使用したBツリー。複雑さは、最初にセットアップする O（mlog m）と、他の各ファイルの O（n log m）で比較します。
理論的な観点からは、2つの文字列間の編集距離を比較する（ここでは、「文字」がファイル名である面白い言語の文字列があるため）O（m + n）にすることはできません。しかし、ここでは簡略化しています。
あなたの場合のアルゴリズムの実装（間違いを含む必要があります）：
# i[0], i[1] are undoable iterables; at the end they both return Null
while (a = i[0].next()) && (b = i[1].next()) : # read one item from each stream
if a != b: # skip if they are identical
c = [[a],[b]] # otherwise, prepare two fast arrays to store difference
for (w = 1; ; w = 1-w) # and read from one stream at a time
nxi = Null
if (nx = i[1-w].next()) in c[w]: # if we read a new character that matches
nxi = c[w].index(nx)
if nx is Null: nxi = -1 # or if we read end of stream
if nxi is not Null: # then output that we found some diff
for cc in c[1-w]: yield cc # the ones stored
for cc in c[w][0:nxi-1]: yield cc # and the ones stored before nx
for cc in c[w][nxi+1:]: i[w].undo(cc) # about the remainder - put it back
break # and return back to normal cycle
# one of them finished
if a: yield a
if b: yield b
for ci in i:
while (cc = ci.next()): yield cc
高速配列と呼ばれるデータ構造があります。これらはおそらく HashSet のものですが、順序を記憶しているものです。それらの追加とルックアップは O（log N）でなければなりませんが、メモリは O（N）を使用します。
これは、違いを見つける以外に O（m + n）を超えるメモリやサイクルを使用しません。すべての「差分ブロック」（Mの結果項目を削除してNの項目を追加すると説明できる操作）に対して、これは O（M + N）メモリと O （MN） O（Mlog N + Nlog M）の手順。メモリはブロックが完了した後に解放されるため、実際に小さな変更のみを行っている場合、これはたいしたことではありません。もちろん、最悪の場合のパフォーマンスは一般的な方法と同じくらい悪いです。
実際には、ソート時間のログ係数の違いはおそらく重要ではありません。 sort は数秒で数十万行をソートできます。したがって、実際にコードを記述する必要はありません。
sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes
これが必ずしも最速のソリューションであると主張しているわけではありません- Ben Sの受け入れられた答えは、少なくともNの値を超えます。しかし、それは間違いなく最も単純で、任意の数のファイルに拡張できます。 Googleのバックアップ操作）を使用すると、所有するファイルの数に対して十分に高速になります。
辞書（ハッシュマップ）がO（n）スペースおよびO（1）挿入/ルックアップであることを受け入れる場合、このソリューションは時間とスペースの両方でO（m + n）である必要があります。
from collections import defaultdict
def diff(left, right):
left_map, right_map = defaultdict(list), defaultdict(list)
for index, object in enumerate(left): left_map[object] += [index]
for index, object in enumerate(right): right_map[object] += [index]
i, j = 0, 0
while i < len(left) and j < len(right):
if left_map[right[j]]:
i2 = left_map[right[j]].pop(0)
if i2 < i: continue
del right_map[right[j]][0]
for i in range(i, i2): print '<', left[i]
print '=', left[i2], right[j]
i, j = i2 + 1, j + 1
elif right_map[left[i]]:
j2 = right_map[left[i]].pop(0)
if j2 < j: continue
del left_map[left[i]][0]
for j in range(j, j2): print '>', right[j]
print '=', left[i], right[j2]
i, j = i + 1, j2 + 1
else:
print '<', left[i]
i = i + 1
for j in range(j, len(right)): print '>', right[j]
>>> diff([1, 2, 1, 1, 3, 5, 2, 9], ... [ 2, 1, 3, 6, 5, 2, 8, 9]) < 1 = 2 2 = 1 1 < 1 = 3 3 > 6 = 5 5 = 2 2 > 8 = 9 9
さて、 list.append および list .__ delitem __ のようにわずかな不正行為は、それらがリンクされたリストである場合にのみO（1）であり、実際はそうではありません。 。しかし、それはアイデアです、とにかく。
エフェメエントの答えの改良版。これは、変更がある場合にのみ追加のメモリを使用します。
def diff(left, right):
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] == right[j]:
print '=', left[i], right[j]
i, j = i+1, j+1
continue
old_i, old_j = i, j
left_set, right_set = set(), set()
while i < len(left) or j < len(right):
if i < len(left) and left[i] in right_set:
for i2 in range(old_i, i): print '<', left[i2]
j = old_j
break
elif j < len(right) and right[j] in left_set:
for j2 in range(old_j, j): print '>', right[j2]
i = old_i
break
else:
left_set .add(left [i])
right_set.add(right[j])
i, j = i+1, j+1
while i < len(left):
print '<', left[i]
i = i+1
while j < len(right):
print '>', right[j]
j = j+1
コメント？改善点
メモリを使い果たすことなく大きなファイルを比較するプログラムを探していましたが、目的に合うものが見つかりませんでした。パッチを適用するために差分を使用することに興味はありません（おそらくlibrdiffの rdiff を使用します）が、差分を視覚的に検査するために、おそらく dwdiff -diff-input （統合diff形式を読み取ります）と、おそらく何らかの方法でword-diffを収集します。
（私の典型的なユースケース：大きなテキストコーパスを処理するために使用するいくつかのNLPツールがあります。一度実行し、122760246行のファイルを取得し、ツールに変更を加え、再度実行し、取得します100万行ごとに異なるファイル、2回の挿入と1回の削除、または1行だけが異なるファイルなど）
何も見つからなかったため、 https：// githubという小さなスクリプトを作成しました。 com / unhammer / diff-large-files ＆＃8211;動作し（dwdiffは入力として受け入れます）、十分に高速（パイプラインで頻繁に実行されるxzプロセスよりも高速）であり、最も重要なことは、メモリ不足にならないことです。
ファイルのリストを2つのセットに読み取り、どちらかのリストに固有のファイル名を見つけます。
Pythonの場合：
files1 = set(line.strip() for line in open('list1.txt'))
files2 = set(line.strip() for line in open('list2.txt'))
print('\n'.join(files1.symmetric_difference(files2)))
