Duże O tablic JavaScript

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.

_{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.

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ź.