Набор Javascript и производительность массива

Возможно, это связано с тем, что наборы являются относительно новыми для Javascript, но мне не удалось найти статью на StackO или где-либо еще, в которой говорилось бы о разнице в производительности между ними в Javascript. Итак, в чем разница с точки зрения производительности между ними? В частности, когда дело доходит до удаления, добавления и повторения.

Хорошо, я протестировал добавление, повторение и удаление элементов как из массива, так и из набора. Я провел «маленький» тест, используя 10 000 элементов, и «большой» тест, используя 100 000 элементов. Вот результаты.

Добавление элементов в коллекцию

Казалось бы, .pushметод массива примерно в 4 раза быстрее, чем .addметод set, независимо от количества добавляемых элементов.

Итерация и изменение элементов в коллекции

В этой части теста я использовал forцикл для итерации по массиву и for ofцикл для итерации по набору. Опять же, итерация по массиву была быстрее. На этот раз, казалось бы, экспоненциально, так как на «малых» тестах потребовалось вдвое больше времени, а на «больших» - почти в четыре раза больше.

Удаление элементов из коллекции

А теперь самое интересное. Я использовал комбинацию forцикла и .spliceдля удаления некоторых элементов из массива, и я использовал for ofи .deleteдля удаления некоторых элементов из набора. Для «малых» тестов удаление элементов из набора было примерно в три раза быстрее (2,6 мс против 7,1 мс), но все резко изменилось для «большого» теста, где на удаление элементов из массива потребовалось 1955,1 мс, в то время как он только На их удаление из набора потребовалось 83,6 мс, в 23 раза быстрее.

Выводы

При 10 тыс. Элементов оба теста прошли сравнимое время (массив: 16,6 мс, набор: 20,7 мс), но при работе с элементами из 100 тыс. Набор явился явным победителем (массив: 1974,8 мс, набор: 83,6 мс), но только из-за удаления операция. В противном случае массив был бы быстрее. Я не могу точно сказать, почему это так.

Я поиграл с некоторыми гибридными сценариями, в которых массив был создан и заполнен, а затем преобразован в набор, в котором некоторые элементы будут удалены, а затем набор снова преобразован в массив. Хотя это даст гораздо лучшую производительность, чем удаление элементов в массиве, дополнительное время обработки, необходимое для передачи в набор и из него, перевешивает выгоды от заполнения массива вместо набора. В конце концов, быстрее иметь дело только с набором. Тем не менее, это интересная идея, что если кто-то решит использовать массив в качестве сбора данных для некоторых больших данных, не имеющих дубликатов, это может быть выгодно с точки зрения производительности, если когда-либо возникнет необходимость удалить много элементов в одном. операция, чтобы преобразовать массив в набор, выполнить операцию удаления и преобразовать набор обратно в массив.

Код массива:

var timer = function(name) {
  var start = new Date();
  return {
    stop: function() {
      var end = new Date();
      var time = end.getTime() - start.getTime();
      console.log('Timer:', name, 'finished in', time, 'ms');
    }
  }
};

var getRandom = function(min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH', 'JOHNSON', 'WILLIAMS', 'JONES', 'BROWN', 'DAVIS', 'MILLER', 'WILSON', 'MOORE', 'TAYLOR', 'ANDERSON', 'THOMAS'];

var genLastName = function() {
  var index = Math.round(getRandom(0, lastNames.length - 1));
  return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
  var index = Math.round(getRandom(0, sex.length - 1));
  return sex[index];
};

var Person = function() {
  this.name = genLastName();
  this.age = Math.round(getRandom(0, 100))
  this.sex = "Male"
};

var genPersons = function() {
  for (var i = 0; i < 100000; i++)
    personArray.push(new Person());
};

var changeSex = function() {
  for (var i = 0; i < personArray.length; i++) {
    personArray[i].sex = genSex();
  }
};

var deleteMale = function() {
  for (var i = 0; i < personArray.length; i++) {
    if (personArray[i].sex === "Male") {
      personArray.splice(i, 1)
      i--
    }
  }
};

var t = timer("Array");

var personArray = [];

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personArray.length + " persons.")

Установить код:

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

