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

http://www.lua.org/notes/ltn009.html
  • Перевод
Роберто Иерусалимши рассказывает, как эффективно соединять немодифицируемые строки.
Несмотря на то, что код написан на 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) их не стал менять, так как смысл алгоритма достаточно ясен.
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 32
  • +12
    StringBuilder?
    • +3
      StringBuilder решает этот вопрос немного по другому — он внутри использует unsafe код, а преимущество этого алгоритма в том, что его можно использовать там, где это недопустимо.
      • +2
        Он использует unsafe код потому что можно. Сделать эффективную реализацию StringBuilder можно было и без этого. Кроме того есть string.Join, string.Concat. В целом, в любом нормальном языке (нормальной платформе) есть средства для эффективной склейки строк. Луа тут исключение а не правило.

        В Си++ вообще можно извратиться на шаблонах, вычислять результат лениво при приведении типа и вообще много интересных и никому не нужных вещей сделать :-)
        • +1
          В новых версиях Lua можно делать так:
            local t = {}
            for l in ... do
              table.insert(t, l)
            end
            s = table.concat(t)


          Этот текст достаточно древен (2002 год), я его перевёл, потому что алгоритм интересен.
          • +4
            Научите: чем вы раскрашиваете синтаксис для постов?
            • +3
              С помощью VIM'а, а точнее gVIM:
              Просто открываю файл с кодом, выполняю команду :TOHtml
              Потом просто выбираю код, который расположен в теге <BODY> (встаю на тег <BODY> и копирую командой "*yit)

              gVIM нужен для того, чтобы раскраска в полученном html совпала с тем, что видно на экране
              • 0
                Экспериментально выяснено, что в :TOhtml буква «h» маленькая.

                Большое спасибо.
        • 0
          Откройте исходные коды в src.zip в JDK. Нет там ни одного native метода, pure Java.
          • +2
            unsafe != native
            • 0
              да, то про .net был разговор. Тоже сразу чуть не поперхнулся — что еще за unsafe в StringBuilder.
            • –1
              Спорю на бутылку пива что напишу аналог StringBuffer-а на базе ArrayList за час (знаю медленно, но жарко тут).
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                Как забыть?
                String s = "foo";
                for (int i = 0; i < 100500; i++) {
                  s += "bar";
                }
                

                Скомпилируется в
                String s = "foo";
                for (int i = 0; i < 100500; i++) {
                  s = new StringBuilder().append(s).append("bar").toString();
                }
                

                Никакой оптимизации, новый StringBuilder объект создается на каждой итерации, причем памяти потребляется O(N2). Память конечно же вычищается, но время на это затрачивается. Или, может быть, вы что-то «такое» знаете про оптимизатор Java 1.5+?
                • 0
                  Забыть о проблеме, но не о StringBuilder.
                  String s = «foo»;
                  StringBuilder sb=new StringBuilder(s);
                  for (int i = 0; i < 100500; i++) {
                  sb.append(«bar»);
                  }
                  s=sb..toString();
                  • 0
                    При этом надо понимать, что каждый append увеличивает длину буфера, что в нашем случае приведет к большому числу перевыделений памяти под буффер. Если решается задача, например, рендеринга html страницы, как в jsp, то в качестве представления последовательности символов эффективнее использовать структуры типа ropes, на которые я ниже в комментариях давал ссылку.
            • +1
              Спасибо, принцип понятен, однако, имхо, проблема должна решаться более красивыми функциями в стандартной библиотеке. Вот пример аналогичного кода для питона, который не вызывает таких гигантских накладных расходов:
              ''.join(file("myfile",'r'))
              

              Этот код:

              1) Создаёт объект file (открывает файл на чтение)
              2) Создаёт итератор для чтения файла (это происходит потому, что класс file имеет методы для работы в качестве итератора (next,iter)
              3) Указанный итератор передаётся в функцию, которая соединяет элементы списка (или итератора, как можно догадаться). Заметим, поскольку функция join морально готова к приёму нескольких строк по-очереди, она не создаёт снова и снова immutable объекты строк, а всего лишь создаёт строку из множества фрагментов, которые ей приходят по-очереди.

              Типа так.
              • 0
                создаёт, ибо не знает размер файла и потому не может сразу выделить нужное количество памяти
                • НЛО прилетело и опубликовало эту надпись здесь
                  • 0
                    Т.е. он развернёт итератор? Плохо… Я ожидал лучше.
                    • НЛО прилетело и опубликовало эту надпись здесь
                • +4
                  мне кажется, что автор кривит душой на счет языка. В каждом языке свои особенности — в питоне, здесь уже привели пример, в дот-нете нерекомендуется использовать конкатенацию строк оператором "+" при больших объемах (проседает сильно производительность из-за реалокации). Другими словами, когда работаете со строками, не сочтите за труд понять, каким образом действует механика по работе с памятью.

                  и да, в этом алгоритме стек — слабое звено (в плане ресурсов).
                  • +2
                    Из этого примера не ясно, что надо дальше делать с полученной строкой. Если в дальнейшем нам нужно лишь итерироваться по этой строке, то стек можно и не разворачивать. Или вообще можно использовать Ropes. Кроме того, дополнительный расход памяти на стек O(числа строк в файле), или, по ощущениям, что-то вроде логарифма от числа символов в файле.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      В начале статьи нужно написать, что алгоритм связан с особенностями lua и ее сборщика мусора
                      • 0
                        А нельзя-ли просто сложить все прочитанные строки в список или массив, а потом выделить большую строку и все туда скопировать? Потребление памяти х2, зато копирование одно.
                        • 0
                          Нельзя, так как в данном случае строки модифицировать нельзя.
                        • 0
                          Мда, казалось бы, конкатенация строк — древняя задча, за жти годы должна быть изучена досконально, а во многих языках, судя по комментам — не решена (вызывать realloc() на каждое склеивание — никак не тянет на решение). Гораздо правильнее при объдинении просто добавлять кусочки в список, а при попытке прочитать значение строки — склеивать все, что накопилось.
                          • 0
                            Гораздо правильнее при объдинении просто добавлять кусочки в список, а при попытке прочитать значение строки — склеивать все, что накопилось.


                            Например, в Google V8 так и сделано, но не избавляет от проблем. Возникают другие вопросы, например, когда из кусочного представления переходить к линейному…
                          • 0
                            называть это словом «алгоритм» — перебор. скорее это кривохак для обхода особенностей языка программирования
                            • 0
                              > например, для чтения 350Кб файла требуется почти минута

                              это невероятно!

                              1 минута * 1 GHz = 60 секунд * 1 000 000 000 = 60 миллионов тактов процессора.

                              Делим на 350 Килобайт и получаем результирующее КПД… примерно 171 тысяч тактов процессора на чтение одного байта.

                              Окей, возьмём «идеальный» алгоритм.

                              350 Кб за 0.02 сек = 17 500 Кб/с.
                              Да у меня интернет быстрее, чем чтение с диска в Lua в самой оптимальной реализации.

                              О чём вообще можно говорить про такую среду исполнения?
                              Мир сошёл с ума.
                              • +1
                                >> О чём вообще можно говорить про такую среду исполнения?

                                О том, что это одна из самых быстрых сред исполнения для динамических языков =)

                                Если её кто-то неправильно использует, то это его проблема.

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