Эта проблема является известной / «классической» проблемой оптимизации для JavaScript, вызванной тем, что строки JavaScript являются «неизменными», а добавление путем конкатенации даже одного символа в строку требует создания, включая выделение памяти и копирования , целая новая строка.
К сожалению, принятый ответ на этой странице неверен, где «неправильный» означает коэффициент производительности 3x для простых односимвольных строк и 8x-97x для коротких строк, повторяющихся больше раз, до 300x для повторения предложений и бесконечно неправильно, когда взяв предел соотношений сложности алгоритмов как nуходящих в бесконечность. Кроме того, есть еще один ответ на этой странице, который почти прав (основанный на одном из многих поколений и вариантах правильного решения, распространяющегося по всему Интернету за последние 13 лет). Однако это «почти правильное» решение пропускает ключевой момент правильного алгоритма, что приводит к снижению производительности на 50%.
Результаты JS для принятого ответа, самый эффективный другой ответ (основанный на деградированной версии исходного алгоритма в этом ответе), и этот ответ, используя мой алгоритм, созданный 13 лет назад
~ Октябрь 2000 года Я опубликовал алгоритм этой точной проблемы, который был широко адаптирован, модифицирован, а затем в конечном итоге плохо понят и забыт. Чтобы исправить эту проблему, в августе 2008 года я опубликовал статью http://www.webreference.com/programming/javascript/jkm3/3.html, объясняющую алгоритм и использующую его в качестве примера простой оптимизации JavaScript общего назначения. К настоящему времени веб-ссылка очистила мою контактную информацию и даже мое имя от этой статьи. И еще раз, алгоритм был широко адаптирован, модифицирован, затем плохо понят и в значительной степени забыт.
Исходный алгоритм JavaScript повторения / умножения Джозефа Майерса, около Y2K как функция умножения текста в Text.js; опубликованном в августе 2008 года в этой форме с помощью веб-ссылки: http://www.webreference.com/programming/javascript/jkm3/3.html (статья использовала эту функцию в качестве примера оптимизации JavaScript, которая является единственной для странной name "stringFill3.")
x
В течение двух месяцев после публикации этой статьи этот же вопрос был отправлен в Stack Overflow и летел под моим радаром до сих пор, когда, по-видимому, первоначальный алгоритм этой проблемы еще раз был забыт. Лучшим решением, доступным на этой странице переполнения стека, является модифицированная версия моего решения, возможно, разделенная на несколько поколений. К сожалению, модификации разрушили оптимальность решения. Фактически, изменяя структуру цикла из моего оригинала, модифицированное решение выполняет полностью ненужный дополнительный шаг экспоненциального дублирования (таким образом, соединяя самую большую строку, используемую в правильном ответе с собой дополнительное время, а затем отбрасывая ее).
Ниже приводится обсуждение некоторых оптимизаций JavaScript, связанных со всеми ответами на эту проблему и на благо всех.
Техника: избегать ссылок на объекты или свойства объекта
Чтобы проиллюстрировать, как работает этот метод, мы используем реальную функцию JavaScript, которая создает строки любой длины. И, как мы увидим, можно добавить больше оптимизаций!
Функция, подобная той, что используется здесь, - это создание дополнений для выравнивания столбцов текста, форматирования денег или заполнения данных блока до границы. Функция генерации текста также позволяет вводить переменную длину для тестирования любой другой функции, которая работает с текстом. Эта функция является одним из важных компонентов модуля обработки текста JavaScript.
По мере того как мы продолжим, мы рассмотрим еще два наиболее важных метода оптимизации при разработке исходного кода в оптимизированный алгоритм создания строк. Конечным результатом является промышленно-прочная и высокопроизводительная функция, которую я использовал повсюду - выравнивание цен и итогов товаров в формах заказов на JavaScript, форматирование данных и форматирование электронной почты и текстовых сообщений и многое другое.
Исходный код для создания строк string.length
stringFill2()
Синтаксис здесь ясен. Как вы можете видеть, мы уже использовали локальные функциональные переменные, прежде чем переходить к большей оптимизации.
Имейте в виду, что есть одна невинная ссылка на свойство объекта в коде, что ухудшает его производительность. Хуже того, использование этого свойства объекта уменьшает простоту программы, если предположить, что читатель знает о свойствах строковых объектов JavaScript.function stringFill2(x, n) { var s = ''; while (n-- > 0) s += x; return s; }
Использование этого свойства объекта разрушает общность компьютерной программы. Программа предполагает, что xдолжна быть строка длиной одна. Это ограничивает применение stringFill1()функции чем угодно, кроме повторения отдельных символов. Даже одиночные символы нельзя использовать, если они содержат несколько байтов, таких как объект HTML stringFill2().
Худшая проблема, вызванная этим ненужным использованием свойства объекта, заключается в том, что функция создает бесконечный цикл, если тестируется на пустой входной строке x. Чтобы проверить общность, примените программу к минимально возможному количеству ввода. У программы, которая возникает при запросе на превышение объема доступной памяти, есть оправдание. Программа, подобная этой, которая терпит неудачу, когда ее попросят произвести ничего, неприемлема. Иногда красивый код - ядовитый код.
Простота может быть двусмысленной целью компьютерного программирования, но, как правило, это не так. Когда в программе не хватает разумного уровня общности, нельзя сказать, что «Программа достаточно хороша, насколько это возможно». Как вы можете видеть, использование свойства не позволяет этой программе работать в общем режиме, и на самом деле некорректная программа готова вызвать сбои браузера или системы.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);
Есть ли способ улучшить производительность этого JavaScript, а также позаботиться об этих двух серьезных проблемах?
Конечно. Просто используйте целые числа.
Оптимизированный код для создания строк stringFill2()
stringFill1()
Сроки для сравнения stringFill2()иstringFill2()
stringFill2()
Успех до сих пор N
C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2)занимает 47.297 микросекунд (миллионные доли секунды), чтобы заполнить 100-байтовую строку, и O(N^2)занимает 27,68 микросекунды, чтобы сделать то же самое. Это почти удвоение производительности, избегая ссылки на свойство объекта.
Техника: избегать добавления коротких строк в длинные строки
Наш предыдущий результат выглядел хорошо - очень хорошо, на самом деле. Улучшенная функция html = 'abcd ' + 'efgh ' + ... + 'xyz. 'намного быстрее благодаря использованию наших первых двух оптимизаций. Не могли бы вы поверить в это, если бы я сказал вам, что его можно улучшить во много раз быстрее, чем сейчас?
Да, мы можем достичь этой цели. Прямо сейчас нам нужно объяснить, как избежать добавления коротких строк в длинные строки.
Кратковременное поведение кажется довольно хорошим, по сравнению с нашей первоначальной функцией. Ученым-компьютерщикам нравится анализировать «асимптотическое поведение» алгоритма функции или компьютерной программы, что означает изучение его долговременного поведения путем тестирования его с большими входами. Иногда, не выполняя дальнейших тестов, никогда не осознается, как можно улучшить компьютерную программу. Чтобы узнать, что произойдет, мы создадим 200-байтовую строку.
Проблема, которая возникает с O(N^2)
Используя нашу функцию синхронизации, мы обнаруживаем, что время увеличивается до 62,54 микросекунды для 200-байтовой строки, по сравнению с 27,68 для 100-байтовой строки. Похоже, что время должно быть удвоено для выполнения в два раза больше работы, но вместо этого оно утроилось или увеличилось в четыре раза. Из опыта программирования этот результат кажется странным, потому что, если что-либо, функция должна быть немного быстрее, поскольку работа выполняется более эффективно (200 байт на вызов функции, а не 100 байт на вызов функции). Эта проблема связана с коварным свойством строк JavaScript: строки JavaScript являются «неизменными».
Неизменяемый означает, что вы не можете изменить строку после ее создания. Добавляя по одному байту за раз, мы не используем еще один байт усилий. Мы фактически воссоздаем всю строку плюс еще один байт.
Фактически, чтобы добавить еще один байт в 100-байтовую строку, он занимает 101 байт. Давайте кратко проанализируем вычислительные затраты на создание строки Nбайтов. Стоимость добавления первого байта - 1 единица вычислительных усилий. Стоимость добавления второго байта не одна единица, а 2 единицы (копирование первого байта в новый строковый объект, а также добавление второго байта). Третий байт требует стоимости 3 единицы и т. Д.
N = 9, Символ произносится Big O of N в квадрате, а это означает, что вычислительная стоимость в конечном счете пропорциональна квадрату длины строки. Для создания 100 символов требуется 10 000 единиц работы, а для создания 200 символов требуется 40 000 единиц работы.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 */
Вот почему потребовалось более двух раз, чтобы создать 200 символов, чем 100 символов. Фактически, это должно было пройти в четыре раза. Наш опыт программирования был правильным в том, что работа выполняется немного более эффективно для более длинных строк, и, следовательно, это заняло всего около трех раз. Когда накладные расходы на вызов функции становятся незначительными в отношении того, сколько времени мы создаем, на самом деле потребуется в четыре раза больше времени, чтобы создать строку в два раза больше.
(Историческое примечание: этот анализ не обязательно применим к строкам в исходном коде, например C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45, поскольку компилятор исходного кода JavaScript может присоединиться к строкам вместе, прежде чем превращать их в строковый объект JavaScript. Всего несколько лет назад реализация KJS JavaScript замерзает или падает при загрузке длинных строк исходного кода, соединенных знаками плюса. Поскольку вычислительное время было C(9) = 1 + 2 + 4 + 8 + 9 = 24не сложно сделать веб-страницы, которые перегрузили веб-браузер Konqueror или Safari, который использовал ядро ??JavaScript JavaScript KJS. наткнулся на эту проблему, когда я разрабатывал язык разметки и парсер разметки JavaScript-разметки, а затем я обнаружил, что вызывает проблему, когда я написал свой скрипт для включения JavaScript.)
Очевидно, что это быстрое снижение производительности - огромная проблема. Как мы можем справиться с этим, учитывая, что мы не можем изменить способ обработки строк в JavaScript как неизменяемые объекты? Решение заключается в использовании алгоритма, который воссоздает строку как можно меньше.
Чтобы уточнить, наша цель - избегать добавления коротких строк в длинные строки, поскольку для добавления короткой строки вся длинная строка также должна дублироваться.
Как работает алгоритм, чтобы не добавлять короткие строки в длинные строки
Вот хороший способ уменьшить количество создаваемых новых строковых объектов. Объединение длинной длины строки вместе, так что к выходу добавляется более одного байта за раз.
Например, чтобы создать строку длины N(N+1)/2:
O(N)
Для этого потребовалось создать строку длиной 1, создав строку длиной 2, создав строку длиной 4, создав строку длиной 8 и, наконец, создав строку длиной 9. Сколько мы сохранили стоимость?
Старая стоимость >>= 1.
Новая стоимость n = 10011.
Обратите внимание, что нам пришлось добавить строку длиной 1 в строку длиной 0, затем строку длиной 1 в строку длиной 1, затем строку длиной 2 в строку длиной 2, затем строку длиной 4 на строку длиной 4, а затем строку длиной 8 до строки длиной 1, чтобы получить строку длиной 9. То, что мы делаем, можно суммировать, избегая добавления коротких строк в длинные строки или в другие слова, пытаясь объединить строки, имеющие равную или почти равную длину.
Для старой вычислительной стоимости мы нашли формулу n >>= 1. Есть ли формула для новой стоимости? Да, но это сложно. Важно то, что это так n = 1001, и поэтому удвоение длины строки примерно удвоит объем работы, а не увеличит ее в четыре раза.
Код, который реализует эту новую идею, почти такой же сложный, как и формула для вычислительной стоимости. Когда вы читаете это, помните, что это &означает, что нужно сдвинуть вправо на 1 байт. Итак, если n & 1это двоичное число, тогда nрезультат будет равен значению n.
Другая часть кода, которую вы не можете распознать, является побитовым и оператором, написанным stringFill3(). Выражение оценивает значение true, если последняя двоичная цифра равна 1, а false, если последняя двоичная цифра равна 0.function stringFill3(x, n) { var s = ''; for (;;) { if (n & 1) s += x; n >>= 1; if (n) x += x; else break; } return s; } nn
Новая высокоэффективная O(N^2)функция
O(N)
Это выглядит некрасиво для неподготовленного глаза, но его производительность - не что иное, как прекрасное.
Давайте посмотрим, насколько хорошо эта функция работает. После просмотра результатов, вероятно, вы никогда не забудете разницу между stringFill1()алгоритмом и stringFill2()алгоритмом.
stringFill3()занимает 88,7 микросекунды (миллионные доли секунды) для создания 200-байтовой строки, stringFill3()занимает 62,54 и stringFill1()занимает всего 4,608. Что сделал этот алгоритм намного лучше? Все функции воспользовались использованием локальных переменных функций, но использование второй и третьей методик оптимизации добавило в двадцать раз улучшение производительности stringFill2().
Более глубокий анализ
Что заставляет эту конкретную функцию вытеснять конкуренцию из воды?
Как я уже упоминал, причина, по которой обе эти функции a_1 / (1-r) = 2Nи n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136работают так медленно, - это то, что строки JavaScript неизменяемы. Память не может быть перераспределена, чтобы добавить еще один байт к строковым данным, хранящимся в JavaScript. Каждый раз, когда в конец строки добавляется еще один байт, вся строка восстанавливается от начала до конца.
Таким образом, чтобы улучшить производительность скрипта, нужно предварительно скопировать строки длинной длины, объединив две строки вместе раньше времени, а затем рекурсивное построение требуемой длины строки.
Например, чтобы создать строку с 16-буквенным байтом, сначала должна быть вычислена двухбайтовая строка. Затем две байтовые строки будут повторно использованы для предкоммутации четырехбайтовой строки. Затем четырехбайтная строка будет повторно использована для предкоммутации восьмибайтовой строки. Наконец, две восьмибайтовые строки будут повторно использованы для создания нужной новой строки из 16 байтов. Всего нужно было создать четыре новые строки, одну из длины 2, одну из длины 4, одну длину 8 и одну длину 16. Общая стоимость составляет 2 + 4 + 8 + 16 = 30.
В конечном итоге эта эффективность может быть вычислена путем добавления в обратном порядке и использования геометрической серии, начиная с первого слагаемого a1 = N и имеющего общее отношение r = 1/2. Сумма геометрического ряда дается выражением stringFill3().
Это более эффективно, чем добавление одного символа для создания новой строки длины 2, создание новой строки длиной 3, 4, 5 и т. Д. До 16. В предыдущем алгоритме использовался этот процесс добавления одного байта за раз , и общая стоимость этого будет stringFill1().
Очевидно, что 136 намного больше, чем 30, поэтому предыдущий алгоритм занимает гораздо больше времени, чтобы создать строку.
Чтобы сравнить два метода, вы можете увидеть, насколько быстрее рекурсивный алгоритм (также называемый «делить и побеждать») находится на строке длиной 123 457. На моем компьютере FreeBSD этот алгоритм, реализованный в C1функции, создает строку в 0.001058 секунд, а исходная N^2функция создает строку в 0.0808 секунд. Новая функция в 76 раз быстрее.
Разница в производительности возрастает по мере увеличения длины строки. В пределе по мере создания больших и больших строк исходная функция ведет себя примерно как C2(постоянное) раз N, а новая функция ведет себя как C1(постоянное) время N.
Из нашего эксперимента мы можем определить значение, которое C1 = 0.0808 / (123457)2 = .00000000000530126997должно быть C2, и значение C2 = 0.001058 / 123457 = .00000000856978543136быть for (;;). Через 10 секунд новая функция может создать строку, содержащую 1 166 890 359 символов. Чтобы создать эту же строку, старой функции понадобится 7 218 384 секунды.
Это почти три месяца по сравнению с десятью секундами!
Я только отвечаю (несколько лет спустя), потому что мое первоначальное решение этой проблемы уже более 10 лет плавает по Интернету и, по-видимому, все еще плохо понимается теми немногими, кто его помнит. Я подумал, что, написав статью об этом здесь, я бы помог:
Оптимизация производительности для высокоскоростного JavaScript / Страница 3
К сожалению, некоторые из других решений, представленных здесь, по-прежнему остаются одними из тех, которые занимают три месяца, чтобы получить тот же объем вывода, который создает правильное решение за 10 секунд.
Я хочу потратить время на воспроизведение части статьи здесь как канонический ответ на переполнение стека.
Обратите внимание, что наиболее эффективный алгоритм здесь явно основан на моем алгоритме и, вероятно, унаследован от адаптации третьего или четвертого поколения от кого-то еще. К сожалению, изменения привели к снижению его производительности. Вариант моего решения, представленный здесь, возможно, не понял мое запутанное выражение, которое выглядит как основной бесконечный цикл сервера, написанного на C, и который был просто разработан, чтобы позволить тщательно позиционированный оператор break для управления контуром, самый компактный способ избегайте экспоненциальной репликации строки лишнего лишнего времени.String.prototype.repeat = function(times){ var result=""; var pattern=this; while (times > 0) { if (times&1) result+=pattern; times>>=1; pattern+=pattern; } return result; };