Nasza strona używa cookies. Korzystając ze strony, wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki. Rozumiem

Ulepsz swój kod z JavaScript Set

Bret Cameron Digital Consultant / Concurrent Design Group
Sprawdź, czym jest Set z JavaScript, poznaj jego przewagę nad tablicą i zobacz, w jaki sposób może ulepszyć Twój kod.
Ulepsz swój kod z JavaScript Set

Jestem pewien, że istnieje wielu programistów, którzy trzymają się podstawowych obiektów globalnych: liczb, ciągów znaków, obiektów, tablic oraz typów boolowskich. W wielu przypadkach jest to właściwie wszystko, czego potrzebujesz. Jeśli jednak chcesz, aby Twój kod był tak szybki i skalowalny, jak to możliwe, to być może potrzeba będzie czegoś więcej.

W tym artykule porozmawiamy o tym, w jaki sposób Set z JavaScript (znany również jako zbiór) przyśpieszy Twój kod — zwłaszcza w miarę jego skalowania. Istnieje znaczna różnica między tym, co potrafi tablica, a tym, co potrafi taki zbiór. Zbiory działają często o wiele lepiej niż tablice. W tym artykule dowiesz się, jak to możliwe. 


Czym Set się różni od tablicy?

Najbardziej fundamentalną różnicą między zbiorami a tablicami jest to, że tablice są kolekcją indeksowaną. Oznacza to, że wartość danych w tablicy jest uporządkowana według indeksu.

const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2

Natomiast zbiory to kolekcje z kluczami — zamiast używać indeksów, porządkują swoje dane za pomocą kluczy. Ich elementy są iterowalne w kolejności wstawiania i nie mogą zawierać żadnych zduplikowanych danych. Innymi słowy, każdy element w zbiorze musi być unikalny.


Główne korzyści

Set ma przewagę nad tablicami w kilku aspektach. Na szczególną uwagę zasługuje tutaj szybsze uruchomienie:

  • Szukanie elementu: użycie indexOf() lub includes(), aby sprawdzić, czy element istnieje w tablicy jest dość wolne.
  • Usuwanie elementu: w zbiorze możesz usunąć element za pomocą jego wartości. W tablicy trzeba do tego użyć splice() na podstawie indeksu elementu. Podobnie jak w poprzednim punkcie, poleganie tu na indeksach spowalnia operację.
  • Wstawianie elementu: dodawanie elementu do zbioru jest szybsze niż dodawanie elementu do tablicy za pomocą metod push(), unshift() lub ekwiwalentu.
  • Przechowywanie NaN: nie można użyć indexOf() lub includes(), aby znaleźć wartość NaN. Zbiór natomiast może przechowywać tę wartość.
  • Usuwanie duplikatów: obiekty zbiorów przechowują tylko unikalne wartości. Jeśli chcesz uniknąć przechowywania duplikatów, to jest to znacząca zaleta w stosunku do tablic, w których wymagany byłby dodatkowy kod do obsługi duplikatów.


Uwaga
: jeśli chcesz uzyskać pełną listę wbudowanych metod Set, odwiedź MDN Web Docs.


Złożoność czasowa

Metody stosowane przez tablicę do wyszukiwania elementów mają liniową złożoność czasową O(N). Innymi słowy, czas działania zwiększa się z taką samą szybkością, jak zwiększa się rozmiar danych.

Natomiast metody używane przez zbiory do wyszukiwania, usuwania i wstawiania elementów mają złożoność czasową wynoszącą tylko O(1) - co oznacza, że rozmiar danych praktycznie nie ma wpływu na czas działania tych metod!

Uwaga: jeśli chcesz dowiedzieć się więcej o złożoności czasowej, sprawdź ten artykuł.


O ile szybsze są zbiory od tablic

Chociaż czas działania może się znacznie różnić w zależności od używanego systemu, wielkości dostarczanych danych i innych zmiennych, to mam nadzieję, że moje wyniki dadzą praktyczne wyobrażenie o tym, o ile szybsze mogą być zbiory. Podzielę się tutaj dwoma przeprowadzonymi przeze mnie testami oraz ich wynikami.


Przygotowanie testów

Przed uruchomieniem jakichkolwiek testów utwórzmy tablicę oraz zbiór zawierający po milion wpisów. Dla uproszczenia zacznę od 0 i policzę do 999,999.