var getRandom = function (min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH','JOHNSON','WILLIAMS','JONES','BROWN','DAVIS','MILLER','WILSON','MOORE','TAYLOR','ANDERSON','THOMAS'];

var genLastName = function() {
    var index = Math.round(getRandom(0, lastNames.length - 1));
    return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
    var index = Math.round(getRandom(0, sex.length - 1));
    return sex[index];
};

var Person = function() {
	this.name = genLastName();
	this.age = Math.round(getRandom(0,100))
	this.sex = "Male"
};

var genPersons = function() {
for (var i = 0; i < 100000; i++)
	personSet.add(new Person());
};

var changeSex = function() {
	for (var key of personSet) {
		key.sex = genSex();
	}
};

var deleteMale = function() {
	for (var key of personSet) {
		if (key.sex === "Male") {
			personSet.delete(key)
		}
	}
};

var t = timer("Set");

var personSet = new Set();

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personSet.size + " persons.")

НАБЛЮДЕНИЯ :

• Операции с наборами можно понимать как снимки в потоке выполнения.
• Мы не стоим перед окончательной заменой.
• У элементов класса Set нет доступных индексов.
• Класс Set - это дополнение к классу Array , полезное в тех сценариях, где нам нужно хранить коллекцию, к которой будут применяться базовые операции добавления, удаления, проверки и итерации.

Делюсь некоторым тестом работоспособности. Попробуйте открыть консоль и скопируйте код ниже.

Создание массива (125000)

var n = 125000;
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); // 125000

1. Расположение указателя

Мы сравнили has-метод Set с Array indexOf:

Array / indexOf (0,281 мс) | Установить / имеет (0,053 мс)

// Helpers
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );

// Vars
var set, result;

console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );

2. Добавление нового элемента

Мы сравниваем методы add и push объектов Set и Array соответственно:

Массив / нажатие (1,612 мс) | Установить / добавить (0,006 мс)

console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );

console.info( arr.length ); // 125001
console.info( set.size ); // 125001

3. Удаление элемента

При удалении элементов мы должны помнить, что Array и Set не запускаются в равных условиях. Array не имеет собственного метода, поэтому необходима внешняя функция.

Array / deleteFromArr (0,356 мс) | Установить / удалить (0,019 мс)

var deleteFromArr = ( arr, item ) => {
    var i = arr.indexOf( item );
    i !== -1 && arr.splice( i, 1 );
};

console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );

Читайте полную статью здесь

По моим наблюдениям, Set всегда лучше, имея в виду две ловушки для больших массивов:

а) Создание наборов из массивов должно выполняться в forцикле с заранее кэшированной длиной.

медленно (например, 18 мс) new Set(largeArray)

быстро (например, 6 мс) const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }

б) Итерация может быть выполнена таким же образом, потому что она также быстрее, чем for ofцикл ...

См. Https://jsfiddle.net/0j2gkae7/5/

для реального сравнения жизни к difference(), intersection(), union()и uniq()(+ их iteratee компаньонов и т.д.) с 40.000 элементами

Что касается итерационной части вашего вопроса, я недавно провел этот тест и обнаружил, что Set намного превосходит Array из 10 000 элементов (примерно в 10 раз больше операций может происходить за тот же период времени). И в зависимости от браузера либо превзойти, либо проиграть Object.hasOwnProperty в подобном тесте.

И Set, и Object имеют свой метод has, который, кажется, амортизируется до O (1), но в зависимости от реализации браузера одна операция может занять больше времени или быстрее. Кажется, что большинство браузеров реализуют ключ в Object быстрее, чем Set.has (). Даже Object.hasOwnProperty, который включает дополнительную проверку ключа, примерно на 5% быстрее, чем Set.has (), по крайней мере, для меня в Chrome v86.

https://jsperf.com/set-has-vs-object-hasownproperty-vs-array-includes/1

Обновление: 11.11.2020: https://jsbench.me/irkhdxnoqa/2

Если вы хотите запустить свои собственные тесты в разных браузерах / средах.

Точно так же я добавлю тест для добавления элементов в массив по сравнению с набором и удалением.

console.time("set")
var s = new Set()
for(var i = 0; i < 10000; i++)
  s.add(Math.random())
s.forEach(function(e){
  s.delete(e)
})
console.timeEnd("set")
console.time("array")
var s = new Array()
for(var i = 0; i < 10000; i++)
  s.push(Math.random())
s.forEach(function(e,i){
  s.splice(i)
})
console.timeEnd("array")

Эти три операции с 10К предметами дали мне:

set: 7.787ms
array: 2.388ms