可以在自己的比赛中击败吗?
-
06-07-2019 - |
题
我正在寻找用于比较两个文件的适当算法。我认为由于一些额外的限制,我可以比 diff
做得更好。
我所拥有的是两个文本文件,每个文件都包含一个文件列表。它们是在两个不同时间拍摄的系统上所有文件的快照。我想弄清楚在两个快照之间添加或删除了哪些文件。
我可以使用 diff
来比较这些文件,但我不想因为:
-
diff
尝试将更改分组在一起,查找文件中的哪些块已更改。我只是在寻找一个已经发生变化的行列表,这应该是一个比找到最常见的子序列或类似事情更简单的问题。 -
广义diff算法在运行时或空间中是 O(mn)。我正在寻找更符合时间 O(m + n)和太空中 O(1)的东西。
醇>
-
两个文件中的文件列表顺序相同。它们不必须按字母顺序排列,但它们处于相同的相对顺序。
-
大多数情况下,列表之间没有差异。如果存在差异,通常只会有少量新的/删除的文件。
-
我不需要将结果分组在一起,比如说“整个目录已被删除”。或“100-200行是新的”。我可以单独列出不同的每一行。
醇>
以下是对问题的限制:
我认为这相当于有两个排序列表的问题,并试图找出两个列表之间的差异。挂钩是列表项不一定按字母顺序排序,因此您不知道一个项是否“更大”。比另一个。您只知道两个列表中存在的文件的顺序相同。
为了它的价值,我之前发布的这个问题< ahref =“http://ask.metafilter.com/”rel =“noreferrer”>几年前询问Metafilter 。请允许我提前回答几个可能的答案。
答案:此问题称为最长公共子序列
响应:我正在尝试避免最长的公共子序列,因为简单的算法在 O(mn)时间/空间中运行,而更好的算法更复杂且更多“启发式&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更多的内存。
其他提示
读取一个文件,将每个文件名放入 HashSet 类似的数据结构, O(1)
add和 O(1)
包含实现。
然后读取秒文件,根据HashSet检查每个文件名。
总算法,如果文件1的长度为 m
,则第二个文件的长度 n
是 O(m + n)
。
注意:此算法假设数据集在物理内存中非常适合快速。
如果数据集无法轻松放入内存中,则可以使用的某些变体来实现查找。带有磁盘分页的B-Tree 。然后,复杂性将是 O(mlog m)
以进行初始设置,并且 O(n log m)
用于每个其他文件比较。
从理论的角度来看,比较两个字符串之间的编辑距离(因为这里你的字符串是一个有趣的语言,其中'字符'是文件名)不能成为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的某个值。但它绝对是最简单的,它将扩展到任意数量的文件,并且(除非你是负责人)谷歌的备份操作)对于你拥有的文件数量来说,它将足够快。
如果你接受字典(哈希映射)是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),如果它们是链表,这不是真的..但无论如何,那就是这个想法。
对ephemient的回答进行了改进,这只会在有变化时使用额外的内存。
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格式)并且可能以某种方式收集单词差异。
(我的典型用例:我有一些NLP工具用于处理大型文本语料库。我运行一次,得到一个122760246行的文件,我对我的工具进行了更改,再次运行,得到一个文件,每百万行不同,可能有两个插入和一个删除,或者只有一行不同,就是那种东西。)
由于我找不到任何东西,我只是制作了一个小脚本 https:// github。 com / unhammer / diff-large-files &#8211;它工作(dwdiff接受它作为输入),它足够快(比在管道中经常运行的xz进程更快),最重要的是它不会耗尽内存。
我会将文件列表读入两组,并找到这两个列表中唯一的文件名。
在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)))