Javascript: Какова алгоритмическая производительность "сращивания"?

Ответ 1

Вы можете подумать, хотите ли вы использовать объект вместо этого; все объекты JavaScript (включая экземпляры Array) являются (высоко оптимизированными) наборами пар ключ/значение с необязательным прототипом. Реализация должна (заметьте, я не говорю "делает") иметь разумный алгоритм хэширования производительности. (Обновление: это было в 2010 году. Здесь, в 2018 году, объекты сильно оптимизированы на всех значимых движках JavaScript.)

Кроме того, производительность splice собирается рознятся между реализациями (например, продавцов). Это одна из причин, по которой "не оптимизировать преждевременно" является еще более подходящим советом для приложений JavaScript, которые будут работать в реализациях разных производителей (например, веб-приложений), чем даже для обычного программирования. Держите ваш код хорошо модульным и устраняйте проблемы производительности, если и когда они возникают.

Ответ 2

Здесь хорошее эмпирическое правило, основанное на тестах, выполненных в Chrome, Safari и Firefox: объединение одного значения в середину массива примерно наполовину быстрее, поскольку нажатие/сдвиг значения на один конец массива. (Примечание: проверяется только на массив размером 10 000.)

http://jsperf.com/splicing-a-single-value

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

Обновление. Как отмечает eBusiness в комментариях ниже, тест выполняет дорогостоящую операцию копирования вместе с каждым splice, push и shift, что означает, что он занижает разница в производительности. Здесь пересмотренный тест, который позволяет избежать копирования массива, поэтому он должен быть намного точнее: http://jsperf.com/splicing-a-single-value/19

Ответ 3

Переместить одиночное значение

//	tmp = arr[1][i];
//	arr[1].splice(i, 1);	// splice is slow in FF
//	arr[1].splice(end0_1, 0, tmp);

	tmp = arr[1][i];
	ii = i;
	while (ii<end0_1)
		{
		arr[1][ii] = arr[1][++ii];
cycles++;
		}
	arr[1][end0_1] = tmp;