Zainicjuj tablicę w zamortyzowanym stałym czasie

13

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

2

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,

3

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

— DeadMG,

3

@ 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)

2

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

1

... 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

1

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

1

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

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