[Перевод] Эффективная работа со строками в JavaScript03.12.2022 01:17

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

Что нужно знать о строках с позиции эффективности их использования? Во первых, строки относятся к примитивным типам данных. Во вторых, значения примитивных (простых) типов данных, в отличии от составных, таких как массивы и структуры не изменяемы. Это значит, что если вы присвоили значение переменной строкового типа один раз, то в дальнейшем эту строку изменить невозможно. Однако такое утверждение может удивить. Что это значит на практике? Если, например, выполнить этот код: 

let hello = "Hello";
hello += " world";
console.log(hello);

то в консоли однозначно появится Hello world, то есть строковая переменная hello изменила свое значение. Как строковая переменная может быть неизменяемой и измениться одновременно?

Дело в том, что интерпретатор языка в случае со строками не добавляет одну строку к другой напрямую. Вместо этого, он создает третью строку в памяти, затем копирует обе строки «Hello» и » world» в эту новую строку и перенаправляет переменную «hello» чтобы она указывала на эту новую строку. Соответственно, значение новой строки устанавливается один раз, а значения первых двух не изменяются и таким образом правило неизменяемости строк выполняется.

Вот как процесс объединения строк выглядит полностью:

3437cc2454accdfb7d76b1756c3871ab.png

Как вы думаете, что в этом процессе плохого? Это крайне не эффективный алгоритм. Он выполняет больше действий чем необходимо и использует в два раза больше памяти чтобы хранить одну и ту же строку. Конечно это не является проблемой если нужно просто объединить две строки. Проблемы могут появиться при необходимости строить большие строки. Например, если нужно динамически создать HTML-текст страницы из массива данных, поступающих из внешнего источника используя цикл по этому массиву. В этом случае, вся создаваемая строка будет полностью копироваться в новую на каждой итерации цикла. Рассмотрим простой пример такого цикла: 

let str = "Hello";

console.log("START",new Date().toUTCString());

for (let index=0;index<100000000;index++) {
    str += "!";
}

console.log("END",new Date().toUTCString());
console.log(str.length);

Этот код создает строку «Hello» и затем добавляет к ней строку »!» сто миллионов раз. В реальных приложениях вместо »!» могут быть реальные данные из внешнего массива. Также, этот код выводит текущее время до начала цикла и после него. Таким образом можно узнать сколько времени требуется на выполнение этого кода. В завершении он выводит длину итоговой строки. Когда я запустил это в Google Chrome, то получил следующий вывод в консоли:

104dc11ffa0f770005f1037f689c975c.png

Данная операции выполнилась за 1 минуту 26 секунд и выдала корректную длину строки. Однако, когда я запустил это на другом компьютере, этот код убил текущую вкладку в браузере и вывел вот такое:

38348bc0b2089d2b77fd3d80f983e3e6.png

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

Увидев все это возникает желание исправить ситуацию и добавлять строку к строке напрямую. В других языках программирования, в таких как Java или Go существуют вспомогательные объекты StringBuilder или StringBuffer, которые именно это и делают. Они позволяют конструировать строки через изменяемые типы данных, такие как массивы. Однако в JavaScript этого нет, но идею несложно реализовать самостоятельно, что и будет сделано далее.

Вернемся к началу и запишем строку «hello» следующим образом: 

let hello = ["Hello"];

Переменная hello это не строка, а массив со строкой. Массивы изменяемы и если выполнить: 

hello.push(" world");

то произойдет именно то что написано и больше ничего: строка » world» добавится в массив после строки «Hello» и массив будет содержать следующее: 

["Hello"," world"]

Таким образом можно добавлять любое количество строк и Javascript будет выполнять лишь одну операцию для каждого добавления. Однако в конце, чтобы получить строку, придется объединить массив с помощью операции join: 

hello = hello.join("");
console.log(hello);

Этот код объединил массив в строку и вывел «Hello world» в консоль. Конечно в момент операции «join» происходит то же самое что и при объединении строк: создается новая строка, в нее копируются все элементы массива и затем эта строка присваивается переменной «hello». Однако это происходит всего один раз, а не каждый раз при добавлении новой строки.

Такой способ позволяет значительно ускорить конструирования строк в цикле. Перепишем пример с циклом через массив: 

let str = ["Hello"];

console.log("START",new Date().toUTCString());

for (let index=0;index<100000000;index++) {
    str.push("!");
}

str = str.join("");

console.log("END",new Date().toUTCString());
console.log(str.length);

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

5e3dcae57c175b58a5dd0015ae276024.png

Результат был достигнут за 8 секунд, что в 10 раз быстрее чем при обычном объединении строк.

Это является примером того, что иногда изменив три строки кода можно значительно увеличить производительность обработки данных. В реальной жизни, я столкнулся с ситуацией когда владелец web-сайта из-за медленной загрузки строки сначала кэшировал данные на CloudFlare, а потом на полном серьезе планировал переходить на AWS для увеличения пропускной способности и балансировки нагрузки. Однако нужно было просто провести code review для фронтенда.

Вы можете использовать этот метод для конструирования строк из массивов внешних данных, размер которых не известен. Просто добавляйте строки в массив, а в самом конце объединяйте этот массив в строку.

То что было сделано можно рассматривать как базовую реализацию StringBuilder для Javascript с одной лишь функцией — добавление подстроки. В качестве домашней работы можете оформить это в виде класса с разными функциями для работы с подстроками, такими как «добавить», «изменить», «удалить» и «преобразовать в строку».

При добавлении элементов в массив важно помнить о существующих ограничениях на количество элементов массива, так как если их не учитывать, то можно столкнуться с ошибкой «RangeError: invalid array range». Подробнее об ограничениях можно узнать здесь: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Invalid_array_length. Поэтому если количество строк, которые нужно добавлять в цикле превышает эти ограничения, то придется периодически сбрасывать массив во временные строковые буферы и потом эти буферы объединять.

Приведенный в начале алгоритм объединения строк в Javascript не претендует на академическую точность по некоторым причинам. Разные реализации движков Javascript могут использовать различные оптимизации по работе со строками и механизмы работы с памятью могут отличаться. Однако не стоит расчитывать на то что ваш код всегда будет запускаться в таких движках. Например, в последней версии Google Chrome на момент написания этого текста объединение строк работало так, как показано на скриншотах выше. Поэтому целью данной статьи является показать как работать со строками эффективнее независимо от того, как это реализовано по умолчанию.

Существуют и более эффективные алгоритмы работы со строками, основанные не только на массивах. Наиболее быстрый из них построен на структуре данных Rope. Она используется для ускорения вставки и удаления подстрок в огромных строках. Подробнее о самой структуре можно прочитать в Википедии: https://en.wikipedia.org/wiki/Rope_(data_structure) . Также думаю не сложно будет найти описания на русском языке. Это несколько сложнее для понимания и использования чем метод описанный в этой статье, однако можно воспользоваться одной из готовых библиотек, которые реализуют Rope на JavaScript:

https://github.com/component/rope
https://github.com/josephg/jumprope

Спасибо, надеюсь это поможет вам в работе. Если есть вопросы или дополнения, пишите в комментариях.

© Habrahabr.ru