Duże O tablic JavaScript


105

Tablice w JavaScript można bardzo łatwo modyfikować, dodając i usuwając elementy. To nieco maskuje fakt, że większość tablic językowych ma stały rozmiar i wymaga skomplikowanych operacji, aby zmienić rozmiar. Wygląda na to, że JavaScript ułatwia pisanie słabo działającego kodu tablicowego. To prowadzi do pytania:

Jakiej wydajności (pod względem dużej złożoności czasu O) mogę oczekiwać od implementacji JavaScript w odniesieniu do wydajności macierzy?

Zakładam, że wszystkie rozsądne implementacje JavaScript mają co najwyżej następujące duże O.

  • Dostęp - O (1)
  • Dołączanie - O (n)
  • Prepending - O (n)
  • Wstawienie - O (n)
  • Usunięcie - O (n)
  • Zamiana - O (1)

JavaScript umożliwia wstępne wypełnienie tablicy do określonego rozmiaru przy użyciu new Array(length)składni. (Pytanie dodatkowe: czy tworzy tablicę w ten sposób O (1) lub O (n)) To jest bardziej jak konwencjonalna tablica i jeśli jest używana jako tablica o ustalonym rozmiarze, może pozwolić O (1) na dołączanie. Jeśli dodana jest logika bufora cyklicznego, można uzyskać wyprzedzanie O (1). Jeśli używana jest tablica rozwijana dynamicznie, O (log n) będzie średnim przypadkiem dla obu z nich.

Czy mogę spodziewać się lepszej wydajności w niektórych przypadkach niż moje założenia? Nie spodziewam się, że cokolwiek zostanie opisane w żadnych specyfikacjach, ale w praktyce może się zdarzyć, że wszystkie główne implementacje używają zoptymalizowanych tablic za kulisami. Czy działają dynamicznie rozwijające się tablice lub inne algorytmy zwiększające wydajność?

PS

Zastanawiam się nad tym, ponieważ badam niektóre algorytmy sortowania, z których większość wydaje się zakładać, że dołączanie i usuwanie to operacje O (1), opisując ich ogólne duże O.


6
Konstruktor Array z rozmiarem jest praktycznie bezużyteczny w nowoczesnych implementacjach JavaScript. W tej postaci pojedynczego parametru nie robi prawie nic. (Ustawia, .lengthale to wszystko.) Tablice nie różnią się zbytnio od zwykłych instancji Object.
Pointy

3
Ustawianie lengthwłaściwości i wstępne przydzielanie miejsca to dwie zupełnie różne rzeczy.
Pointy

1
@Pointy: Czy spodziewam się zbyt wiele, kiedy oczekuję, że ustawienie array[5]a new Array(10)jest O (1)?
Kendall Frey,

1
Chociaż ECMAScript nie definiuje sposobu implementacji obiektu Array (definiuje tylko niektóre reguły semantyczne), jest bardzo możliwe, że różne implementacje będą optymalizować dla oczekiwanych przypadków (np. Mają "rzeczywistą tablicę" dla tablic o rozmiarze mniejszym niż n ). Nie jestem zbyt biegły w implementacjach, ale byłbym naprawdę zaskoczony, gdyby nie zostało to gdzieś zrobione ...

5
@KendallFrey „Najlepsza odpowiedź” prawdopodobnie napisze kilka przypadków testowych jsperf dla różnych wzorców n / dostępu i zobaczy, co z tego

Odpowiedzi:


111

UWAGA: Chociaż ta odpowiedź była poprawna w 2012 roku, obecnie silniki używają bardzo różnych wewnętrznych reprezentacji zarówno obiektów, jak i tablic. Ta odpowiedź może być prawdą lub nie.

