Какой эффективный способ удалить подстроки?

Question

У меня есть длинная строка и список [end-index, string], например:

long_sentence = "This is a long long long long sentence"
indices = [[6, "is"], [8, "is a"], [18, "long"], [23, "long"]]

Элемент 6, "is" указывает, что 6 является конечным индексом слова "is" встрока.В конце я хочу получить следующую строку:

>> print long_sentence
This .... long ......... long sentence"

Я попробовал такой подход:

temp = long_sentence
for i in indices:
    temp = temp[:int(i[0]) - len(i[1])] + '.'*(len(i[1])+1) + temp[i[0]+1:]

Хотя это, кажется, работает, это занимает исключительно много времени (более 6 часов на 5000 строк в файле размером 300 МБ).Есть ли способ ускорить это?

Answer 1

Вы можете избежать поведения O (n), используя наборы для тестирования членства и str.join для объединения результатов:

>>> redacts = set()
>>> indices = [[6, "is"], [8, "is a"], [18, "long"], [23, "long"]]
>>> for end, substr in indices:
        redacts.update(range(end-len(substr)+1, end+1))
>>> ''.join([('.' if i in redacts else c) for i, c in enumerate(long_sentence)])
'This .... long .... .... long sentence'

В качестве альтернативы, вы можете использовать bytearray , который позволяет вам изменять "строку" на месте:

>>> arr = bytearray(long_sentence)
>>> for end, substr in indices:
        arr[end-len(substr)+1: end+1] = '.' * len(substr)
>>> str(arr)
'This .... long .... .... long sentence'

Последний метод работает только для не-юникодных строк.

Answer 2

Я бы в первую очередь сосредоточился на написании самого чистого и удобочитаемого лаконичного кода, а затем на оптимизации; и это именно тот подход, который вы выбрали, браво! 6 часов кажутся несостоятельными и время для оптимизации. Вы четко отделили время создания замещающей строки от времени, необходимого для генерации списка индексов?

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

Answer 3

Вы можете выполнить замену символов с помощью изменяемого стандарта array типа:

>>> import array

>>> long_sentence = "This is a long long long long sentence"
>>> indices = [[6, "is"], [8, "is a"], [18, "long"], [23, "long"]]

>>> temp = array.array('c', long_sentence)  # Could replace long_sentence too
>>> for end, substr in indices:
...     temp[end-len(substr)+1:end+1] = array.array('c', '.'*len(substr))
...     
>>> temp
array('c', 'This .... long .... .... long sentence')

Новая строка может быть записана в выходной файл с помощью:

temp.tofile(your_file)

(Сама строка возвращается temp.tostring().)

Преимущество этого подхода состоит в том, что предотвращает создание слишком большого количества новых строк путем нарезки , что требует времени. Другое преимущество состоит в том, что он эффективен для памяти : обновление строки выполняется на месте (это показано по адресу, найденному в temp.buffer_info(), который остается постоянным). Побочным эффектом является то, что эта экономия памяти может позволить вашему компьютеру избежать перестановки и, следовательно, ускорить процесс.

Вы также можете ускорить процесс с помощью кэширования '.'*len(substr) строк через специальный класс DotString с помощью специального метода __getitem__, где DotString[4] возвращает '....' и т. Д.

PS : для большинства попыток оптимизации сначала используется профилирование . Вы можете профилировать свою программу с помощью:

python -m cProfile -o stats.prof <Python program name and arguments>

Затем вы можете проанализировать время с помощью:

python -m pstats stats.prof

Первая команда, которую вы обычно запускаете, это sort time (сортировка функций по времени, потраченному строго внутри кода функции), а затем stats 10 (первые 10 самых длинных выполнений функции).

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

PPS : тип 'c', использованный в приведенном выше примере, предназначен для байтовых строк (обычно кодирование ASCII). Строки символов (иначе говоря, строки Unicode) могут обрабатываться с 'u'.

Answer 4

Каждый раз, когда вы делаете это temp = temp... назначение, Python должен создавать новую строку (потому что строки Python являются неизменяемыми).

Вместо этого вы можете превратить строку в список символов, затем обработать список символов и затем снова объединить этот список в строку.

long_list = list(long_sentence)
for end, repstr in indices:
    long_list[end-len(repstr):end] = ['.'] * len(repstr)
new_sentence = ''.join(long_list)