Array benchmark

Сейчас работаю с big-data, вот и пригодилась экономия на списках которую я продвигал везде и всюду.

Нужно читать данные из файла (самые большие 88, 44, 35 метров) и складывать в массив. Первое и самое простое это прочитать файл функцией file но вот черт под node.js нет такой функции. Ладно, худо бедно смастерил обертку над fs.createReadStream, но об этом в другой раз.

Какой самый лучший способ сложить в массив? Начнем с самого быстрого в написании и самого медленного при выполнении:


var size = 1e6;
var a = [];
var start = new Date();
for (var i = 0; i < size; i++) {
    a.push(Math.random());
}
var stop = new Date();
console.log(stop - start); // 360 :(

Логично, push каждый раз создает новый массив в памяти, избавимся от него.


var size = 1e6;
var a = [];

var start = new Date();
for (var i = 0; i < size; i++) {
    a[i] = Math.random();
}
var stop = new Date();
console.log(stop - start); // 110

Ожидаемый прирост, но можно ли больше? Зададим размер массиву как в java


var size = 1e6;
var a = new Array(size);

var start = new Date();
for (var i = 0; i < size; i++) {
    a[i] = Math.random();
}
var stop = new Date();
console.log(stop - start); // 150

Странно, но быстрее не вышло, а что если убрать размер и оставит только создание через конструктор?


var size = 1e6;
var a = new Array();

var start = new Date();
for (var i = 0; i < size; i++) {
    a[i] = Math.random();
}
var stop = new Date();
console.log(stop - start); // 50 !

В рот мне ноги! В 7 раз быстрее!!! На восьми миллионах записей весьма ощутимо.

4 Комментарии “Array benchmark

  1. Серьёзно? Один замер и всё? Это просто статистически незначимо.
    Для сравнения производительности различных сниппетов JS кода есть jsperf: http://jsperf.com/array-insert-benchmark-damn (там внизу уже есть результаты 3 браузеров, два с тем же JS движком, что и Node.JS)
    Как видно, все варианты равнозначны кроме new Array(size). Почему это он так — вопрос открытый и, полагаю, implementation defined.
    Почему вдруг push должен под капотом создавать новый массив? Мы же состояние текущего меняем.

    Вообще, заниматься big data’ой на JS, имхо, дело гиблое. Тут слишком мало контроля над тем, что происходит на низком уровне, слишком высокоуровневые абстракции. Я не призываю писать на си, но какая-нибудь Java (или её вариант вроде Scala) вполне ок.

  2. Не один конечно) десяточек и среднее минус самое большое и самое маленькое. До jspref рочемуто не додумался :( По поводу пуша: если на низком уровне каждый раз не создавать массив с количеством элементов большим на 1 чем текущий то как это организовать

  3. Ну, во-первых, все разумные реализации расширяющихся массивов используют известную стратегию «экспоненциального роста»: при заполнении массвива он увеличивается в два (или 1.5) раза. Можно показать, что амортизированно сложность вставки тогда будет O(1).

    Во-вторых, учитывая то, что всё в JS объект, а так же то, что храниться в массивах могут значения разных типов, нет оснований считать, что внутри там настоящий массив. Вполне может быть хеш-таблица.

  4. логично. тогда все лишнее время занимает создание элементов с undefind’ом

Комментарии закрыты