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

Ответ 1

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

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

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

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

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

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

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

Выводы

В 10k-элементах оба теста выполняли сопоставимые времена (массив: 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.")

Ответ 2

НАБЛЮДЕНИЯ

• Операции установки можно понимать как моментальные снимки в потоке выполнения.
• Мы не находимся перед окончательной заменой.
• Элементы класса 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 с массивом indexOf:

Массив/ indexOf (0.281ms) | Set/ имеет (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 соответственно:

Массив/ push (1.612ms) | Set/ добавить (0.006ms)

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 не запускаются при равных условиях. Массив не имеет нативного метода, поэтому необходима внешняя функция.

Массив/ deleteFromArr (0.356ms) | Set/ удалить (0.019ms)

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' );

Прочитайте полную статью здесь

Ответ 3

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

a) Создание наборов из массивов должно выполняться в цикле 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]) }

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

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

для сравнения реальной жизни с difference(), intersection(), union() и uniq() (+ их итерационные компаньоны и т.д.) с 40 000 элементами

Ответ 4

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")

Те три операции на объектах 10K дали мне:

set: 7.787ms
array: 2.388ms