Разность может быть разбита в ее собственной игре?

Это очень субъективный вопрос, но лично я бы порекомендовал Django. Python - очень хороший язык для использования, а среда Django небольшая, простая в использовании, хорошо документирована и также имеет довольно активное сообщество.

Этот выбор был сделан частично из-за моей неприязни к PHP, поэтому примите рекомендацию с щепоткой соли.

10
задан John Kugelman supports Monica 20 June 2009 в 04:22
поделиться

6 ответов

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

9
ответ дан 3 December 2019 в 18:00
поделиться

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

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

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

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

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

9
ответ дан 3 December 2019 в 18:00
поделиться

С теоретической точки зрения сравнение расстояния редактирования между двумя строками (потому что здесь есть строки на забавном языке, где «символ» - это имя файла) не может быть выполнено O (m + п). Но здесь у нас есть упрощения.

Реализация алгоритма в вашем случае (должна содержать ошибки):

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

2
ответ дан 3 December 2019 в 18:00
поделиться

Если вы согласны с тем, что словари (хеш-карты) занимают 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), если они связаны списками, что на самом деле неверно ... но в любом случае это идея.

1
ответ дан 3 December 2019 в 18:00
поделиться

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

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

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

2
ответ дан 3 December 2019 в 18:00
поделиться

Уточнение ответа 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

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

0
ответ дан 3 December 2019 в 18:00
поделиться
Другие вопросы по тегам:

Похожие вопросы: