W IT , szczególnie w algorytmiczne , A lista pomijania lub lista rozjazdy , czy lista skok jest struktura danych probabilistyczny, na podstawie połączonego list równolegle. Większość jego operacji jest wykonywana w czasie O (log n ) z dużym prawdopodobieństwem, gdzie n to liczba elementów zawartych w liście.
Do Pomiń listę zostały wymyślone przez Williama Pugh , po raz pierwszy zaprezentowany w raporcie technicznym w 1989 roku, a następnie prezentowane w publikacji w roku 1990. Autor, w jego raport techniczny porównuje je ze zrównoważonych wyszukiwania binarnych drzew , pisze:
Listy pomijania to probabilistyczna struktura danych, która wydaje się zastępować drzewa zrównoważone jako preferowaną metodę implementacji dla wielu zastosowań. Algorytmy pomijania listy mają takie same asymptotyczne oczekiwane ograniczenia czasowe, jak drzewa zrównoważone, są prostsze, szybsze i zajmują mniej miejsca.
( Listy pomijania to struktura danych, która wydaje się przewyższać zrównoważone drzewa (pliki binarne wyszukiwania) jako preferowana metoda implementacji dla wielu aplikacji. Algorytmy list pomijania mają taką samą oczekiwaną asymptotyczną złożoność jak wały zrównoważone i są prostsze, szybsze i zużywają mniej pamięci)
A lista Przejdź prezentowana jest jako poprawa o klasyfikowane połączonej listy . Zawiera dodatkowe wskaźniki do przodu, dodawane losowo, dzięki czemu wyszukiwanie na liście może "przeskoczyć" ( by pominąć angielski) wiele pozycji.
Lista pomijania jest zorganizowana w warstwy . Najniższa warstwa to po prostu standardowa lista połączona . Każda górna warstwa i +1 jest „ szybkim pasem ” do pokonywania niższych warstw 1,…, i . Element znajdujący się na warstwie i ma stałe prawdopodobieństwo p bycia częścią warstwy i +1. Przeciętnie każdy element pojawia się w warstwach 1 / (1- p ), a najwyższy element (często element atrapy mniejszy niż wszystkie inne) pojawia się we wszystkich warstwach. Lista pomijania zawiera warstwy O (log 1 / p n ), gdzie n jest całkowitą liczbą elementów.
Poniższy przykład przedstawia listę pomijania zawierającą 10 elementów z 4 warstwami:
couche 4 1 couche 3 1-----4---6 couche 2 1---3-4---6-----9 couche 1 1-2-3-4-5-6-7-8-9-10Wyszukiwanie rozpoczyna się od najmniejszego elementu na najwyższej warstwie. Dla każdej odwiedzanej warstwy przechodzimy przez linki, aż dotrzemy do ostatniego elementu mniejszego lub równego poszukiwanemu elementowi. Jeśli więc ten element jest ściśle niższy niż pożądana wartość, schodzimy pionowo do następnej warstwy. Oczekiwana liczba kroków w każdej warstwie wynosi 1/ p . Całkowity koszt badań wynosi w ; co równa się, jeśli uznamy p za ustalone.
Dostosowując wartość tego parametru p , uzyskuje się kompromis między czasem wyszukiwania a zużywaną przestrzenią pamięci. Dla p = 0, lista pomijania jest standardową listą połączoną (tylko jedna warstwa). Im bliżej p do 1, tym więcej warstw.
Wstawianie i usuwanie jest realizowane jak w połączonej liście, z wyjątkiem tego, że elementy „na górze” muszą być wstawiane i usuwane na wielu warstwach.
Ze względu na swój probabilistyczny charakter , ta struktura danych nie daje takich samych gwarancji co do najgorszych przypadków, jak na przykład drzewa zrównoważone . Rzeczywiście, jest bardzo mało prawdopodobne, ale mimo to możliwe, że losowy układ mógł wytworzyć bardzo niezrównoważoną strukturę.
W rzeczywistości listy te działają bardzo dobrze w praktyce i uważa się, że są łatwiejsze do wdrożenia niż ich deterministyczny odpowiednik przywracania równowagi. W rzeczywistych implementacjach zmierzyliśmy, że ich wydajność w czasie i przestrzeni jest niższa niż w przypadku B-drzewa . Wynika to z problemów, takich jak bliskość danych w pamięci podręcznej.
W deterministycznych listach pomijania elementy do pominięcia nie są wybierane losowo, ale w sposób deterministyczny.