Fragmentalna Kasadowanie: Pojedyncza Binarne Przeszukiwanie Poprzez Wiele List

Problem: wielokrotne wyszukiwania w powiązanych listach

Rozważmy sytuację, która jest typowa dla geometrii obliczeniowej: zbiór k segmentów linii przecinanych przez rodzinę pionowych linii, gdzie na każdej pionowej linii musisz wiedzieć, które segmenty przecinające ją znajdują się natychmiast nad i pod punktem zapytania. Jeśli każdy plaster jest przechowywany jako osobny posortowany tablica współrzędnych y, odpowiadanie pojedynczemu zapytaniu oznacza prowadzenie oddzielnego wyszukiwania binarnego na każdym z k plasterów, co daje O(k log n) czasu na zapytanie, nawet jeśli plasty są blisko ze sobą powiązane i ich posortowane kolejności prawie nie zmieniają się między plasterami. Ten wzorzec pojawia się stale: drzewa zakresów wielopoziomowych, struktury lokalizacji punktów na płaszczyźnie, zapytania o stłumienie przedziałów i schematy indeksowania wielopoziomowego w bazach danych – wszystkie mierzą się z tą samą postacią problemu, gdzie pojedyncze zapytanie logiczne wymaga odpowiedzi od każdego poziomu hierarchii posortowanych danych. Stratą jest to, że każde wyszukiwanie binarne zasadniczo odkrywa informacje, które poprzednie wyszukiwanie już implikowało, ponieważ kolejne listy w tych aplikacjach mają tendencję do bycia strukturalnie podobnymi, różniąc się jedynie kilkoma elementami dodanymi, usuniętymi lub przesuniętymi między poziomami.

Budowanie mostów: rozszerzanie każdej listy o próbki z sąsiedniej

Krok budowy frakcyjnego spadkowania przetwarza łańcuch list wykorzystując odwrócony podział, zaczynając od ostatniej listy i przechodząc do pierwszej. W każdym kroku każda lista jest rozszerzana o dodatkowe próbki pobrane z kolejnej listy. Konkretnie, co drugie (w przybliżeniu połowę) elementów rozszerzonej wersji listy i+1 wstawia się do listy i jako element mostowniczy, łączy je w uporządkowany podział listy i oraz oznaczony jest wskazywacz wskazujący na jego oryginalną pozycję w liście i+1. Oznacza to, że rozszerzona lista i ma przybliżoną tę samą wielkość asymptotyczną co pierwotna, ponieważ szeregi geometryczne halowania rozmiarów próbek sumują się do stałego czynnika, ale teraz zawiera wbudowane wskazówki prowadzące do następnej listy. Po tym wstępnym przetwarzaniu każdy element w rozszerzonej liście posiada odniesienie do najbliższego elementu mostowego w kolejnej liście łańcucha, dzięki czemu, gdy znajdziesz pozycję zapytania w jednej rozszerzonej liście, podążanie za powiązanym z nią wskazywaczem prowadzi Cię do małego, stałej wielkości obszaru w pobliżu prawidłowej pozycji w następnej liście, nawet bez znajomości szczegółowego składu tej następnej listy.

Zapytanie: pojedyncza wyszukiwanie binarna, następnie operacje o stałej złożoności

