Zainicjuj tablicę w zamortyzowanym stałym czasie - jak nazywa się ta sztuczka?

Istnieje taka struktura danych, która handluje wydajnością dostępu do tablicy w porównaniu z potrzebą iteracji po jej wyczyszczeniu. Utrzymujesz licznik generacji przy każdym wpisie, a także licznik generacji globalnej. Operacja „wyczyść” zwiększa licznik generacji. Przy każdym dostępie porównujesz liczniki generacji lokalnej i globalnej; jeśli się różnią, wartość jest traktowana jako „czysta”.

To pojawiło się ostatnio w odpowiedzi na Stack Overflow , ale nie pamiętam, czy ta sztuczka ma oficjalną nazwę. Czy to?

Jednym z przypadków użycia jest algorytm Dijkstry, jeśli tylko niewielki podzbiór węzłów musi być rozluźniony, i jeśli trzeba to powtarzać wielokrotnie.

algorithms terminology krlmlr
źródło

Ciekawa sztuczka, ale ma sporo narzutów. Zastanawiam się więc, które zastosowania mają wyczyszczenie tablicy jako tak częstą operację, za którą płaci cena? (Szczere pytanie!)

Joachim Sauer,

@JoachimSauer: Edytowano.

krlmlr

W ogólnym przypadku brzmi bardzo drogo, zarówno pod względem zużycia pamięci, jak i kosztów dostępu. Przypadek użycia tej techniki musi być bardzo konkretny.

Martin York,

@ Joachim: Służy do szybkiego czyszczenia buforów w przybliżeniu renderowania. Mają po prostu „czysty bit” na 64kb lub coś takiego.

DeadMG,

@ user946850 „zamortyzowany” oznacza, że możesz udowodnić, że kosztowna operacja zdarza się dość rzadko na ogólnym obrazie, że nie wnosi ona więcej niż np. O (1)

Odpowiedzi:

Wspomniane wyżej podejście wymaga, aby każda komórka mogła pomieścić liczbę wystarczająco dużą, aby pomieścić liczbę ponownych inicjalizacji macierzy, co stanowi znaczną karę przestrzenną. Jeśli miejsce jest w stanie pomieścić co najmniej jedną wartość, która nigdy nie zostanie zapisana w sposób zgodny z prawem, można uniknąć kary pieniężnej za inne kary (nietrwałe) kosztem dodania O(Wlg(N))kary czasowej, gdzie Wjest liczba różnych miejsc tablic zapisanych między operacje czyszczenia i Njest to rozmiar tablicy. Załóżmy na przykład, że będziemy przechowywać liczby całkowite od -2 147 483 647 do 2 147 483 647 (ale nigdy -2 147 483 648) i chcemy, aby puste elementy tablicy były odczytywane jako zero. Zacznij od wypełnienia tablicy -2 147 483 648 (wywołaj tę wartośćB). Czytając miejsce na tablicę dla aplikacji, zgłoś wartość równą Bzero. Przed napisaniem gniazdo tablicową I, należy sprawdzić, czy jest utrzymywane B, a jeśli tak, i Ijest większa niż jeden, należy przechowywać zero do gniazda I/4po wykonaniu podobny czek na tym miejscu (i, jeśli to odbyło B, I/16itp).

Aby wyczyścić tablicę, zacznij od wartości Irównej 0 lub 1, w zależności od podstawy tablicy (opisany algorytm będzie działał dla obu). Następnie powtórz następującą procedurę: Jeśli pozycja Ijest B, przyrost Ii, jeśli to daje wielokrotność czterech, podziel przez cztery (zakończ, jeśli dzielenie daje wartość 1); jeśli element Inie jest B, zapisz go Bi pomnóż Iprzez cztery (jeśli Izaczyna się od zera, pomnożenie przez cztery pozostawi go zero, ale ponieważ element 0 będzie pusty, Izostanie zwiększony).

Zauważ, że można zastąpić stałą „cztery” powyżej innymi liczbami, przy czym większe wartości zwykle wymagają mniejszego oznaczania pracy, ale mniejsze wartości zwykle wymagają mniejszego czyszczenia pracy; ponieważ gniazda tablicowe, które są oznaczone, muszą zostać wyczyszczone, wartość trzech lub czterech jest prawie na pewno optymalna; ponieważ wartość cztery jest z pewnością zbliżona do optymalnej, jest lepsza niż dwie lub osiem i jest wygodniejsza niż jakakolwiek inna liczba, wydaje się to najbardziej rozsądnym wyborem.

supercat
źródło

Wystarczy mieć licznik wersji, który jest w stanie pomieścić wystarczającą liczbę resetów sekwencyjnych, zanim wszystkie komórki zostaną zaktualizowane o nowe wartości. W praktyce bajt może być wystarczający lub nawet mniejszy w ciasnych pętlach.

9000

@ 9000: Kod, który opiera się na takim zachowaniu, może być delikatny, szczególnie biorąc pod uwagę, że jedynym powodem zastosowania takiego „pseudo-czystego” podejścia (w przeciwieństwie do zwykłego czyszczenia tablicy) byłby zestaw elementów, które potrzebowałyby do wyczyszczenia był zazwyczaj niewielki i zmienny - para warunków, które spiskują w celu zwiększenia prawdopodobieństwa, że przedmiot zostanie wykorzystany, „wyczyszczone”, a następnie pozostaną nietknięte przez dowolnie długi czas. Można rozważyć zeskanowanie tablicy i fizyczne wyczyszczenie wszystkich starych gniazd, gdy licznik zamierza się owinąć, ale ...

supercat

... jeśli wartość zawijania licznika jest stała, średnia ilość pracy dla każdej operacji czyszczenia tablicy wynosiłaby O (N), przy czym N jest rozmiarem tablicy. Nie znaczy to, że coś takiego może nie być przydatne w praktyce, ponieważ implementacja O (N) przyspieszona o współczynnik 65 536 nadal byłaby O (N), ale byłaby również 65 536 razy szybsza niż wersja niez ulepszona . Nawiasem mówiąc, przypadki, w których takie podejścia byłyby pomocne, mogą również skorzystać z zastosowania struktury danych o rzadkich tablicach, które mogłyby wykorzystać przestrzeń O (AlgN) do przechowywania tablicy o tablicy o rozmiarze N z niepustymi elementami.

supercat

Nazwałbym to „ponownym zainicjowaniem komórki leniwej macierzy”, ale wydaje się, że nie ma ona żadnej ustalonej nazwy (to znaczy, nazwa jest w powszechnym użyciu).

Algorytm jest sprytny, ale bardzo wyspecjalizowany i ma zastosowanie w bardzo wąskim obszarze.

Aleksander Adamowski
źródło

Uważam, że jest to szczególny przypadek zapamiętywania , z wyjątkiem tego przypadku, że „notatki” domyślnie „starzeją się” z każdym przyrostem licznika globalnego. Chyba coś w rodzaju „zapamiętywania wstecznego”.

defube
źródło