Co jest dużym O dla tablicy JavaScript, gdy jest używane jako skrót?

Question

Jaka jest wielka szansa na uzyskanie dostępu do tablicy JavaScript, gdy jest używana jako skrót?

Na przykład

var x= []; 
for(var i=0; i<100000; i++){ 
    x[i.toString()+'a'] = 123; // using string to illustrate x[alpha] 
} 
alert(x['9999a']); // linear search? 

Można mieć nadzieję silniki JS nie użyje przeszukiwanie liniowe wewnętrznie O (n), ale jest to na pewno?

Answer 1

Przede wszystkim Tablice są w rzeczywistości skrótów. Zawsze. Dlatego x[5] === x["5"]:

var x = []; 
x[5] = 10; 
alert(x[5] === x["5"]); // true 

Obiekty są skróty i Tablice są tylko specjalne przedmioty. Jeśli chcesz używać ogólnych skrótów, wybierz Obiekty. "Tablice asocjacyjne" w JavaScript to Obiekty. Tablice są dla danych indeksowanych numerycznie. Tablice mają właściwość length i podobne do tablicowych metody, takie jak push, pop, sort itp., Co nie ma sensu być używane na skrótach.

Co do wielkiego O do wyszukiwania w obiektach: jest to zależne od implementacji .

Prawdopodobnie 2 najlepszych rzeczy można zrobić, aby:

1. sprawdzić kod źródłowy niektórych implementacjach przeglądarki

2. Czy jakieś odniesienia dla dużego n i zrobić wniosek

---

Związana część numeru language specification:

4.3.3 obiekt

Obiekt jest zbiorem właściwości i ma pojedynczy obiekt prototypowy.

8.6.2 Właściwości obiektu wewnętrzne i metody

obiektów macierzy mają nieco inną realizację [[DefineOwnProperty]] wewnętrzną metodą . Obiekty Array dają specjalne traktowanie dla określonej klasy nazw nieruchomości.

Answer 2

Uzyskanie dostępu do właściwości obiektu i elementów tablicy w JavaScript jest składnie założone w constant time: O (1). Charakterystyki wydajności nie są gwarantowane w specyfikacji ECMAScript, ale wszystkie współczesne silniki JavaScript pobierają właściwości obiektów w stałym czasie.

Oto prosty przykład pokazujący, jak czas dostępu rosną, gdy pojemnik jest większe czasy X1000:

var largeObject = {}; 
var smallObject = {}; 

var x, i; 

for (i = 0; i < 1000000; i++) { 
    largeObject['a' + i] = i; 
} 

for (i = 0; i < 1000; i++) { 
    smallObject['b' + i] = i; 
} 

console.time('10k Accesses from largeObject'); 
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)]; 
console.timeEnd('10k Accesses from largeObject'); 

console.time('10k Accesses from smallObject'); 
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)]; 
console.timeEnd('10k Accesses from smallObject'); 

Wyniki w Firebug, Firefox 3.6.10 (Mac OS X 10.6.4 - 2,93 GHz Intel Core 2 Duo):

10k Accesses from largeObject: 22ms 
10k Accesses from smallObject: 19ms 

Wyniki w Chrome Dev Tools 6.0.472:

10k Accesses from largeObject: 15ms 
10k Accesses from smallObject: 15ms 

Internet EXPL orer 8.0.7600 z Firebug Lite na Windows 7

10k Accesses from largeObject: 250ms 
10k Accesses from smallObject: 219ms