Po zbudowaniu rozszerzonej struktury, odpowiadając na zapytanie o klucz x, najpierw wykonuje się standardowe wyszukiwanie binarne dla x w rozszerzonym pierwszym podzbiorze, kosztujące zwykle O(log n) czasu. Następnie, na każdym kolejnym poziomie, zamiast przeszukiwać od zera, algorytm śledzi wskazany punkt mostu powiązany z najbliżej położonym elementem, aby skoczyć do przybliżonej pozycji w następnym rozszerzonym podzbiorze, a następnie wykonuje niewielką operację o stałej wielkości, zwykle porównując się z maksymalnie dwoma lub trzema sąsiednimi elementami, aby precyzyjnie określić prawidłową pozycję na tym poziomie. Ponieważ gęstość próbkowania gwarantuje, że punkty mostu kolejnych poziomów są blisko siebie w stosunku do już znanej lokalizacji zapytania, ta korekcja lokalna nigdy nie wymaga więcej niż O(1) porównań na poziomie. Całkowity koszt na k poziomów wynosi O(log n) dla pierwszego wyszukiwania plus O(k) dla operacji o stałej złożoności poprzez skoki przez pozostałe poziomy, co stanowi znaczną poprawę w stosunku do naiwnego O(k log n), zwłaszcza gdy liczba poziomów k rośnie w stosunku do rozmiaru pojedynczego podzbioru.

Dlaczego to działa: intuicja struktury katalogu

Aby zrozumieć frakcjonujące spadki, można wyobrazić sobie łańcuch katalogów zamówionych na wynos, w którym każdy katalog jest posortowaną listą przedmiotów, a każdy katalog dodatkowo zawiera garść reprezentatywnych wpisów pobranych z kolejnego katalogu w łańcuchu wraz z odniesieniem do strony w tym katalogu. Jeśli znasz przybliżoną pozycję produktu w katalogu pierwszym i katalog pierwszy zdarza się, że również listuje próbny wpis z katalogu drugiego tuż obok tej pozycji, wraz z numerem strony w tym katalogu, możesz prawie bezpośrednio przejść do odpowiedniej okolicy w katalogu drugim bez ponownego przeszukiwania go od początku. Matematyka stojąca za tym, dlaczego pobieranie każdego drugiego elementu wystarcza, a nie konieczne jest pobieranie wszystkiego, opiera się na fakcie, że przerwy między sąsiednimi próbkami w rozszerzonej liście są ograniczone, więc niezależnie od tego, gdzie znajduje się prawdziwa odpowiedź pomiędzy dwoma sąsiadującymi próbkami, położenie prawdy w niezmodyfikowanej liście wyższego poziomu można znaleźć, sprawdzając tylko określoną liczbę sąsiednich elementów wokół znanego targeta pozycji próbki, nigdy nie wymagając nowego przeszukiwania z nieznanego punktu początkowego.

Zastosowania poza geometrią

Chociaż spadkowość frakcyjna została wynaleziona, aby przyspieszyć lokalizację punktów na płaszczyźnie i związane z nią algorytmy geometryczne, jej podstawowy wzorzec – unikanie powtarzania wyszukiwania, gdy już wiemy, gdzie szukać w przybliżeniu – pojawia się w całym zakresie systemów i projektowania algorytmów. Drzewa zakresowe warstwowe dla zapytań o zakres prostopadły w dwóch lub więcej wymiarach wykorzystują spadkowość frakcyjna między poziomami, aby odpowiadać na zapytania wielowymiarowe w czasie zbliżonym do tego, jaki kosztowałby pojedynczego wymiarowego wyszukiwanie binarny. Iteracyjne algorytmy, które wielokrotnie zapytywają łańcuch wersji zmieniającej się struktury posortowanej, takiej jak niektóre implementacje persistencji danych, korzystają ze spadkowych wskaźników między kolejnymi wersjami. Nawet poza formalnym programowaniem komputerowym, ta podstawowa idea pojawia się nieformalnie w systemach, które utrzymują wiele posortowanych indeksów dla tego samego lub bardzo podobnych danych i chcą uniknąć zbędnych wyszukiwań, takich jak schematy wielo-rozdzielczości lub wielopoziomowego indeksowania w bazach danych i silnikach wyszukiwania, gdzie zapytanie musi być rozwiązane spójnie w ramach hierarchii powiązanych posortowanych widoków danych, które nie ulegają znacznym zmianom z poziomu na poziom.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Fractional Cascading: One Binary Search Through Many Lists i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.