Хочу разобраться в этом вопросе. Задача: сначала идёт процесс накопления строк, потом нужен результат в виде одной строки - конкатенации всех строк. Собственно варианта основных, как я понимаю, два: либо делать «в лоб» через +=, либо собирать строки в массив строк и потом делать arr.join(""). Первичное тестирование выявило, что оба варианта дают примерно похожую скорость. Тем не менее хотелось бы понять, почему. Асимптотику выяснить не получилось: тупо памяти не хватает почему-то на тех объёмах, где время работы алгоритма начинается от 10 секунд. На всяких SO рекомендуют писать «в лоб», но я SO в таких вопросах не доверяю. Но как разобраться - не знаю.
Сроки в JS иммутабельны. Логично предположить, что это всё похоже на Java. В Java подход с конкатенацией строк даст O(N^2), то бишь работать будет только для малого N. Мб там JIT умеет оптимизировать какие-то простые случаи, но на это полагаться глупо. StringBuilder-а в JS нет.
Вроде бы подход с массивом строк должен быть оптимален. Массив строк это по сути массив указателей на строку. Наверняка там есть capacity >= length и push в итоге даёт O(1) амортизировано. Метод join может работать в 2 прохода: сначала выяснить длину результата, выделить память и во втором проходе построить результат за O(N).
По факту я не вижу разницы между этими подходами. И вынужден заключить, что либо JS резервирует для иммутабельных строк память порядка length * 2, чтобы потом оптимизировать конструкцию str += s за счёт этого. Либо метод Array.prototype.join реализован неправильно и работает с O(N^2). Оба вывода грустные. Помогите разобраться, если кто копал тут на низком уровне.
