Я не думаю, что есть лучший или более быстрый способ сделать это, чем то, что вы делаете в первом подходе.(Обновление: есть, см. Ниже.) Сохранение строк из small.txt в set и итерирование строк в big.txt, проверка, находятся ли они в этом наборе, будет иметь сложность O(b), с b это число строк в big.txt.
Что вы, похоже, пытаетесь уменьшить, до O(s*logb), где s - это количество строк в small.txt, используя бинарный поискпроверить каждую строку в small.txt, находится ли она в big.txt и затем удалить / перезаписать ее.
Это будет хорошо работать, если все строки будут в list с произвольным доступом к любому массиву,но у вас есть только файл, который не разрешает произвольный доступ к какой-либо строке.Он действительно , однако разрешает произвольный доступ к любому символу с file.seek, который (по крайней мере, в некоторых случаях?) представляется равным O (1) .Но тогда вам все равно придется найти предыдущий разрыв строки в этой позиции, прежде чем вы сможете фактически прочитать эту строку.Кроме того, вы не можете просто заменить строки на пустые строки, но вы должны перезаписать число тем же количеством символов, например пробелами.
Так что, да, теоретически это можно сделать в O(s*logb), еслиВы делаете следующее:
- реализуете бинарный поиск, ища не по строкам, а по символам большого файла
- для каждой позиции, возвращайтесь к последнему разрыву строки, затемпрочитайте строку, чтобы получить число
- , попробуйте еще раз в нижней / верхней половине, как обычно, с двоичным поиском
- , если число найдено, замените столько пробелов, сколькоцифры в числе
- повторяются со следующим номером из небольшого файла
В моей системе чтение и запись файла с 10 миллионами строк чисел занимало всего 3 секунды каждаяили около 8 секунд с fileinput.input и print.Таким образом, ИМХО, это на самом деле не стоит усилий, но, конечно, это может зависеть от того, как часто вы должны делать эту операцию.
Хорошо, так что мне стало любопытно - и кому нужнав любом случае, обеденный перерыв? - поэтому я попытался реализовать это ... и это работает на удивление хорошо.Это найдет указанный номер в файле и заменит его на соответствующий номер - (, а не просто пустая строка, это невозможно без перезаписи всего файла).Обратите внимание, что я не провёл тщательный тест алгоритма бинарного поиска для крайних случаев, ошибочных ошибок и т. Д.
import os
def getlineat(f, pos):
pos = f.seek(pos)
while pos > 0 and f.read(1) != "\n":
pos = f.seek(pos-1)
return pos+1 if pos > 0 else 0
def bsearch(f, num):
lower = 0
upper = os.stat(f.name).st_size - 1
while lower <= upper:
mid = (lower + upper) // 2
pos = getlineat(f, mid)
line = f.readline()
if not line: break # end of file
val = int(line)
if val == num:
return (pos, len(line.strip()))
elif num < val:
upper = mid - 1
elif num > val:
lower = mid + 1
return (-1, -1)
def overwrite(filename, to_remove):
with open(filename, "r+") as f:
positions = [bsearch(f, n) for n in to_remove]
for n, (pos, length) in sorted(zip(to_remove, positions)):
print(n, pos)
if pos != -1:
f.seek(pos)
f.write("-" * length)
import random
to_remove = [random.randint(-500, 1500) for _ in range(10)]
overwrite("test.txt", to_remove)
Сначала будут собраны все позиции, которые нужно перезаписать, а затем будет выполнена реальная перезапись.во втором, в противном случае бинарный поиск будет иметь проблемы, когда он попадет в одну из ранее «удаленных» строк.Я проверил это с помощью файла, содержащего все числа от 0 до 1000 в отсортированном порядке и список случайных чисел (как внутри, так и за его пределами), которые нужно удалить, и это работало просто отлично.
ОбновлениеТакже проверил его с файлом со случайными числами от 0 до 100 000 000 в отсортированном порядке (944 МБ) и перезаписал 100 случайных чисел, и он сразу же завершился, так что это действительно должно быть O (s * logb), по крайней мере, в моей системе (сложность file.seek может зависеть от файловой системы, типа файла и т. д.).
Функцию bsearch можно также обобщить для принятия другого параметра value_function вместо жесткого кодирования val = int(line).Затем его можно использовать для бинарного поиска в произвольных файлах, например, в огромных словарях, базах данных генов, CSV-файлах и т. Д., Если строки отсортированы по той же функции значения.