Właśnie przeczytałem to pytanie: Czy są słowniki w JavaScript jak Python?

Jedna z odpowiedzi powiedziano, że możesz użyć obiektów JavaScript, takich jak słowniki Python. Czy to prawda? Jaki jest wydajność wyszukiwania kluczy w obiekcie? Czy to O (1)? Jest dodawanie klucza do obiektu również stały czas (mieszanie)?

57
Saher Ahwal 9 październik 2011, 06:07

3 odpowiedzi

Najlepsza odpowiedź

V8 Design Docs sugeruje wyszukiwanie, które będą co najmniej tak szybko, jeśli nie szybsze:

Większość silników JavaScript używają struktury danych podobnej do słownika jako Przechowywanie właściwości obiektu - każdy dostęp do nieruchomości wymaga Dynamic Lookup, aby rozwiązać lokalizację właściwości w pamięci. To podejście zapewnia dostęp do nieruchomości w javascript wolniej niż dostęp do zmiennych instancji w językach programowania, takich jak Java i smalk. W tych językach znajdują się zmienne instancji przy stałych przesunięciach określonych przez kompilator ze względu na stały obiekt układ zdefiniowany przez klasę obiektu. Dostęp jest po prostu kwestią ładunek pamięci lub sklep, często wymaga tylko jednej instrukcji.

Aby zmniejszyć czas potrzebny do uzyskania dostępu do właściwości JavaScript, V8 Nie używaj dynamicznego wyszukiwania, aby uzyskać dostęp do właściwości. Zamiast tego v8 dynamicznie Tworzy ukryte klasy za kulisami. [...] w V8 zmienia się obiekt jego ukryta klasa, gdy dodano nową właściwość.

Brzmi, jak dodanie nowego klucza może być nieco wolniejsze, ze względu na utworzenie klas ukrytych.

61
Domenic 9 październik 2011, 03:26

Tak, możesz założyć, że dodanie klucza, a później przy użyciu go do dostępu są efektywnie Studhistly Constant Time Operations.

Pod maską Engine JS może zastosować niektóre techniki, aby zoptymalizować kolejne wyszukiwania, ale do celów dowolnego algorytmu można założyć O (1).

21
Peter 9 październik 2011, 03:45

Oprócz domenic's Odpowiedź, większość współczesnych silników JS używają całkowanej techniki, aby przyspieszyć dostęp do nieruchomości obiektu. Technika opiera się na tak zwanych klasach Hidden lub kształty . Ważne jest, aby zrozumieć, jak ta optymalizacja działa, jeśli chcesz napisać wydajny kod JS.

JS Obiekt wygląda jak słownik, więc dlaczego nie używać jednego do przechowywania właściwości? Tabela Hash ma O (1) złożoność dostępu, wygląda na dobre rozwiązanie. Właściwie, pierwsze silniki JS wdrożyły obiekty w ten sposób. Ale w statycznych językach napisanych, takich jak C ++ lub Java dostęp do nieruchomości w klasie jest szybki błyskawiczny. W takich językach instancja klasowa jest tylko segmentem pamięci, koniec Każda nieruchomość ma swój własny stały przesunięcie, więc aby uzyskać wartość nieruchomości, musimy wziąć wskaźnik instancji i dodać offset do niego. Innymi słowy, w czasie kompilacji Wyrażenie takie jak ten point.x jest właśnie zastąpiony adresem w pamięci.

Może być możemy wdrożyć podobną technikę w JS? Ale jak? Spójrzmy na prostą funkcję JS:

function getX(point) {
  return point.x;
}

Jak uzyskać wartość point.x? Pierwszym problemem jest tutaj, że nie mamy klasy (ani kształtu), który opisuje point. Ale możemy obliczyć jeden, to właśnie robią współczesne silniki JS. Większość obiektów JS w czasie wykonania ma kształt, który jest związany obiektem. Kształt opisuje właściwości obiektu i gdzie przechowywane są wartości właściwości. Jest bardzo podobny do sposobu, w jaki definicja klasy opisuje klasę w C ++ lub Java. To dość duże pytanie, jak obliczany jest kształt obiektu, nie opiszę go tutaj. Polecam Ten artykuł który zawiera wielkie wyjaśnienie kształtów, a Ten post, który wyjaśnia, w jaki sposób rzeczy są realizowane w V8. Najważniejszą rzeczą, którą powinieneś wiedzieć o kształtach, jest to, że wszystkie obiekty o tych samych właściwościach, które są dodawane w tej samej kolejności będą miały ten sam kształt. Istnieje kilka wyjątków, na przykład, jeśli obiekt ma wiele właściwości, które są często zmieniane, lub jeśli usuniesz niektóre właściwości obiektu za pomocą operatora delete, obiekt zostanie przełączony w tryb słownika i nie będzie miał kształt.

Teraz wyobraźmy sobie, że obiekt point ma tablicę wartości właściwości, a mamy dołączony do niego kształt, który opisuje, gdzie przechowywana jest wartość x w tej tablicy właściwości. Ale problem polega na tym, że możemy przekazać dowolny obiekt do funkcji, nie jest to nawet konieczne, aby obiekt ma właściwość {X2}}. Problem ten jest rozwiązany przez technikę zwaną Wymienny buforowanie. Jest całkiem proste, gdy getX() jest wykonywane po raz pierwszy, pamięta kształt punktu i wynik wyszukiwania x. Gdy funkcja nazywa się drugi raz, porównuje kształt punktu z poprzednim. Jeśli pasuje do kształtu nie jest wymagane wyszukiwanie, możemy wziąć poprzedni wynik wyszukiwania.

Podstawową opcję jest to, że wszystkie obiekty opisujące to samo powinny mieć ten sam kształt, tj. Powinny mieć ten sam zestaw właściwości, które są dodawane w tej samej kolejności. Wyjaśnia również, dlaczego lepiej jest zawsze zainicjować właściwości obiektu, nawet jeśli są undefined Domyślnie, Oto wielkie wyjaśnienie problemu.

Względne zasoby:

1
Valeriy Katkov 28 maj 2020, 12:45