Take the 2-minute tour ×

I'm looking for the appropriate algorithm to use to compare two files. I think I can do better than diff due to some added constraints.

What I have are two text files each containing a list of files. They are snapshots of all the files on a system taken at two different times. I want to figure out which files have been added or deleted between the two snapshots.

I could use diff to compare these files, but I don't want to because:

  1. diff tries to group changes together, finding which chunks in a file have changed. I'm only looking for a list of lines that have changed, and that should be a much simpler problem than finding the longest-common-subsequence or some such thing.

  2. Generalized diff algorithms are O(mn) in runtime or space. I'm looking for something more like O(m+n) in time and O(1) in space.

Here are the constraints on the problem:

  1. The file listings are in the same order in both files. They are not necessarily in alphabetical order, but they are in the same relative order.

  2. Most of the time there will be no differences between the lists. If there are differences, there will usually only be a handful of new/deleted files.

  3. I don't need to group the results together, like saying "this entire directory was deleted" or "lines 100-200 are new". I can individually list each line that is different.

I'm thinking this is equivalent to the problem of having two sorted lists and trying to figure out the differences between the two lists. The hitch is the list items aren't necessarily sorted alphabetically, so you don't know if one item is "greater" than another. You just know that the files that are present in both lists will be in the same order.

For what it's worth, I previously posted this question on Ask Metafilter several years ago. Allow me to respond to several potential answers upfront.

Answer: This problem is called Longest Common Subsequence.

Response: I'm trying to avoid the longest common subsequence because simple algorithms run in O(mn) time/space and better ones are complicated and more "heuristical". My intuition tells me that there is a linear-time algorithm due to the added constraints.

Answer: Sort them alphabetically and then compare.

Response: That would be O(m log m+n log n), which is worse than O(m+n).

share|improve this question
So the bottom line, at least as I understand it: let's say each change can be represented as deleting M_i lines, adding N_i. Then you need O(max(M_i + N_i)) memory and O(m + n + sum_i(Mlog N + Nlog M) ) instructions. –  ilya n. Jun 20 '09 at 5:27

7 Answers 7

up vote 9 down vote accepted

This isn't quite O(1) memory, the memory requirement in the order of the number of changes, but it's O(m+n) runtime.

It's essentially a buffered streaming algorithm that at any given line knows the difference of all previous lines.

// 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) {
    } else {
         changes.add(lineA, A)

    if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
    } else {
         changes.add(lineB, B)

for each (line in longerFile) {
    if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
    } 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

This heavily relies on the fact the the files are listed in the same relative order. Otherwise, the memory requirement would be much larger than the number of changes. However, due to that ordering this algorithm shouldn't use much more memory than 2 * numChanges.

share|improve this answer
I'm not sure that's right... on inputs (1, 2, 3, 4) and (1, 3, 4) it will 'remove 1A and 1B', then 'add 2A and 3B' and 'add 3A and 4B' and outside the read loop 'add 4A' ... when clearly '2A' is the only difference. –  jerryjvl Jun 20 '09 at 4:56
Yeah, I noticed, it's fixed now. –  Benoit Jun 20 '09 at 4:58
The hashing is done only on the line, and maps to the source file, so my old algorithm would actually have 3 and 4 as additions. –  Benoit Jun 20 '09 at 5:03
Yes, your algorithm, if you expand it, will be essentially the same as mine. The crucial thing is to note that when you hash a very small number of elements, you might as well just do an array :) –  ilya n. Jun 20 '09 at 5:04
That looks a lot better... I'd recommend making the operations on your hash-set a little more explicit though ('add (line, A) from HashSet', etc.) it'll make the solution more readable and understandable :) –  jerryjvl Jun 20 '09 at 5:04

Read one file, placing each file-name into a HashSet-like data structure with O(1) add and O(1) contains implementations.

Then read the seconds file, checking each file-name against the HashSet.

Total algorithm if file one has length m and the second file has length n is O(m+n) as required.

Note: This algorithm assumes the data-set fits comfortably in physical memory to be fast.

If the data set cannot easily fit in memory, the lookup could be implemented using some variation of a B-Tree with disk paging. The complexity would then be O(mlog m) to initially setup and O(n log m) for each other file compare.

