Можно ли побить свою игру в своей игре?

Ответ 1

Это не совсем 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.

Ответ 2

Прочитайте один файл, поместив каждое имя файла в структуру HashSet, с O(1) add и O(1) содержит реализации.

Затем прочитайте файл секунд, проверяя каждое имя файла на HashSet.

Общий алгоритм, если файл имеет длину m, а второй файл имеет длину n O(m+n) по мере необходимости.

Примечание. Этот алгоритм предполагает, что набор данных удобно помещается в физической памяти, чтобы быть быстрым.

Если набор данных не может быть легко помещен в память, поиск может быть реализован с использованием некоторого изменения B-Tree с пейджингом на диске. Тогда сложность была бы O(mlog m) для первоначальной настройки и O(n log m) для сравнения друг с другом.

Ответ 3

С теоретической точки зрения, сравнивая расстояние редактирования между двумя строками (потому что здесь у вас есть строки на смешном языке, где "символ" - это имя файла) не может быть сделано 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) инструкции. Память освобождается после того, как блок сделан, так что это не большая вещь, если у вас действительно есть небольшие изменения. Конечно, производительность худшего случая не так плоха, как при использовании общего метода.

Ответ 4

На практике разница в логарифмическом коэффициенте во времена сортировки, вероятно, незначителен - sort может сортировать сотни тысяч строк за несколько секунд. Поэтому на самом деле вам не нужно писать код:

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

Я не утверждаю, что это обязательно самое быстрое решение - я думаю, принятый ответ Ben S будет, по крайней мере, выше некоторого значения N. Но это определенно самый простой, он будет масштабироваться до любого количества файлов, и (если вы не являетесь парнем, ответственным за операцию резервного копирования Google), он будет более чем достаточно быстрым для количества файлов, которые у вас есть.

Ответ 5

Если вы принимаете, что словари (хэш-карты) - это O (n) пространство и O (1) insert/lookup, это решение должно быть 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), если они связаны списками, что на самом деле не так... но что идея во всяком случае.

Ответ 6

Уточнение эфемерного ответа, при использовании изменений используется дополнительная память.

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

Комментарии? Улучшения?

Ответ 7

Я был после программы для разграничения больших файлов без исчерпания памяти, но не нашел ничего подходящего для моих целей. Мне не интересно использовать diff для исправления (тогда я бы, вероятно, использовал rdiff от librdiff), но для визуального контроля различий, возможно, превратив их в word-diffs с помощью dwdiff --diff-input (который читает унифицированный формат diff ) и, возможно, собирая слово-diffs как-то.

(Мой типичный прецедент: у меня есть инструмент NLP, который я использую для обработки большого текстового содержимого. Я запускаю его один раз, получаю файл длиной 122760246 строк, я делаю изменения в своем инструменте, запускаю его снова, получаю файл, который отличается как каждый миллион строк, может быть, две вставки и удаление, или только одна строка отличается от такого рода.)

Поскольку я ничего не мог найти, я просто сделал немного script https://github.com/unhammer/diff-large-files - он работает (dwdiff принимает его как входной), он достаточно быстро (быстрее, чем xz-процесс, который часто запускается после него в конвейере), и, самое главное, он не исчерпывается.

Ответ 8

Я бы прочитал списки файлов на два набора и нашел те имена файлов, которые являются уникальными для любого списка.

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