Jak działa lista pominięć?

Aby wykonać zadanie domowe, muszę zrozumieć, jak działa lista pominięć.

Programuję od nieco ponad 2 lat (wiem, że w rzeczywistości nie jest to tak długo) i nigdy nie słyszałem o liście pominięć.

Przejrzałem wszystkie przewodniki, które mogę znaleźć, i wciąż ledwo rozumiem, jak one działają. Przeszukałem nawet Code Review dla przykładowej implementacji i znalazłem tylko jedną recenzję; i nie jest to nawet pełna implementacja. Przejrzałem przykładową implementację dostarczoną przez kurs i jest to absolutnie okropne. Pomiędzy brakiem odpowiednich metod a jednoznakowymi nazwami zmiennych nie mam pojęcia, jak to działa.

Jak działa lista pominięć? Czy znajomość listy pominięć jest wymagana do zrozumienia bardziej zaawansowanych struktur danych?

W dawnych czasach w klasie struktur danych dowiedzieliśmy się, jak działają drzewa AVL . Miałbym to na jednej z moich zajęć, ale instruktor powiedział „nigdy tak naprawdę tego nie użyjesz”, zamiast tego zamiast tego nauczylibyśmy 2-3 drzewa i b * drzewa. To były dni, kiedy pamięć była napięta, a procesy były pojedynczo powiązane. Nie użyłeś znaku deque, gdy pojedynczo połączona lista działałaby równie dobrze.

Lista pominięć jest dziś znacznie bardziej powszechna, a problemem jest większa ilość dostępnej pamięci i współbieżności (nie musisz wcale dużo blokować, gdy działasz jako pisarz na liście pominięć - w porównaniu do wszystkiego z drzewem AVL).

Szczerze mówiąc, jest to teraz moja ulubiona struktura danych, ponieważ mogę z łatwością zrozumieć, jak działa pod spodem i gdzie będzie to korzystne lub niekorzystne w użyciu.

Nie będziesz musiał pisać od zera (chyba, że ​​dostaniesz to jako pytanie do rozmowy kwalifikacyjnej - ale równie prawdopodobne jest, że zaimplementujesz drzewo AVL).

Ci mają zamiar trzeba zrozumieć, dlaczego chcesz wybrać ConcurrentSkipListMapw Javie zamiast HashMaplub TreeMaplub którykolwiek z pozostałych implementacji map.

Aby zrozumieć, jak to działa, musisz zrozumieć, jak działa drzewo binarne. Poczekaj, pozwól mi to poprawić. Musisz zrozumieć, jak działa zrównoważone drzewo binarne. Bez zrównoważenia drzewa binarnego jego wyszukiwanie nie daje żadnej realnej korzyści.

Powiedzmy, że mamy to drzewo:

I wstawiamy do niej „8”. Teraz mamy:

I to nie jest zrównoważone. Idziemy więc magicznie równoważąc to poprzez jakieś wdrożenie ...

I znów masz zrównoważone drzewo. Ale to było dużo magii, machnąłem ręką.

Zróbmy listę pominięć.

Ten okazuje się być idealizowany. Niewiele jest, ale pokazuje zrównoważoną naturę drzewa binarnego, którą ideał skiplist przybliża.

Teraz chcemy wstawić tam 6. To wstawia go podobnie jak połączoną listę. Zaczynamy jednak u góry i schodzimy w dół. Najwyższe punkty do 5. Czy 6> 5? Tak. Ok, najwyższe punkty są teraz do końca, więc schodzimy na stos (jesteśmy na 5). Następny jest 7. Czy 6> 7? Nie. Więc schodzimy o poziom i jesteśmy na poziomie podstawowym, więc wstawiamy 6 po prawej stronie 5.

Rzucamy monetą - głowy, które budujemy, ogony zostajemy. Ogony Nic więcej nie trzeba robić.

Pozwala wstawić teraz 8. 8> 5? tak. 8> 7? Tak. A teraz znów jesteśmy na najniższym poziomie po kolejnych strzałkach i stosie i testujemy 8> 11? Nie. Więc wstawiamy 8 po prawej stronie 7.

Rzucamy monetą - głowy, które budujemy, ogony zostajemy. Ogony Nic więcej nie trzeba robić.

W zrównoważonym drzewie wszyscy bylibyśmy zaniepokojeni tym, że drzewo nie jest teraz zrównoważone. Ale to nie jest drzewo - to lista pominięć. Mamy zbliżenie zrównoważona drzewo.

Teraz wstawmy 10. Uniknę wszystkich porównań.

Rzucamy monetą - głowy, które budujemy, ogony zostajemy. Heads! I odwróć to jeszcze raz, Heads znowu! Odwróć to jeszcze raz, ok, są ogony. Dwa poziomy powyżej podstawowej połączonej listy.

Zaletą jest to, że teraz, jeśli wstawimy 12, możemy przeskoczyć od 5 do 10 bez wykonywania wszystkich innych porównań. Możemy je pominąć za pomocą listy pominięć. I nie musimy się martwić o zrównoważone drzewo - probabilistyczny charakter układania robi to za nas.

Dlaczego to takie przydatne? Ponieważ przy wstawianiu 10 mogę to zrobić, blokując zapis na wskaźnikach 5 i 7 i 8 zamiast na całej strukturze. I kiedy to robię, czytelnicy mogą nadal przeglądać listę pominięć bez niespójnego stanu. W przypadku równoczesnego użytkowania jego szybsze nie trzeba blokować. Iteracja po dolnej warstwie jest szybsza niż drzewo (radość z algorytmów BFS i DFS do nawigacji po drzewie - nie musisz się o nie martwić).

Spotkasz to? Prawdopodobnie zobaczysz go w użyciu w miejscach. I wtedy dowiesz się, dlaczego autor wybrał tę implementację zamiast a TreeMaplub HashMapdla struktury.

Wiele z tego zostało zapożyczonych z mojego posta na blogu: The Skip List