Эта проблема является хорошо известной / «классической» проблемой оптимизации для JavaScript, вызванной тем, что строки JavaScript являются «неизменяемыми», а добавление путем конкатенации даже одного символа в строку требует создания, включая выделение памяти для и копирование в целую новую строку.
К сожалению, принятый ответ на этой странице неправильный, где «неправильный» означает с коэффициентом производительности 3x для простых односимвольных строк и 8x-97x для коротких строк, повторяющихся больше раз, до 300x для повторяющихся предложений, и бесконечно неверно, когда принимается предел отношений сложности алгоритмов, когда n уходит в бесконечность. Кроме того, на этой странице есть другой ответ, который является почти правильным (на основе одного из многих поколений и вариантов правильного решения, распространенного в Интернете за последние 13 лет). Однако это «почти правильное» решение не учитывает ключевой момент правильного алгоритма, что приводит к снижению производительности на 50%.
Результаты JS-производительности для принятого ответа, другого ответа с наибольшим результатом (на основе ухудшенной версии исходного алгоритма в этом ответе) и этого ответа с использованием моего алгоритма, созданного 13 лет назад
~ октябрь 2000 г. Я опубликовал алгоритм для этой точной задачи, который был широко адаптирован, модифицирован, а затем, в конце концов, плохо понят и забыт. Чтобы исправить эту проблему, в августе 2008 года я опубликовал статью http://www.webreference.com/programming/javascript/jkm3/3.html, объясняющую алгоритм и использующую его в качестве примера простых оптимизаций JavaScript общего назначения. К настоящему времени Web Reference удалил мою контактную информацию и даже мое имя из этой статьи. И снова, алгоритм был широко адаптирован, модифицирован, затем плохо понят и в значительной степени забыт.
Исходный алгоритм JavaScript повторения / умножения строк
Джозеф Майерс, около Y2K как функция умножения текста в Text.js;
опубликовано в августе 2008 г. в этой форме посредством веб-ссылки:
http://www.webreference.com/programming/javascript/jkm3/3.html (
статья использовала функцию в качестве примера оптимизации JavaScript,
который является единственным для странного имени "stringFill3.")
/*
* Usage: stringFill3("abc", 2) == "abcabc"
*/
function stringFill3(x, n) {
var s = '';
for (;;) {
if (n & 1) s += x;
n >>= 1;
if (n) x += x;
else break;
}
return s;
}
В течение двух месяцев после публикации этой статьи этот же вопрос был опубликован в Stack Overflow и оставался у меня под радаром до сих пор, когда, очевидно, первоначальный алгоритм для этой проблемы снова был забыт. Лучшее решение, доступное на этой странице переполнения стека, - это модифицированная версия моего решения, возможно, разделенная несколькими поколениями. К сожалению, модификации разрушили оптимальность решения. Фактически, изменяя структуру цикла по сравнению с моим оригиналом, модифицированное решение выполняет совершенно ненужный дополнительный шаг экспоненциального дублирования (таким образом, объединяя наибольшую строку, использованную в правильном ответе, с самим собой дополнительное время, а затем отбрасывая его).
Ниже следует обсуждение некоторых оптимизаций JavaScript, связанных со всеми ответами на эту проблему и на благо всех.
Техника: избегайте ссылок на объекты или свойства объектов
Чтобы проиллюстрировать, как работает этот метод, мы используем реальную функцию JavaScript, которая создает строки любой необходимой длины. И, как мы увидим, можно добавить больше оптимизаций!
Функция, подобная используемой здесь, заключается в создании отступов для выравнивания столбцов текста, для форматирования денег или для заполнения данных блока до границы. Функция генерации текста также позволяет вводить переменную длину для тестирования любой другой функции, которая работает с текстом. Эта функция является одним из важных компонентов модуля обработки текста JavaScript.
По мере продолжения мы рассмотрим еще два наиболее важных метода оптимизации, развивая исходный код в оптимизированном алгоритме создания строк. Конечный результат - промышленная мощная, высокопроизводительная функция, которую я использовал повсюду - выравнивание цен на товары и итоговых сумм в формах заказа JavaScript, форматирование данных и форматирование сообщений электронной почты / текстовых сообщений и многие другие применения.
Оригинальный код для создания строк stringFill1()
function stringFill1(x, n) {
var s = '';
while (s.length < n) s += x;
return s;
}
/* Example of output: stringFill1('x', 3) == 'xxx' */
Синтаксис здесь понятен. Как вы можете видеть, мы уже использовали локальные переменные функции, прежде чем перейти к дальнейшей оптимизации.
Имейте в виду, что в коде есть одна невинная ссылка на свойство объекта s.length, которое ухудшает его производительность. Еще хуже то, что использование этого свойства объекта уменьшает простоту программы, предполагая, что читатель знает о свойствах строковых объектов JavaScript.
Использование этого свойства объекта нарушает универсальность компьютерной программы. Программа предполагает, что x должна быть строкой длины один. Это ограничивает применение функции stringFill1() чем угодно, кроме повторения отдельных символов. Даже отдельные символы не могут быть использованы, если они содержат несколько байтов, таких как сущность HTML .
Худшая проблема, вызванная этим ненужным использованием свойства объекта, заключается в том, что функция создает бесконечный цикл при тестировании на пустой входной строке x. Чтобы проверить общность, примените программу к минимально возможному количеству ввода. У программы, которая аварийно завершает работу при запросе превышения объема доступной памяти, есть оправдание. Такая программа, которая вылетает, когда ее просят ничего не производить, недопустима. Иногда красивый код - это ядовитый код.
Простота может быть неоднозначной целью компьютерного программирования, но, как правило, это не так. Когда программе не хватает разумного уровня общности, нельзя сказать: «Программа достаточно хороша, насколько это возможно». Как видите, использование свойства string.length не позволяет этой программе работать в общих настройках, и фактически неверная программа готова вызвать сбой браузера или системы.
Есть ли способ улучшить производительность этого JavaScript, а также решить эти две серьезные проблемы?
Конечно. Просто используйте целые числа.
Оптимизированный код для создания строк stringFill2()
function stringFill2(x, n) {
var s = '';
while (n-- > 0) s += x;
return s;
}
Временной код для сравнения stringFill1() и stringFill2()
function testFill(functionToBeTested, outputSize) {
var i = 0, t0 = new Date();
do {
functionToBeTested('x', outputSize);
t = new Date() - t0;
i++;
} while (t < 2000);
return t/i/1000;
}
seconds1 = testFill(stringFill1, 100);
seconds2 = testFill(stringFill2, 100);
Успех до сих пор stringFill2()
stringFill1() занимает 47,297 микросекунд (миллионные доли секунды), чтобы заполнить 100-байтовую строку, а stringFill2() занимает 27,68 микросекунд, чтобы сделать то же самое. Это почти удваивает производительность, избегая ссылки на свойство объекта.
Техника: избегайте добавления коротких строк в длинные строки
Наш предыдущий результат выглядел хорошо - на самом деле очень хорошо. Улучшенная функция stringFill2() намного быстрее благодаря использованию наших первых двух оптимизаций. Поверите ли вы этому, если я скажу вам, что его можно улучшить во много раз быстрее, чем сейчас?
Да, мы можем достичь этой цели. Прямо сейчас нам нужно объяснить, как мы не добавляем короткие строки в длинные.
Краткосрочное поведение представляется довольно хорошим по сравнению с нашей первоначальной функцией. Специалистам по информатике нравится анализировать «асимптотическое поведение» алгоритма функции или компьютерной программы, что означает изучение его долговременного поведения путем тестирования его с большими входами. Иногда, не проводя дальнейшие тесты, никто не узнает, как можно улучшить компьютерную программу. Чтобы увидеть, что произойдет, мы собираемся создать 200-байтовую строку.
Проблема, которая появляется с stringFill2()
Используя нашу функцию синхронизации, мы находим, что время увеличивается до 62,54 микросекунд для 200-байтовой строки по сравнению с 27,68 для 100-байтовой строки. Кажется, что нужно удвоить время, чтобы выполнить вдвое больше работы, но вместо этого оно утроится или увеличится в четыре раза. Из опыта программирования этот результат кажется странным, потому что, во всяком случае, функция должна быть немного быстрее, поскольку работа выполняется более эффективно (200 байт на вызов функции, а не 100 байт на вызов функции). Эта проблема связана с коварным свойством строк JavaScript: строки JavaScript являются «неизменяемыми».
Неизменяемый означает, что вы не можете изменить строку после ее создания. Добавляя по одному байту за раз, мы не тратим еще один байт на усилия. На самом деле мы воссоздаем всю строку плюс еще один байт.
Фактически, чтобы добавить еще один байт к 100-байтовой строке, требуется работа в 101 байт. Давайте кратко проанализируем вычислительные затраты на создание строки размером N байт. Стоимость добавления первого байта составляет 1 единицу вычислительного усилия. Стоимость добавления второго байта - не одна единица, а 2 единицы (копирование первого байта в новый строковый объект, а также добавление второго байта). Третий байт требует 3 единицы стоимости и т. Д.
C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). Символ O(N^2) произносится как Big O из N в квадрате, и это означает, что вычислительные затраты в долгосрочной перспективе пропорциональны квадрату длины строки. Для создания 100 символов требуется 10000 единиц работы, а для создания 200 символов - 40000 единиц работы.
Именно поэтому создание 200 символов заняло более чем вдвое больше времени, чем 100 символов. На самом деле, это должно было занять в четыре раза больше времени. Наш опыт программирования был верным в том, что работа для более длинных строк выполняется немного более эффективно, и, следовательно, это заняло всего три раза больше времени. Как только издержки на вызов функции становятся незначительными в зависимости от длины создаваемой строки, на самом деле создание строки в два раза дольше.
(Историческая справка: этот анализ не обязательно применяется к строкам в исходном коде, например html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n', поскольку компилятор исходного кода JavaScript может объединять строки перед тем, как превратить их в строковый объект JavaScript. Всего несколько лет назад реализация JavaScript в KJS зависала или зависала при загрузке длинных строк исходного кода, соединенных знаками плюса. Поскольку время вычислений составляло O(N^2), было не сложно создать веб-страницы, которые перегружали бы веб-браузер Konqueror или Safari, Я использовал ядро движка KJS JavaScript. Впервые я столкнулся с этой проблемой, когда разрабатывал язык разметки и синтаксический анализатор языка разметки JavaScript, а затем обнаружил причину проблемы, когда писал свой сценарий для JavaScript Includes.)
Очевидно, что это быстрое снижение производительности является огромной проблемой. Как мы можем справиться с этим, учитывая, что мы не можем изменить способ обработки строк в JavaScript как неизменных объектов в JavaScript? Решение состоит в том, чтобы использовать алгоритм, который воссоздает строку как можно меньше раз.
Чтобы уточнить, наша цель состоит в том, чтобы избежать добавления коротких строк в длинные строки, поскольку для добавления короткой строки также должна быть продублирована вся длинная строка.
Как работает алгоритм, чтобы избежать добавления коротких строк в длинные строки
Вот хороший способ уменьшить количество раз, когда создаются новые строковые объекты. Объедините более длинные строки вместе, чтобы к выводу добавлялось более одного байта за раз.
Например, чтобы сделать строку длиной N = 9:
x = 'x';
s = '';
s += x; /* Now s = 'x' */
x += x; /* Now x = 'xx' */
x += x; /* Now x = 'xxxx' */
x += x; /* Now x = 'xxxxxxxx' */
s += x; /* Now s = 'xxxxxxxxx' as desired */
Для этого требовалось создать строку длины 1, создать строку длины 2, создать строку длины 4, создать строку длины 8 и, наконец, создать строку длины 9. Сколько затрат мы сэкономили
Старая стоимость C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.
Новая стоимость C(9) = 1 + 2 + 4 + 8 + 9 = 24.
Обратите внимание, что мы должны были добавить строку длины 1 к строке длины 0, затем строку длины 1 к строке длины 1, затем строку длины 2 к строке длины 2, затем строку длины 4 до строки длины 4, затем строки длины 8 до строки длины 1, чтобы получить строку длины 9. То, что мы делаем, можно суммировать, избегая добавления коротких строк в длинные строки, или, другими словами, пытаясь объединить строки одинаковой или почти равной длины.
Для старых вычислительных затрат мы нашли формулу N(N+1)/2. Есть ли формула для новой стоимости? Да, но это сложно. Важно то, что это O(N), поэтому удвоение длины строки примерно вдвое увеличит объем работы, а не увеличит ее в четыре раза.
Код, который реализует эту новую идею, почти так же сложен, как формула для вычислительных затрат. Когда вы читаете это, помните, что >>= 1 означает сдвиг вправо на 1 байт. Таким образом, если n = 10011 является двоичным числом, то n >>= 1 приводит к значению n = 1001.
Другая часть кода, которую вы можете не распознать, - это побитовый оператор и оператор, написанный &. Выражение n & 1 оценивает true, если последняя двоичная цифра n равна 1, и false, если последняя двоичная цифра n равна 0.
Новая высокоэффективная функция stringFill3()
function stringFill3(x, n) {
var s = '';
for (;;) {
if (n & 1) s += x;
n >>= 1;
if (n) x += x;
else break;
}
return s;
}
Это выглядит некрасиво для неподготовленного глаза, но его производительность - не что иное, как прекрасное.
Посмотрим, насколько хорошо работает эта функция. После просмотра результатов, скорее всего, вы никогда не забудете разницу между алгоритмом O(N^2) и алгоритмом O(N).
stringFill1() занимает 88,7 микросекунды (миллионные доли секунды) для создания 200-байтовой строки, stringFill2() - 62,54, а stringFill3() - только 4,608. Что сделало этот алгоритм намного лучше? Все функции воспользовались преимуществом использования переменных локальной функции, но использование второго и третьего методов оптимизации добавило к двадцатикратному улучшению производительности stringFill3().
Более глубокий анализ
Что заставляет эту особую функцию вырывать конкуренцию из воды?
Как я уже говорил, причина того, что обе эти функции, stringFill1() и stringFill2(), выполняются так медленно, заключается в том, что строки JavaScript являются неизменяемыми. Память нельзя перераспределить, чтобы допустить добавление еще одного байта за раз к строковым данным, хранящимся в JavaScript. Каждый раз, когда в конец строки добавляется еще один байт, вся строка восстанавливается от начала до конца.
Таким образом, чтобы улучшить производительность скрипта, нужно предварительно вычислить строки большей длины, заранее объединив две строки вместе, а затем рекурсивно выстроив желаемую длину строки.
Например, для создания 16-буквенной байтовой строки сначала будет вычислена двухбайтовая строка. Затем двухбайтовая строка будет повторно использована для предварительного вычисления четырехбайтовой строки. Затем четырехбайтовая строка будет повторно использована для предварительного вычисления восьмибайтовой строки. Наконец, две восьмибайтовые строки будут повторно использованы для создания желаемой новой строки из 16 байтов. Всего нужно было создать четыре новые строки, одну из длины 2, одну из длины 4, одну из длины 8 и одну из длины 16. Общая стоимость составляет 2 + 4 + 8 + 16 = 30.
В долгосрочной перспективе эта эффективность может быть рассчитана путем сложения в обратном порядке и использования геометрического ряда, начинающегося с первого члена a1 = N и имеющего общее отношение r = 1/2. Сумма геометрического ряда определяется как a_1 / (1-r) = 2N.
Это более эффективно, чем добавление одного символа для создания новой строки длиной 2, создание новой строки длиной 3, 4, 5 и т. Д. До 16. В предыдущем алгоритме использовался этот процесс добавления одного байта. за один раз, и общая стоимость этого будет n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.
Очевидно, что 136 - намного большее число, чем 30, и поэтому предыдущий алгоритм требует гораздо, намного больше времени для построения строки.
Чтобы сравнить два метода, вы можете увидеть, насколько быстрее рекурсивный алгоритм (также называемый «разделяй и властвуй») на строке длиной 123 457. На моем компьютере с FreeBSD этот алгоритм, реализованный в функции stringFill3(), создает строку за 0,001058 секунд, в то время как исходная функция stringFill1() создает строку за 0,0808 секунды. Новая функция в 76 раз быстрее.
Разница в производительности увеличивается по мере увеличения длины строки. В пределе, когда создаются все большие и большие строки, исходная функция ведет себя примерно как C1 (постоянные) времена N^2, а новая функция ведет себя как C2 (постоянные) времена N.
Из нашего эксперимента мы можем определить значение C1, равное C1 = 0.0808 / (123457)2 = .00000000000530126997, и значение C2, равное C2 = 0.001058 / 123457 = .00000000856978543136. За 10 секунд новая функция может создать строку, содержащую 1 166 890 359 символов. Чтобы создать эту же строку, старой функции потребуется 7 218 384 секунд времени.
Это почти три месяца по сравнению с десятью секундами!
Я отвечаю только (с опозданием на несколько лет), потому что мое первоначальное решение этой проблемы распространялось по Интернету уже более 10 лет, и, видимо, его все еще плохо понимают те немногие, кто его помнит. Я думал, что, написав статью об этом здесь, я помогу:
Оптимизация производительности для высокоскоростного JavaScript / Страница 3
К сожалению, некоторые из других решений, представленных здесь, все еще являются теми, которые потребовали бы три месяца, чтобы произвести тот же объем вывода, который правильное решение создает за 10 секунд.
Я хочу потратить время на то, чтобы воспроизвести часть статьи здесь в качестве канонического ответа о переполнении стека.
Обратите внимание, что наиболее эффективный алгоритм здесь явно основан на моем алгоритме и, вероятно, унаследован от чужой адаптации 3-го или 4-го поколения. К сожалению, модификации привели к снижению его производительности. Вариант моего решения, представленный здесь, возможно, не понимал моего запутанного выражения for (;;), которое выглядит как основной бесконечный цикл сервера, написанного на C, и которое было просто разработано, чтобы позволить аккуратно расположить оператор останова для управления циклом, наиболее компактный способ избежать экспоненциальной репликации строки в одно дополнительное ненужное время.