Составление строк из множества частей

Роберто Иерусалимши рассказывает, как эффективно соединять немодифицируемые строки.
Несмотря на то, что код написан на Lua, алгоритм подойдёт и для других языков, в которых строки нельзя изменять.

Пролог

В Lua, «накопление» результатирующей строки (т.е. цикл с телом вида s = s..x) может быть крайне затратным по ресурсам. Данная записка описывает эффективный способ создания строки по частям в Lua.

Проблема

Допустим, что вы составляете строку по частям, например, считывая из файла строку за строкой. Типичный код может выглядеть так:

-- WARNING: bad code ahead!!
local buff = ""
while 1 do
  local line = read()
  if line == nil then break end
  buff = buff..line.."\n"
end

Несмотря на невинный вид, такой код на Lua может вызвать существенную потерю производительности для больших файлов: например, для чтения 350Кб файла требуется почти минута.

Часто это не проблема. Для маленьких строк подобный цикл это нормально. Чтобы прочитать файл целиком, можно использовать опцию «*all», которая позволит считать файл целиком. Но иногда такого простого решения нет. В таком случае, единственным решением является более эффективный алгоритм для этой проблемы. Здесь мы покажем его (алгоритм, не проблему).

Решение

Сердцем алгоритма является стек, который хранит большие строки внизу, а маленькие строки приходят сверху. Главный инвариант такого стека похож на популярную (среди программистов) «Ханойскую Башню»: строка в стеке не может находиться поверх более короткой. Когда новая строка помещается поверх более короткой, тогда (и только тогда) алгоритм объединяет их вместе. Объединение строк создаёт большую строку, которая может быть больше, чем её соседка с нижнего этажа. Если такое произошло, то полученная строка и соседка снизу также объединяются. Эти объединения идут вниз по стеку, пока цикл не достигнет большей строки или дна стека.

function newBuffer ()
  return {n=0}     -- 'n' counts number of elements in the stack
end

function addString (stack, s)
  tinsert(stack, s)       -- push 's' into the top of the stack
  for i=stack.n-1, 1, -1 do
    if strlen(stack[i]) > strlen(stack[i+1]) then break end
    stack[i] = stack[i]..tremove(stack)
  end
end

Чтобы получить окончательный результат, нам надо просто объединить все строки сверху до низу:

function toString (stack)
  for i=stack.n-1, 1, -1 do
    stack[i] = stack[i]..tremove(stack)
  end
  return stack[1]
end

Используя нашу новую структуру данных, мы можем переписать программу следующим образом:

local s = newBuffer()
while 1 do
  local line = read()
  if line == nil then break end
  addString(s, line.."\n")
end
s = toString(s)

Эта программа уменьшила время чтения 350Кб файла с 40 секунд до 0.5 секунды. Вызов read "*all" всё ещё быстрей, выполняя то же самое за 0.02 секунды).

Объяснение

Чтобы понять, что происходит, когда мы применяем наивный подход, предположим, что мы в середине процесса чтения; buff уже содержит строку размером 50Кб и каждая строка размером в 20 байт. После операции конкатенации

buff = buff..line.."\n"

переменная buff содержит уже 50020 байт, а старая строка стала мусором. После двух итераций цикла, buff уже содержит 50040 байт, и уже две строки образуют больше чем 100Кб мусора. Таким образом, Lua решает, совершенно правильно, что пора запустить сборщик мусора, и освобождает эти 100Кб. Проблема в том, что это происходит каждые две итерации, и Lua запустит сборщик мусора две тысячи раз до того, как закончится цикл. И даже со всеми этими действиями, потребление памяти будет в три раза больше, чем размер файла. И что ещё хуже, каждая конкатенация должна скопировать содержимое всей строки (50Кб и больше) в новую строку.

Эта проблема не только Lua: другие языки с настоящим сборщиком мусора, и где строки немодифицируемые объекты, ведут себя также (самый известный из которых Java).

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

P.S.

Примеры даны на достаточно старой версии Lua, и я (Xitsa) их не стал менять, так как смысл алгоритма достаточно ясен.