share|improve this answer
+1, I love how you're not needing the tricky "same ordering" bit!-) –  Alex Martelli Jun 20 '09 at 4:21
There are usually more processor cycles then memory. –  ilya n. Jun 20 '09 at 4:21
Good one. I've edited the question to specify an O(1) space requirement. Reading either file into memory seems like overkill, an oversight of my original specification. :-) –  John Kugelman Jun 20 '09 at 4:24
I added a new answer with a better memory constraint. –  Benoit Jun 20 '09 at 4:45
OP does say that O(m log m + n log n) isn't good enough, though... so O((m + n) log m) probably isn't either. :( –  ephemient Jun 20 '09 at 4:58

From a theoretical point of view, comparing the editing distance between two strings (because here you have strings in a funny language where a 'character' is a file name) cannot be made O(m+n). But here we have simplifications.

An implementation of an algorithm in your case (should contain mistakes):

# 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

There are data structures that I call fast arrays -- they are probably HashSet things, but the ones that remember ordering. The addition and lookup in them should be O(log N), but the memory use O(N).

This doesn't use any memory or cycles beyond O(m+n) outside of finding differences. For every 'difference block' -- the operation that can be described as taking away M consequtive items and adding N ones -- this takes O(M+N) memory and O(MN) O(Mlog N+Nlog M) instructions. The memory is released after a block is done, so this isn't much of a thing if you indeed only have small changes. Of course, the worst-case performance is as bad as with generic method.

share|improve this answer
The important thing to realize is that we don't actually need to compare the Strings. The problem is different. –  Benoit Jun 20 '09 at 4:22
He does need to compare two strings in an alphabet where character is a possible file name. But we can do it more effectively if we know some constraints. –  ilya n. Jun 20 '09 at 4:28
Interesting. The quadratic cost could be improved to linear by throwing some memory at the problem a la Ben S's answer. In particular, add the lines in A to setA and the lines in B to setB, checking each successive line in each file against the opposite file's set. Once you find a line that is in the opposite set (or you reach EOF in both files) you have re-synchronized yourself. That seems like a darn fast algorithm! –  John Kugelman Jun 20 '09 at 4:41
It can actually be done with less memory that my original answer. I added a new solution. –  Benoit Jun 20 '09 at 4:46
@ilya n: No, you don't need to compare it to everything, you just need to hash it, and see if there's a collision. That's constant time, not quadratic. –  Benoit Jun 20 '09 at 5:13

If you accept that dictionaries (hash maps) are O(n) space and O(1) insert/lookup, this solution ought to be O(m+n) in both time and space.

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
            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

Okay, slight cheating as list.append and list.__delitem__ are only O(1) if they're linked lists, which isn't really true... but that's the idea, anyhow.

share|improve this answer
Yes, I've already suggested something similar to this. the O(m+n) space is not acceptable. The set is too large. –  Benoit Jun 20 '09 at 4:54
I can shrink memory usage in the average case, but avoiding a worst-case O(m+n) space while maintaining O(m+n) time is challenging. I'll sleep on it and see if I come up with something else tomorrow... –  ephemient Jun 20 '09 at 4:59
Worst-case space will be O(m+n), I don't think it's possible to sidestep that. –  ilya n. Jun 20 '09 at 5:32

In practice, a log factor difference in sorting times is probably insignificant -- sort can sort hundreds of thousands of lines in a few seconds. So you don't actually need to write any code:

sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes

I'm not claiming that this is necessarily the fastest solution -- I think Ben S's accepted answer will be, at least above some value of N. But it's definitely the simplest, it will scale to any number of files, and (unless you are the guy in charge of Google's backup operation) it will be more than fast enough for the number of files you have.

share|improve this answer
Indeed. In reality, I changed the client program that generated the file listings to simply generate them in alphabetical order, a simple enough change. That made it trivial to compare the two listings. –  John Kugelman Jun 21 '09 at 6:46

A refinement of ephemient's answer, this only uses extra memory when there are changes.

def diff(left, right):
    i, j = 0, 0

        if left[i] == right[j]:
            print '=', left[i], right[j]
            i, j = i+1, j+1

        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

            elif j < len(right) and right[j] in left_set:
                for j2 in range(old_j, j): print '>', right[j2]
                i = old_i

                left_set .add(left [i])
                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

Comments? Improvements?

share|improve this answer
Yes, looks like the same I did, but you did it cleaner. –  ilya n. Jun 20 '09 at 5:22
Note that you would have to rewrite it with iterators, because holding input data in arrays in unrealistic -- it's already agreed inputs can be big. –  ilya n. Jun 20 '09 at 5:23
Actually I'm not sure you exiting correctly when left[i] in right_set –  ilya n. Jun 20 '09 at 5:31
Storing a small set of lines in memory while you're trying to figure out what's changed is fine by me, if you want to incorporate that into your solution. Or perhaps we can get two solutions written up, one that is slower but uses no extra memory (yours) and one that is faster but uses a bit of extra memory figuring out what's changed (mine, Ben S's). –  John Kugelman Jun 20 '09 at 5:35
No, no, I'm pointing to a slightly different thing. First, our solutions are the same at this point; mine is not slower; well, i said it's N log N, where N is a typical diff size, but this exists in your solution too -- HashSet is NOT constant lookup! HashSet is log lookup. Second, I want to point out that you can't have arrays left, right like you do, since we agreed to not use O(m+n) of memory and those were files in the problem. So, you'll have to read streams/iterators. Third, Ben S solution is now slower than yours(+mine), but can be fixed, after which we'll have 3 identical solutions. –  ilya n. Jun 20 '09 at 5:50

I've been after a program to diff large files without running out of memory, but found nothing to fit my purposes. I'm not interested in using the diffs for patching (then I'd probably use rdiff from librdiff), but for visually inspecting the diffs, maybe turning them into word-diffs with dwdiff --diff-input (which reads the unified diff format) and perhaps collecting the word-diffs somehow.

(My typical use case: I have some NLP tool that I use to process a large text corpus. I run it once, get a file that's 122760246 lines long, I make a change to my tool, run it again, get a file that differs like every million lines, maybe two insertions and a deletion, or just one line differs, that kind of thing.)

Since I couldn't find anything, I just made a little script https://github.com/unhammer/diff-large-files – it works (dwdiff accepts it as input), it's fast enough (faster than the xz process that often runs after it in the pipeline), and most importantly it doesn't run out of memory.

share|improve this answer

Your Answer


