Pytanie Czy wyszukiwanie mapy w Elixir O (1)?


Zapewnienie struktur dyktowania / map opartych na tabelach Hash O(1) czas wyszukiwania. Mimo to widzę konsekwencje, które w Elixir znajdowanie pasującej funkcji głowy jest szybsze niż wyszukiwanie czegoś na mapie.

Na przykład Eliksir String.Unicode  kompiluje listę znaków Unicode w wielu głowicach funkcyjnych, więc odpowiedź na pytanie: "co to jest wersja é", znajduje odpowiedź na pytanie, do czego służy funkcja upcase który oczekuje "é".

Nie wiem, dlaczego byłaby to szybsza lub bardziej wydajna pamięć niż posiadanie singla upcase głowa funkcji, która wyszukuje "é" na mapie.

Podobnie, pokazując, jak zbudować bibliotekę I18n w "Metaprogramming Elixir", Chris McCord nadaje każdemu kluczowi tłumaczącemu swoją własną funkcję i mówi:

"Poprzez generowanie nagłówków funkcji dla każdego mapowania tłumaczeń, ponownie pozwalamy na przejęcie Maszyny wirtualnej w celu szybkiego wyszukiwania."

Czy mapy w eliksirie nie zapewniają wyszukiwania O (1)? Czy znalezienie pasującej funkcji głowy O (1)? Po co decydować się na kompilowanie listy statycznej wielu głowom funkcyjnym zamiast po prostu przechowywać ją na mapie?


11
2018-02-28 02:05


pochodzenie


Pamiętaj tylko, że analiza złożoności nie jest szybka. Jedna funkcja O (1) może działać dziesięć razy szybciej niż inna. W każdym przypadku, mieszanie nie jest O (1). Może podchodzić lub amortyzować do O (1) w pewnych okolicznościach (probabilistycznie O (1)), ale kolizje zawsze będą je przesuwać w stronę O (n). - paxdiablo
gist.github.com/BinaryMuse/bb9f2cbf692e6cfa4841 wydaje się wskazywać nie - Frederick Cheung
@ Paxdiablo Rozumiem, że złożoność! = szybkość, i to jest dobra uwaga. Jeśli chodzi o kolizje, nie widzę, w jaki sposób dążą do O (N). Tabela mieszająca ograniczy liczbę kluczy na wiadro - np. Może maksymalnie do 10. Zatem wyszukiwanie w wiadrze nigdy nie jest dłuższe niż 10 kontroli, a zatem O (1), prawda? Z dobrym hashiem potrzeba rehashu powinna być coraz rzadziej - np. Za każdym razem, gdy powtarzamy, musimy wykonać dwukrotnie więcej pracy niż ostatnio, ale zajęło nam to dwa razy więcej czasu, więc amortuje się do O (1). Jeśli w jakiś sposób nowe klucze wciąż płyną w tym samym wiadrze, to jest to złe hashing, prawda? - Nathan Long
@Nathan, jeśli możesz ograniczyć dane, wszystkie algorytmy stają się O (1). Analiza złożoności dotyczy arbitralnych danych. Możesz przesunąć problem dalej na odległość, na przykład za pomocą skrótów haszu, ale bez ograniczeń danych, problem zawsze będzie istniał. - paxdiablo
@paxdiablo :) Tak, ale jestem dość pewny, że ograniczenie liczby kluczy na wiadro jest konieczne, aby tabele miały wydajność O (1). Jestem nie Mówiąc, ogranicz liczbę przedmiotów w haszyszu, po prostu ponownie wszystko szatamy, gdy kubełki stają się zbyt pełne. Zaimplementowałem hasz i napisałem o tym na stronie nathanmlong.com/2015/10/reimplementing-rubys-hash - może przejdź do "Czy osiągnęliśmy O (1)?" Myślę, że może w jakiś sposób się nie rozumiemy - brzmisz, jakbyś wiedział, o czym mówisz i jestem prawie pewna, że ​​ja też. :) - Nathan Long


Odpowiedzi:


Mapy eliksirów nie są mieszkanie tablice danych oparte na hash-table. Małe mapy są uporządkowanymi listami, na których mapa ma <= 31 wpisów. Kiedy mapa dostaje 32 wpisy, zmienia się w hash, który ma odnośnik O(log n). Niezmienne, bazujące na tabelach tabelarycznych bazy danych byłyby w końcu bardzo kosztowne do zaktualizowania, co jest podstawową metodą "budowania" jednego z tych datastruktur. Zmiana jednej wartości wymagałaby zaktualizowania nowej mapy za pomocą jeszcze tylko jednego elementu. Opierają się one na uporczywych hadhmaps Rich Hickey, które są swego rodzaju mapowaniem tablicy haszów.

Złożoność dopasowania głowy funkcji jest O(n) najgorszy przypadek, ale może być zoptymalizowany przez kompilator w sposób, którego nie rozumiem w pełni. W niektórych przypadkach może przekształcić niektóre wzory główki funkcji w drzewo. Ale ponieważ dopasowania funkcji head nie mają całkowitej kolejności i muszą być zgodne w kolejności, w której są zdefiniowane, ilość optymalizacji jest dość ograniczona. Być może po prostu będziesz mieć szczęście w korzystaniu z części funkcji head match, które są bardzo niskie, a także w drzewie kolejności dopasowywania funkcji.

Każdy krok w głowę jest również lekki i wysoce zoptymalizowany, gdzie mapy są wciąż całkiem nowe i istnieją pewne optymalizacje wydajności, które można uzyskać. Na przykład złożoność funkcji mieszającej nie jest prosta, jeśli klucz jest złożony / zagnieżdżony (proste liczby całkowite mają jednak bardzo szybkie funkcje skrótu). Ale w twoim przykładzie na Unicode, stawiam standard unicode, z natury, w jaki sposób zamawia on id, umieszcza tyle z ich powszechnie używanych znaków na froncie. To prawdopodobnie bardzo ułatwia VM optymalizację i uzyskanie bardzo dobre czasy wyszukiwania. Jestem pewien, że gdybyś spojrzał na mało znany alfabet, zmieniłaby się twoja złożoność.

Ale powodem, dla którego nie należałoby po prostu dynamicznie generować modułu z dopasowaniem funkcji, ponieważ sposób wyszukiwania danych polega na tym, że wyrzuciliby Państwo stan globalny, w szczególności moduł code_server. Niektóre wyszukiwania mogą pójść szybciej, ale przyspieszenia prawdopodobnie spowolniłyby, gdy struktura danych powiększyłaby się.


16
2018-02-28 16:38



Czy miałeś na myśli, że hash trie ma odnośnik O(log n) i nie O(n log n)? - Wile E. Coyote
@ Dogbert też myślałem O(n log n) był zbyt nieefektywny, by uzyskać mapę. - dotslash