W przeciwieństwie do większości języków, które implementują tablice z tablicami, w JavaScript tablice są obiektami, a wartości są przechowywane w tablicy haszującej, podobnie jak zwykłe wartości obiektów. Takie jak:

  • Dostęp - O (1)
  • Dołączanie - amortyzowane O (1) (czasami wymagana jest zmiana rozmiaru tablicy hashy; zwykle wymagane jest tylko wstawienie)
  • Prepending - O (n) via unshift, ponieważ wymaga ponownego przypisania wszystkich indeksów
  • Wstawienie - amortyzowane O (1), jeśli wartość nie istnieje. O (n), jeśli chcesz przesunąć istniejące wartości (np. Używając splice).
  • Usunięcie - amortyzowane O (1), aby usunąć wartość, O (n), jeśli chcesz ponownie przypisać indeksy za pośrednictwem splice.
  • Zamiana - O (1)

Ogólnie rzecz biorąc, ustawienie lub anulowanie dowolnego klucza w dyktowaniu jest amortyzowane O (1), i to samo dotyczy tablic, niezależnie od tego, jaki jest indeks. Każda operacja, która wymaga zmiany numeracji istniejących wartości to O (n) po prostu dlatego, że musisz zaktualizować wszystkie wartości, których to dotyczy.


4
Czy na początku nie powinno być O (n)? Ponieważ wszystkie indeksy muszą zostać przesunięte. To samo dotyczy wstawiania i usuwania (w dowolnym indeksie i przesuwania / zwijania elementów).
nhahtdh

2
Ponadto, jest lengthustawiony na mutację Array, czy też getna niej osiągnie długość i prawdopodobnie ją zapamięta?
Alex

27
Warto wspomnieć, że ta odpowiedź nie jest już poprawna. Nowoczesne silniki nie przechowują tablic (lub obiektów z indeksowanymi kluczami całkowitymi) jako tabele skrótów (ale podobnie jak ... tablice, jak w C), chyba że są one rzadkie. Aby zacząć, oto
``

4
Czy jest to zdefiniowane w standardzie, czy jest to tylko powszechna implementacja w silnikach JS? A co z V8?
Albert

4
@BenjaminGruenbaum byłoby miło, gdybyś mógł trochę rozwinąć sposób ich przechowywania. Lub podaj źródła.
Ced

1

gwarancja

Nie ma określonej gwarancji złożoności czasowej dla żadnej operacji na tablicy. Sposób działania tablic zależy od podstawowej struktury danych wybranej przez silnik. Silniki mogą również mieć różne reprezentacje i przełączać się między nimi w zależności od pewnych heurystyk. Początkowy rozmiar tablicy może być taką heurystyką, ale nie musi.

rzeczywistość

Na przykład, V8 zastosowań (jak dzisiaj) oba hashtables i listy tablicy do reprezentowania tablic. Ma również różne reprezentacje obiektów, dlatego nie można porównywać tablic i obiektów. Dlatego dostęp do tablicy jest zawsze lepszy niż O (n), a nawet może być tak szybki, jak dostęp do tablicy w C ++. Dołączanie jest O (1), chyba że osiągniesz rozmiar struktury danych i musisz ją przeskalować (czyli O (n)). Gorzej jest z udawaniem. Usunięcie może być jeszcze gorsze, jeśli zrobisz coś takiego delete array[index](nie!), Ponieważ może to zmusić silnik do zmiany swojej reprezentacji.

Rada

Użyj tablic dla numerycznych struktur danych. Do tego są przeznaczone. Właśnie pod tym kątem silniki będą je optymalizować. Unikaj rzadkich tablic (lub, jeśli musisz, spodziewaj się gorszej wydajności). Unikaj tablic z mieszanymi typami danych (ponieważ to sprawia, że ​​reprezentacje wewnętrzne są bardziej złożone ).

Jeśli naprawdę chcesz zoptymalizować dla określonego silnika (i wersji), sprawdź jego kod źródłowy, aby uzyskać absolutną odpowiedź.


Poczekaj chwilę, możemy mieć tablice z mieszanymi typami danych? Javascript jest super!
Anurag

Dokładnie @Anurag, ale w 99% przypadków nie potrzebujesz tej funkcji
Desiigner
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.