Это очень субъективный вопрос, но лично я бы порекомендовал Django. Python - очень хороший язык для использования, а среда Django небольшая, простая в использовании, хорошо документирована и также имеет довольно активное сообщество.
Этот выбор был сделан частично из-за моей неприязни к PHP, поэтому примите рекомендацию с щепоткой соли.
Это не совсем 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.
Общий алгоритм, если первый файл имеет длину м
, а второй файл имеет длину n
равно O (m + n)
по мере необходимости.
Примечание: этот алгоритм предполагает, что набор данных удобно размещается в физической памяти, чтобы быть быстрым.
Если набор данных не может легко поместиться в памяти, поиск может быть реализован с использованием некоторого варианта B-Tree с подкачкой на диск. Тогда сложность составит O (mlog m)
для начальной настройки и O (n log m)
для сравнения файлов друг с другом.
С теоретической точки зрения сравнение расстояния редактирования между двумя строками (потому что здесь есть строки на забавном языке, где «символ» - это имя файла) не может быть выполнено 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)
инструкции. Память освобождается после завершения блока, так что это не так уж важно, если у вас действительно есть только небольшие изменения. Конечно, производительность в худшем случае такая же плохая, как и при использовании универсального метода.
Если вы согласны с тем, что словари (хеш-карты) занимают 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), если они связаны списками, что на самом деле неверно ... но в любом случае это идея.
На практике разница логарифмических коэффициентов во времени сортировки, вероятно, несущественна - sort
может отсортировать сотни тысяч строк за несколько секунд. Так что на самом деле вам не нужно писать какой-либо код:
sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes
Я не утверждаю, что это обязательно самое быстрое решение - я думаю, что принятый ответ Бена С. будет, по крайней мере, выше некоторого значения N. Но это определенно самый простой способ масштабирования до любого количества файлов,
Уточнение ответа 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
Комментарии? Улучшения?