let arr = [], set = new Set(), n = 1000000;
for (let i = 0; i < n; i++) {
  arr.push(i);
  set.add(i);
}


Test 1: w poszukiwaniu elementu

Na początek znajdźmy liczbę 123123, która zwróci true:

let result;
console.time('Array'); 
result = arr.indexOf(123123) !== -1; 
console.timeEnd('Array');
console.time('Set'); 
result = set.has(123123); 
console.timeEnd('Set');

  • Tablica: 0.173ms
    Set: 0.023ms
  • Set był 7.54 raza szybszy


Test 2: usuwanie elementu

Na koniec usuńmy element z każdej kolekcji (możemy użyć tej, którą właśnie dodaliśmy). Nie ma do tego wbudowanej metody tablicy, dlatego stworzymy helper, aby wszystko było na miejscu:

const deleteFromArr = (arr, item) => {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
};


Oto kod dla naszego testu:

console.time('Array'); 
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set'); 
set.delete(n);
console.timeEnd('Set');

  • Tablica: 1.122ms
    Set: 0.015ms
  • Tym razem Set był aż o 74.13 raza szybszy!


Ogólnie rzecz biorąc, widzimy, że można znacznie poprawić czas uruchomienia, używając Set zamiast tablicy. Zobaczmy teraz kilka praktycznych przykładów, w których zbiory mogą być przydatne.


Przypadek 1: usuwanie duplikatów z tablicy

Jeśli chcesz szybko usunąć zduplikowane wartości z tablicy, możesz przekonwertować ją na zbiór. Jest to zdecydowanie najbardziej zwięzły sposób filtrowania unikalnych wartości:

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// If you want to turn the array into a Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// If you want to keep your values in an array
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]


Przypadek 2: pytanie z rozmowy kwalifikacyjnej w Google

W innym artykule omówiłem cztery sposoby odpowiedzi na pytania zadane podczas rozmowy kwalifikacyjnej w Google. Nasza rozmowa została przeprowadzona przy użyciu C++, ale gdyby to było JavaScript, zbiór byłby niezbędną częścią ostatecznego rozwiązania.

Oto krótkie podsumowanie ostatniego rozwiązania.


Pytanie

Biorąc pod uwagę nieuporządkowaną tablicę liczb całkowitych i wartość sum, zwróć wartość true, jeśli można dodać dowolne dwa elementy, aby były równe wartości sum. W przeciwnym razie zwróć false

Zatem, jeśli otrzymamy tablicę [3, 5, 1, 4] i wartość 9, nasza funkcja powinna zwrócić wartość true, ponieważ 4 + 5 = 9.


Rozwiązanie

Świetnym podejściem do tego pytania jest iteracja przez tablicę oraz tworzenie zbioru elementów w miarę upływu czasu. Zastosujmy ten sposób myślenia do powyższego przykładu. Kiedy napotkamy 3, możemy dodać 6 do naszego zbioru elementów, ponieważ wiemy, że musimy znaleźć sumę 9.

Następnie za każdym razem, gdy wejdziemy w kontakt z nową wartością w tablicy, możemy sprawdzić, czy znajduje się ona w naszym zbiorze elementów. Kiedy dojdziemy do 5, dodamy do naszego zbioru 4. Następnie, gdy w końcu napotkamy 4, znajdziemy go również w naszym zbiorze, abyśmy mogli zwrócić true.

Oto, jak to rozwiązanie może wyglądać:

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};


Oto krótsza wersja:

const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));


Ponieważ Set.prototype.has() ma złożoność czasową wynoszącą tylko O(1), użycie JavaScript Sets do przechowywania elementów, zamiast tablicy pomaga zapewnić całemu naszemu rozwiązaniu liniowy czas działania O(N).


Gdybyśmy byli natomiast zależni od Array.prototype.indexOf() lub Array.prototype.include(), z których oba mają złożoność czasową O(N), ogólny czas działania wyniósłby O(N²). To dużo wolniej!

Mam nadzieję, że dobrze ukazałem Wam przydatność Set z JavaScript!

Rozpocznij dyskusję

Lubisz dzielić się wiedzą i chcesz zostać autorem?

Podziel się wiedzą z 160 tysiącami naszych czytelników

Dowiedz się więcej