Obliczenia przyrostowe

Obliczenia przyrostowe , znane również jako obliczenia przyrostowe , to funkcja oprogramowania , która za każdym razem, gdy zmienia się fragment danych , próbuje zaoszczędzić czas , przeliczając tylko te dane wyjściowe, które zależą od zmienionych danych. Gdy przetwarzanie przyrostowe zakończy się sukcesem, może być znacznie szybsze niż naiwne obliczanie nowych wyników. Na przykład arkusza kalkulacyjnego może wykorzystywać obliczenia przyrostowe w swojej funkcji ponownego obliczania, aby aktualizować tylko te komórki zawierające formuły, które zależą (bezpośrednio lub pośrednio) od zmienionych komórek.

Gdy przetwarzanie przyrostowe jest realizowane przez narzędzie, które może je automatycznie zaimplementować dla różnych fragmentów kodu, narzędzie to jest przykładem narzędzia do analizy programu w celu optymalizacji .

Obliczenia przyrostowe wyprowadzają nową parę wejścia/wyjścia z jednej lub kilku starych relacji wejścia/wyjścia. Aby to zrobić, ΔP musi powiązać zmianę na wejściu ze zmianą na wyjściu. Konsument wyniku może być zainteresowany pełnym zaktualizowanym wyjściem, wyjściem delta lub jednym i drugim.

Statyczny kontra dynamiczny

Techniki obliczeń przyrostowych można zasadniczo podzielić na dwa rodzaje podejść:

Podejścia statyczne próbują wyprowadzić program przyrostowy z konwencjonalnego programu P, stosując np. ręczne projektowanie i refaktoryzację lub automatyczne transformacje programu. Te przekształcenia programu mają miejsce przed wprowadzeniem jakichkolwiek danych wejściowych lub zmian wejściowych.

Podejścia dynamiczne rejestrują informację o wykonywaniu programu P na określonym wejściu (I1) i wykorzystują tę informację, gdy wejście zmienia się (na I2) w celu aktualizacji wyjścia (z O1 na O2). Rysunek przedstawia zależność między programem P, funkcją obliczania zmian ΔP, która stanowi rdzeń programu przyrostowego, a parą wejść i wyjść, I1, O1 i I2, O2.

Podejścia specjalistyczne i ogólne

Niektóre podejścia do obliczeń przyrostowych są wyspecjalizowane, podczas gdy inne są ogólnego przeznaczenia. Specjalistyczne podejścia wymagają od programisty wyraźnego określenia algorytmów i struktur danych, które zostaną użyte do zachowania niezmienionych podobliczeń. Z drugiej strony podejścia ogólnego przeznaczenia wykorzystują język, kompilator lub techniki algorytmiczne, aby nadać zachowanie przyrostowe programom, które w przeciwnym razie nie są przyrostowe.

Metody statyczne

Pochodne programu

Biorąc pod uwagę obliczenie i potencjalną zmianę ${\ Displaystyle x_ {j}: = \ Delta _ {x_ {j}}}$ ${\ Displaystyle C = f (x_ {1}, x_ {2}, \ kropki x_ {n})$ , możemy wstawić kod przed zmianą (pre-pochodna) i po zmianie (post-pochodna), aby zaktualizować wartość z do ${\ displaystyle C}$ szybciej niż ponowne uruchomienie $displaystyle f}$ . Paige spisała listę reguł formalnego różnicowania programów w SUBSETL.

Zobacz konserwację

W systemach baz danych, takich jak DBToaster, widoki są definiowane za pomocą algebry relacyjnej. Przyrostowa konserwacja widoku analizuje statycznie algebrę relacyjną w celu tworzenia reguł aktualizacji, które szybko utrzymują widok w przypadku niewielkich aktualizacji, takich jak wstawienie wiersza.

Metody dynamiczne

Obliczenia przyrostowe można uzyskać, budując wykres zależności wszystkich elementów danych, które mogą wymagać ponownego obliczenia, oraz ich zależności. Elementy, które wymagają aktualizacji, gdy zmienia się pojedynczy element, są określone przez przechodnie domknięcie relacji zależności grafu. Innymi słowy, jeśli istnieje ścieżka od zmienionego elementu do innego elementu, ten ostatni może zostać zaktualizowany (w zależności od tego, czy zmiana ostatecznie dotrze do elementu). Graf zależności może wymagać aktualizacji w miarę zmiany zależności lub dodawania lub usuwania elementów z systemu. Jest używany wewnętrznie przez implementację i zwykle nie musi być wyświetlany użytkownikowi.

Przechwytywania zależności we wszystkich możliwych wartościach można uniknąć, identyfikując podzbiór ważnych wartości (np. wyniki agregacji), w ramach których można śledzić zależności, oraz stopniowo przeliczając inne zmienne zależne, a tym samym równoważąc ilość informacji o zależnościach, które mają być śledzone, z ilością ponownego obliczenia do wykonania po zmianie wejścia.

Ocena częściowa może być postrzegana jako metoda automatyzacji najprostszego możliwego przypadku przetwarzania przyrostowego, w którym próbuje się podzielić dane programu na dwie kategorie: te, które mogą się zmieniać w zależności od danych wejściowych programu i te, które nie mogą (i najmniejsze jednostka zmiany to po prostu „wszystkie dane, które mogą się różnić”). Częściową ocenę można łączyć z innymi przyrostowymi technikami obliczeniowymi.

W przypadku cykli na wykresie zależności pojedyncze przejście przez wykres może nie wystarczyć do osiągnięcia stałego punktu. W niektórych przypadkach całkowita ponowna ocena systemu jest semantycznie równoważna ocenie przyrostowej i może być bardziej wydajna w praktyce, jeśli nie w teorii.

Istniejące systemy

Obsługa kompilatorów i języków

Automatyczna inkrementalizacja (zwana także „samodopasowującymi się obliczeniami” i „adaptacyjnym programowaniem funkcyjnym”), Delta ML , Haskell Adaptive
Generator syntezatora Cornell
IceDust - niestandardowy język specyficzny dla domeny.

Frameworki i biblioteki

Adapton - z implementacjami w kilku językach
Jednokierunkowe ograniczenia przepływu danych (obliczenia reaktywne w C++)
Różnicowy przepływ danych
Przyrostowy Jane Street
Rejestr danych przyrostowych ( LogicBlox )
Prolog przyrostowy (XSB)
Podejścia specyficzne dla domeny:
- przyrostowe sprawdzanie typu

Aplikacje

Bazy danych (obsługa przeglądania)
Buduj systemy
Arkusze kalkulacyjne
Środowiska programistyczne
Obliczenia finansowe
Ocena gramatyki atrybutów
Obliczenia i zapytania grafów
GUI (np. różnicowanie React i DOM)
Zastosowania naukowe

Zobacz też