Zestaw JavaScript a wydajność tablicy

Może dlatego, że zestawy są stosunkowo nowe w Javascript, ale nie udało mi się znaleźć artykułu, na StackO ani nigdzie indziej, który mówi o różnicy w wydajności między nimi w Javascript. Jaka jest więc różnica, jeśli chodzi o wydajność, między nimi? W szczególności jeśli chodzi o usuwanie, dodawanie i iterowanie.

Ok, przetestowałem dodawanie, iterowanie i usuwanie elementów zarówno z tablicy, jak i zestawu. Przeprowadziłem „mały” test, używając 10 000 elementów i „duży” test, używając 100 000 elementów. Oto wyniki.

Dodawanie elementów do kolekcji

Wydawałoby się, że .pushmetoda tablicowa jest około 4 razy szybsza niż .addmetoda set, niezależnie od ilości dodawanych elementów.

Iterowanie i modyfikowanie elementów w kolekcji

W tej części testu użyłem forpętli do iteracji po tablicy i for ofpętli do iteracji po zestawie. Ponownie, iterowanie po tablicy było szybsze. Tym razem wydawać by się mogło, że jest to wykładnicze, ponieważ podczas testów „małych” trwało to dwa razy dłużej, a podczas testów „dużych” prawie czterokrotnie dłużej.

Usuwanie elementów z kolekcji

Teraz robi się interesująco. Użyłem kombinacji forpętli i .spliceusunięcia niektórych elementów z tablicy oraz użyłem for ofi .deleteusunąłem niektóre elementy z zestawu. W przypadku „małych” testów usuwanie elementów z zestawu było około trzy razy szybsze (2,6 ms w porównaniu z 7,1 ms), ale sytuacja zmieniła się drastycznie w przypadku testu „dużego”, w którym usunięcie elementów z tablicy zajęło tylko 1955,1 ms. usunięcie ich z zestawu zajęło 83,6 ms, czyli 23 razy szybciej.

Wnioski

Przy 10 tys. Elementów oba testy działały porównywalnie (tablica: 16,6 ms, zestaw: 20,7 ms), ale przy 100 tys. Elementów zestaw był wyraźnym zwycięzcą (tablica: 1974,8 ms, zestaw: 83,6 ms), ale tylko ze względu na usunięcie operacja. W przeciwnym razie tablica była szybsza. Nie potrafię dokładnie powiedzieć, dlaczego tak jest.

Bawiłem się niektórymi scenariuszami hybrydowymi, w których tablica została utworzona i zapełniona, a następnie przekształcona w zestaw, w którym niektóre elementy zostałyby usunięte, a następnie zestaw zostałby ponownie przekształcony w tablicę. Chociaż da to znacznie lepszą wydajność niż usuwanie elementów w tablicy, dodatkowy czas przetwarzania potrzebny do przesłania do iz zestawu przeważa nad korzyściami wynikającymi z zapełnienia tablicy zamiast zestawu. W końcu szybciej jest zajmować się tylko zestawem. Mimo to jest interesującym pomysłem, że jeśli zdecydujesz się użyć tablicy jako zbioru danych dla niektórych dużych zbiorów danych, które nie mają duplikatów, może to być korzystne pod względem wydajności, jeśli kiedykolwiek zajdzie potrzeba usunięcia wielu elementów w jednym operacja, aby przekonwertować tablicę na zestaw, wykonać operację usuwania i przekonwertować zestaw z powrotem na tablicę.

Kod tablicy:

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

Ustaw kod:

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

UWAGI :

• Operacje na zbiorach można rozumieć jako migawki w strumieniu wykonania.
• Nie jesteśmy przed ostatecznym substytutem.
• Elementy klasy Set nie mają dostępnych indeksów.
• Klasa set to uzupełnienie klasy Array , przydatne w tych scenariuszach, w których musimy przechowywać kolekcję, na której można zastosować podstawowe operacje dodawania, usuwania, sprawdzania i iteracji.

Podzielę się pewnym testem wydajności. Spróbuj otworzyć konsolę i skopiuj poniższy kod.

Tworzenie tablicy (125000)

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

1. Lokalizowanie indeksu

Porównaliśmy metodę has z Set z Array indexOf:

Array / indexOf (0,281 ms) | Ustawiono / ma (0,053 ms)

// 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. Dodanie nowego elementu

Porównujemy odpowiednio metody add i push obiektów Set i Array:

Array / push (1,612 ms) | Ustaw / dodaj (0,006 ms)

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. Usunięcie elementu

Podczas usuwania elementów musimy pamiętać, że Array i Set nie rozpoczynają się na równych warunkach. Array nie ma metody natywnej, więc potrzebna jest funkcja zewnętrzna.

Array / deleteFromArr (0,356 ms) | Ustaw / usuń (0,019 ms)

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

Przeczytaj cały artykuł tutaj

Z moich obserwacji wynika, że ​​zestaw jest zawsze lepszy, mając na uwadze dwie pułapki związane z dużymi tablicami:

a) Tworzenie zestawów z tablic musi odbywać się w forpętli o określonej długości.

wolno (np. 18 ms) new Set(largeArray)

szybki (np. 6 ms) const SET = new Set(); const L = largeArray.length; for(var i = 0; i<L; i++) { SET.add(largeArray[i]) }

b) Iterowanie można wykonać w ten sam sposób, ponieważ jest również szybsze niż for ofpętla ...

Zobacz https://jsfiddle.net/0j2gkae7/5/

dla prawdziwego stosunku do życia difference(), intersection(), union()i uniq()(+ ich towarzyszy iteratee etc.) z 40.000 elementów

Jeśli chodzi o iteracyjną część twojego pytania, przeprowadziłem niedawno ten test i stwierdziłem, że Set znacznie przewyższył tablicę 10 000 elementów (około 10 razy więcej operacji mogło się wydarzyć w tym samym czasie). W zależności od przeglądarki, Object.hasOwnProperty pobił lub przegrał w podobnym teście.

Zarówno Set, jak i Object mają metodę "ma" działającą w sposób, który wydaje się być amortyzowany do O (1), ale w zależności od implementacji przeglądarki pojedyncza operacja może trwać dłużej lub szybciej. Wygląda na to, że większość przeglądarek implementuje klucz w Object szybciej niż Set.has (). Nawet Object.hasOwnProperty, który obejmuje dodatkowe sprawdzenie klucza, jest około 5% szybszy niż Set.has () przynajmniej dla mnie w Chrome v86.

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

Aktualizacja: 11.11.2020: https://jsbench.me/irkhdxnoqa/2

Jeśli chcesz uruchomić własne testy z różnymi przeglądarkami / środowiskami.

Podobnie dodam wzorzec dodawania elementów do tablicy w porównaniu do zestawu i usuwania.

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

Te trzy operacje na przedmiotach 10K dały mi:

set: 7.787ms
array: 2.388ms