Miękkie hałdy: czym jest korupcja i dlaczego jest przydatna?

Question

Niedawno przeczytałem papier Bernarda Chazelle za „miękki kupa, przybliżoną kolejki priorytetowej z Optimal Error Rate Bernard Chazelle” (http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf)

Papier dużo mówi o „korupcji”. Czym jest korupcja, w jaki sposób elementy ulegają uszkodzeniu i jak ci to pomaga?

Spędziłem dużo czasu czytając gazetę i Google, a to wciąż nie ma sensu.

Answer 1

Odpowiedź jest w drugą stronę.

„Miękka sterty może w każdej chwili zwiększyć wartość niektórych klawiszy Klawisze Takie i co za tym idzie, odpowiednie elementy, nazywane są uszkodzone korupcji. jest całkowicie według uznania struktury danych i użytkownik nie ma nad nią kontroli Naturalnie findmin zwraca błąd w postaci minimalnego klucza bieżącego, który może, ale nie musi, być uszkodzony . Korzyścią jest szybkość: podczas aktualizacji sterty, przedmioty podróżują razem w pakietach w formie "car pooling", aby zaoszczędzić czas Z teoretycznego punktu widzenia, korupcja jest sposobem na ecrease entropii danych przechowywanych w strukturze danych, a tym samym ułatwienia jej leczenia . Entropia jest zdefiniowana jako logarytm, w podstawie drugiej, o liczbie odrębnych przypisań klawiszy (tj. Entropii rozkładu jednorodnego dla przypisań klucza ). Aby zobaczyć solidność tego pomysłu, wypchnij go do granic możliwości i obserwuj, czy jeśli każdy klucz był uszkodzony przez podniesienie jego wartości do `, to zestaw kluczy miałby zero entropii i mogliśmy trywialnie wykonać wszystkie operacje w stałej czas. Co ciekawe, miękkie hałdy pokazują, że entropia nie musi spaść do zera oraz złożoność stać na stałym poziomie.”

Czy to autodestrukcyjne struktura danych?

Answer 2

W większości prac naukowych dotyczących kolejek priorytetowych, każdy element w kolejka ma przypisany numer nazywany priorytetem ustawionym po wstawieniu elementu Elementy są następnie usuwane z kolejki w kolejności rosnącego priorytetu Większość języków programowania obsługujących kolejki priorytetowe w rzeczywistości nie używa wyraźnych priorytetów i zamiast tego bazuje na porównaniu funkcja do pozycjonowania elementów, ale miękka stuła używa "skojarzonego priorytetu numerycznego" modelu:

Bec Kolejki priorytetów ause powodują zaniżanie elementów w rosnącej kolejności priorytetu, mogą być używane do sortowania sekwencji wartości - zaczynają się od wstawienia każdego elementu do kolejki priorytetów z priorytetem równym jego pozycji w sekwencji, a następnie odjęcia wszystkich elementów z kolejki priorytetów . To wyciąga elementy w posortowanej kolejności.

Połączenie między kolejkami priorytetowymi i sortowaniem wiąże się jednak z kosztem. Znane są dolne granice algorytmów porównywania sortowania (żaden algorytm sortowania porównawczego nie może mieć środowiska wykonawczego lepszego niż O (n log n)). W związku z tym istnieje niższa granica w środowisku wykonawczym każdej kolejki priorytetowej opartej na porównaniu. Konkretnie, n kolejek i n dequeues musi mieć całkowity koszt nie lepszy niż O (n log n). W większości przypadków jest to w porządku, ale w niektórych przypadkach nie jest to wystarczająco szybkie.

Dopóki kolejka priorytetów może być używana do sortowania sekwencji wejściowych, środowisko wykonawcze z n kolejkowaniami i n usuń nigdy nie pokona O (n log n). Ale co, jeśli kolejka priorytetów nie sortuje danych wejściowych? Przenieś to do ekstremum - jeśli kolejka priorytetowa oddaje elementy w całkowicie arbitralnej kolejności, to możliwe jest zaimplementowanie n kolejki i n usuń w czasie O (n) - wystarczy użyć stosu lub kolejki, na przykład.

Intuicyjnie można myśleć o miękkiej kupie jako pomostu między dwoma skrajnościami "zawsze posortowane" i "bez gwarancji co do kolejności". Każda sterta sortowania jest parametryzowana przez pewną ilość & epsilon; nazywany "parametrem korupcji", który określa, jak blisko posortowane mogą być wartości wychodzące z miękkiego sterty. W szczególności jako & epsilon; zbliża się do 0, wyjście będzie stopniowo sortowane bardziej, a jako & epsilon; zbliża się do 1, wyjście będzie stopniowo coraz bardziej arbitralne. Odpowiednio, środowisko wykonawcze operacji miękkiego sterty jest określane jako funkcja O (log & epsil; ^-1), więc środowisko wykonawcze operacji staje się tańsze i tańsze, tak jak w przypadku & epsilon; idzie w górę (i, w związku z tym, wydajność jest mniej posortowana), a operacje stają się droższe, ponieważ & epsilon; idzie w dół (w takim przypadku wyjście staje się coraz bardziej posortowane).

Miękka sterta precyzyjnie określa, w jaki sposób nieposortowane dane wyjściowe będą wykorzystywać nową koncepcję "korupcji". W kolejce o normalnym priorytecie, po wstawieniu pary element/priorytet, priorytet elementu nigdy się nie zmienia. W miękkim sterty elementy związane z priorytetem mogą stać się uszkodzone, gdy element znajduje się wewnątrz miękkiego sterty. Gdy priorytet elementu jest uszkodzony, jego priorytet zwiększa się o pewną kwotę. (Ponieważ miękka sterta odrywa elementy w porządku rosnącym priorytetu, priorytet zwiększania elementu oznacza, że ​​wyjdzie on z kolejki później niż normalnie). Innymi słowy, korupcja spowoduje, że elementy nie pojawią się w uporządkowanej kolejności, ponieważ priorytety elementów, które są usuwane z listy, niekoniecznie muszą być takie same, jak w momencie ich kolejkowania.

Wybór & epsilon; dostrzega, jak wiele różnych elementów może mieć zepsute priorytety. Z & epsilon; małe, mniej elementów ma zepsute priorytety, a wraz z & epsilon; duże, więcej elementów zepsuje priorytety.

Teraz, na konkretne pytania - w jaki sposób priorytety elementów ulegają uszkodzeniu i jak to pomaga? Twoje pierwsze pytanie jest dobre - w jaki sposób struktura danych decyduje, kiedy skorumpować priorytety? Istnieją dwa sposoby na oglądanie tego. Po pierwsze, możesz myśleć o miękkiej kupie jako strukturze danych, gdzie z góry określasz, ile korupcji jest akceptowalna (to jest parametr & epsilon;), a struktura danych wewnętrznie decyduje, kiedy i jak korumpować priorytety, o ile tak nie jest ". t przekracza pewien poziom całkowitej korupcji. Jeśli wydaje się dziwne, że struktura danych podejmuje takie decyzje, zastanów się nad filtrem Bloom lub pominięciem, gdzie naprawdę istnieją wewnętrzne wybory losowe, które mogą wpłynąć na obserwowalne zachowanie struktury danych. Okazuje się, że miękki stert zazwyczaj nie jest zaimplementowany przy użyciu losowości (imponująca funkcja!), Ale nie jest to tutaj szczególnie istotne.

Wewnętrznie, obie znane implementacje miękkich stosach (jeden z oryginalnego papieru Chazelle, a później oczyszczanie przy użyciu drzewo binarne) wdrożyć korupcji przy użyciu techniki zwanej Carpooling gdzie elementy są grupowane i wszystkie mają wspólny priorytet. Korupcja występuje, ponieważ pierwotne priorytety wszystkich elementów w każdej grupie zostały zapomniane, a zamiast nich zastosowano nowy priorytet. Rzeczywiste szczegóły na temat grupowania elementów są przerażająco skomplikowane i nie warto ich analizować, więc najlepiej jest zostawić je jako "strukturę danych, która chce ją uszkodzić, o ile tylko nie uszkodzi więcej elementów niż podałeś przy wyborze & epsilon ;. "

Następnie, dlaczego jest przydatny? W praktyce tak nie jest. Miękka kupa jest prawie wyłącznie teoretycznym zainteresowaniem. W teorii teoretycznie brzmi to, że czas wykonania n wstawień i n usunięć z miękkiego sterty może być O (n) - szybszy niż O (n log n) - if & epsilon; jest wybrany poprawnie. Początkowo stosowano miękkie hałdy jako blok konstrukcyjny w szybkim algorytmie do budowania minimalnych drzew opinających. Są również wykorzystywane w nowym algorytmie do selekcji liniowej, pierwszego takiego deterministycznego algorytmu, który działa w czasie liniowym od słynnego algorytmu median-median.W obu tych przypadkach miękka sterta jest używana do "w przybliżeniu" sortowania elementów wejściowych w sposób, który pozwala algorytmom uzyskać przybliżone przybliżenie posortowanej sekwencji, w którym to momencie algorytm wykonuje dodatkową logikę, aby skorygować brak doskonałość. Niemal na pewno nigdy nie zobaczysz miękkiej kupy używanej w praktyce, ale jeśli w końcu znajdziesz przypadek, w którym to robisz, zostaw komentarz i daj znać!

Podsumowując:

• zgorszenie priorytety to sposób dokonywania kompromis między doskonałej sortowania (dokładna, ale powolny) i arbitralnej zamawiającego (niedokładne, ale bardzo szybko). Parametr & epsilon; określa, gdzie na spektrum znajduje się poziom korupcji.
• Korupcja działa poprzez zmianę priorytetów istniejących elementów w miękkim hałdzie, w szczególności poprzez podniesienie priorytetów niektórych elementów. Niska korupcja odpowiada w przybliżeniu posortowanym sekwencjom, a wysoka korupcja odpowiada bardziej arbitralnym sekwencjom.
• Sposób postępowania w przypadku uszkodzenia jest specyficzny dla danych i trudny do zrozumienia. Najlepiej myśleć o miękkich hałdach jako o korupcji, kiedy trzeba, ale nigdy w sposób przekraczający granicę nałożoną przez wybór & epsilon ;.
• Korupcja jest pomocna w ustawieniach teoretycznych, gdy sortowanie jest zbyt wolne, ale w przybliżeniu poprawnie posortowana sekwencja jest wystarczająco dobra do praktycznych zastosowań. Jest mało prawdopodobne, aby był przydatny w praktyce.

Mam nadzieję, że to pomoże!