Zestaw JavaScript a wydajność tablicy


87

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.


1
Nie możesz ich używać zamiennie. Nie ma więc sensu ich porównywać.
zerkms,

mówisz o porównaniu między Seta []lub {}?
wysłany

2
Dodawanie i iterowanie nie robi dużej różnicy, usuwanie i - co najważniejsze - wyszukiwanie robi różnicę.
Bergi


3
@ zerkms - ściśle, tablice też nie są uporządkowane, ale ich użycie indeksu pozwala traktować je tak, jakby były. ;-) Sekwencja wartości w zestawie jest utrzymywana w kolejności wstawiania.
RobG

Odpowiedzi:


98

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


1
Pamiętaj, że wartości zestawu są domyślnie unikalne. Tak więc, jeśli [1,1,1,1,1,1]tablica miałaby długość 6, zbiór miałby rozmiar 1. Wygląda na to, że twój kod może w rzeczywistości generować zestawy o szalenie różnych rozmiarach niż 100 000 elementów rozmiaru w każdym przebiegu z powodu tej cechy zestawów. Prawdopodobnie nigdy nie zauważyłeś, ponieważ nie pokazujesz rozmiaru zestawu, dopóki nie zostanie uruchomiony cały skrypt.
KyleFarris

6
@KyleFarris O ile się nie mylę, byłoby to prawdą, gdyby w zestawie były duplikaty, jak w twoim przykładzie [1, 1, 1, 1, 1], ale ponieważ każdy element w zestawie jest w rzeczywistości obiektem o różnych właściwościach, w tym imię i nazwisko losowo wygenerowane z listy setek możliwych imion, losowo generowany wiek, losowo generowana płeć i inne losowo generowane atrybuty ... szanse na posiadanie dwóch identycznych obiektów w zestawach są niewielkie.
snowfrogdev

3
Właściwie masz rację w tym przypadku, ponieważ wydaje się, że zestawy w rzeczywistości nie różnią się od obiektów w zestawie. Tak więc, rzeczywiście, mógłbyś nawet mieć w zestawie ten sam dokładny obiekt 10 {foo: 'bar'}000x i miałby rozmiar 10 000. To samo dotyczy tablic. Wydaje się, że jest unikalny tylko w przypadku wartości skalarnych (ciągi znaków, liczby, wartości logiczne itp.).
KyleFarris

12
Możesz mieć tę samą dokładną zawartość obiektu {foo: 'bar'} wiele razy w zestawie, ale nie dokładnie ten sam obiekt (odniesienie). Warto
zwrócić

14
Zapomniałeś o pomiarze najważniejszego powodu używania zestawu, wyszukiwania 0 (1). hasvs IndexOf.
Magnus,

65

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


4
Array.indexOf powinno mieć wartość Array.includes, aby były równoważne. W przeglądarce Firefox otrzymuję bardzo różne liczby.
kagronick

2
Byłbym zainteresowany porównaniem Object.includes vs. Set. Ma ...
Leopold Kristjansson

1
@LeopoldKristjansson Nie napisałem testu porównawczego, ale zrobiliśmy taktowanie w zakładzie produkcyjnym z tablicami z 24k pozycjami i przejściem z Array.includes na Set. Było niesamowitym wzrostem wydajności!
sedot

3

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


3

Zrzut ekranu testowanej iteracjiJeś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.


4
Nie używaj linków w swoich odpowiedziach (chyba że są one połączone z oficjalnymi bibliotekami), ponieważ mogą one zostać zerwane - tak jak stało się w Twoim przypadku. Link to 404.
Gil Epshtain

Użyłem linku, ale również skopiowałem dane wyjściowe, gdy były dostępne. Szkoda, że ​​tak szybko zmienili strategię łączenia.
Zargold

Zaktualizowałem post teraz o zrzut ekranu i nową stronę internetową z wydajnością JS: jsbench.me
Zargold

-5
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

@Bergi też tak myślałem na początku, ale tak jest.
zerkms

1
@zerkms: Zdefiniuj "work" :-) Tak, tablica będzie pusta po znaku forEach, ale prawdopodobnie nie w taki sposób, jakiego oczekiwałeś. Jeśli ktoś chce porównywalnego zachowania, to też powinno s.forEach(function(e) { s.clear(); }).
Bergi

1
Cóż, robi coś, ale nie to, co jest zamierzone: usuwa wszystkie elementy między indeksem i a końcem. To nie ma porównania z tym, co deleterobi na planie.
trincot

@Bergi o racja, usuwa wszystko w zaledwie 2 iteracjach. Mój błąd.
zerkms

4
W 1 iteracji. splice(0)opróżnia tablicę.
trincot
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.