Оптимизированный алгоритм вставки строк

Question

Есть небольшая часть нашего программного обеспечения, которая вставляет строку до и после определенной совпавшей строки в огромный кусок кода (средняя длина 900000 символов).

Пример:

Lorem Ipsum - просто фиктивный текст в полиграфии и вёрстке.Лорем Ипсум был стандартным фиктивным текстом в отрасли с 1500-х годов, когда неизвестный принтер взял камбуз шрифта и скремблировал его, чтобы сделать книгу типовых образцов.Lorem Ipsum - просто дурацкий текст <span class="class1 class2">printing</span> и индустрии набора текста.У Лорема Ипсума есть <span class="class1 class2 class3">been</span> стандартный фиктивный текст отрасли <span class="class1">ever since the 1500s</span>, когда неизвестный принтер взял галеру типа и скремблировал ее, чтобы сделать книгу типовых экземпляров.Мы могли бы просто искать и заменять, но содержимое в некоторой степени семантически относительно, поэтому printing в этом случае было заменено, но не могло быть в каком-то другом месте текста.То, что мы сделали, это указатель, в котором мы хотели заменить текст, поэтому для каждой замены мы получаем начальную и конечную позиции.

Текущий код:

new_val = huge_string_goes_here
entities.each { |entity|
    add_before = "<span class=\"#{entity.getStuff}\">"
    add_after = '</span>'

    new_val.insert(entity.getStart+increment, add_before)
    increment = increment+add_before.length
    new_val.insert(entity.getEnd+increment, add_after)
    increment = increment+add_after.length
}

Анализ длиной 900000 символовСтрока занимает около 15-20 секунд.

Кто-нибудь есть какие-либо предложения о том, как мы могли бы его оптимизировать?

Спасибо

Answer 1

Если вы не хотите переходить на язык более низкого уровня, чтобы сделать это, возможно, было бы полезно изменить свое мышление, чтобы вы один раз просматривали исходную строку и записывали новую (если это могло быть заранее выделенным, тем лучше), потому что это избавило бы от необходимости перемещать все символы ~ 900000-N за точкой вставки N.

Существуют также специальные представления, в которые можно перейти, чтобы сделать такие операции очень быстрыми (например, веревки ), но вам не нужно что-то подобное для этого сценария.

РЕДАКТИРОВАТЬ: Многие старые структуры данных (и новые тоже в этом отношении), которые имеют хорошие большие значения, на практике медленны из-за гигантских постоянных факторов, которые были проигнорированы, и / или они не учитывают современную архитектуру ( например, кеши, вычисления против извлечения). Веревки кажутся слишком интенсивными по указателям, чтобы быть быстрыми на практике, и вы бы справились с чем-то вроде буфера с разрывом для общих изменений буфера.

Answer 2

Подумайте о написании модуля расширения C для Ruby , который мог бы найти для вас индексы совпадений - такая операция должна быть намного быстрее, чем с интерпретируемым кодом.Получив индексы, вы можете использовать Ruby для вставки текста до / после или, если производительность все еще нуждается в повышении, подумайте о том, чтобы сделать все это в C.

Обратите внимание, что, как и при любой оптимизации,важно убедиться, что ваша «оптимизация» на самом деле улучшает неоптимизированный код.Напишите бенчмарк для некоторых примеров и проследите, сколько времени занимает чистый код Ruby, затем запустите тот же бенчмарк, используя ваше собственное расширение, и посмотрите, действительно ли производительность лучше.

Answer 3

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