diff能在自己的游戏中被击败吗?

读取一个文件,将每个文件名放入 HashSet O(1) 添加和 包含实现。

然后读取seconds文件,对照HashSet检查每个文件名。

如果文件1具有长度,则为Total算法 m 第二个文件具有长度 n 是 O(m+n) 根据需要。

注意:该算法假设数据集在物理内存中的速度非常快。

如果数据集不能很容易地放入内存中,那么可以使用 B-Tree 使用磁盘分页。这样,复杂性就会大大降低 O(mlog m) 初始设置和 O(n log m)

这不太好 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

您案例中的算法实现(应包含错误):

# 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个consequentive项并添加N个consequentive项的操作——这需要 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's accepted answer

如果您接受字典(散列映射)是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

评论?改进?

我一直在寻找一个程序来区分大文件而不耗尽内存,但没有找到适合我的目的。我对使用diff进行修补不感兴趣(那么我可能会使用 rdiff 来自librdiff),但为了直观地检查差异,可能需要使用 dwdiff --diff-input (读取统一的diff格式)并可能以某种方式收集diff这个词。

(我的典型用例是:我有一些NLP工具,用来处理大型文本语料库。我运行一次,得到一个122760246行长的文件,我对我的工具进行更改,再次运行,得到一个每百万行不同的文件,可能两次插入和一次删除,或者只有一行不同,诸如此类。)

因为我什么都找不到,所以我只做了一个小脚本 https://github.com/unhammer/diff-large-files 它可以工作(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)))