Czy istnieje paradygmat komponowania funkcji „aktualizacji przyrostowej” w czystym stylu przepływu danych?

Nie znam poprawnej terminologii do zadawania tego pytania, dlatego opiszę to wieloma słowami, proszę o wyrozumiałość.

Tło , więc jesteśmy na tej samej stronie: programy często zawierają pamięci podręczne - kompromis czas / pamięć. Częstym błędem programisty jest zapomnienie o aktualizacji pamięci podręcznej po zmianie jednego z jej źródeł / precedensów. Ale paradygmat programowania przepływu danych lub FRP jest odporny na takie błędy. Jeśli mamy wiele czystych funkcji i połączymy je razem na ukierunkowanym wykresie zależności, wówczas węzły mogą mieć buforowaną wartość wyjściową i ponownie wykorzystywaną, dopóki dowolne dane wejściowe funkcji się nie zmienią. Tę architekturę systemu opisano w artykule Caching In Data-Environments-Based Environments, aw imperatywnym języku jest mniej więcej analogiczna do zapamiętywania.

Problem : Gdy jedno z danych wejściowych funkcji się zmienia, nadal musimy wykonać funkcję jako całość, wyrzucając jej buforowane dane wyjściowe i ponownie obliczając od zera. W wielu przypadkach wydaje mi się to marnotrawstwem. Rozważ prosty przykład, który generuje listę „5 najlepszych czegokolwiek”. Dane wejściowe to nieposortowana lista czegokolwiek. Jest przekazywany jako dane wejściowe do funkcji, która wyświetla posortowaną listę. Które z kolei jest wprowadzane do funkcji, która bierze tylko pierwsze 5 pozycji. W pseudokodzie:

input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)

Złożoność funkcji sortowania wynosi O (N log N). Ale weź pod uwagę, że ten przepływ jest używany w aplikacji, w której dane wejściowe zmieniają się tylko nieznacznie, dodając 1 element. Zamiast za każdym razem od nowa sortować od zera, szybsze, w rzeczywistości O (N), byłoby użycie funkcji, która aktualizuje starą sortowaną listę w pamięci podręcznej poprzez wstawienie nowego elementu we właściwej pozycji. To tylko jeden przykład - wiele funkcji „od zera” ma takie odpowiedniki z „przyrostową aktualizacją”. Być może nowo dodany element nie pojawi się nawet w końcowym wyjściu, ponieważ znajduje się on na 5. pozycji.

Moja intuicja sugeruje, że można by w jakiś sposób dodać takie funkcje „aktualizacji przyrostowej” do systemu przepływu danych, obok istniejących funkcji „od zera”. Oczywiście ponowne obliczanie wszystkiego od zera musi zawsze dawać taki sam wynik, jak wykonywanie szeregu aktualizacji przyrostowych. System powinien mieć właściwość, że jeśli każda z pojedynczych prymitywnych par FromScratch-Incremental zawsze daje ten sam wynik, wówczas zbudowane z nich większe funkcje kompozytowe powinny automatycznie dawać ten sam wynik.

Pytanie : Czy można mieć system / architekturę / paradygmat / meta-algorytm, który może obsługiwać zarówno funkcje FromScratch, jak i ich odpowiedniki przyrostowe, współpracując w celu zwiększenia wydajności i składając się w duże przepływy? Jeśli nie to dlaczego? Jeśli ktoś już zbadał ten paradygmat i opublikował go, jak się nazywa i czy mogę uzyskać krótkie podsumowanie jego działania?

To pole zostało wynalezione wiele razy i pod wieloma nazwami, takie jak:

• Algorytmy online .
• Algorytmy strumieniowe, zapytania strumieniowe, zapytania ciągłe.
• Dynamiczne struktury danych.
• Obliczenia samodopasowujące się (według Andreja).

(I możliwe, że więcej.) Nie są takie same, ale powiązane.

Paraphrasing Cai i wsp. (1): Istnieją dwa podstawowe sposoby ogólnej implementacji algorytmów online (tj. Bez odniesienia do konkretnego problemu algorytmicznego):

• Inkrementalizacja statyczna. Podejścia statyczne analizują program w czasie kompilacji i tworzą wersję przyrostową, która skutecznie aktualizuje dane wyjściowe oryginalnego programu zgodnie ze zmieniającymi się danymi wejściowymi. Podejścia statyczne mogą być bardziej wydajne niż podejścia dynamiczne, ponieważ nie jest wymagana księgowość w czasie wykonywania. Obliczone wersje przyrostowe można często optymalizować przy użyciu standardowych technik kompilatora, takich jak ciągłe składanie lub wstawianie. Jest to podejście badane w (1).

• Dynamiczna inkrementalizacja. Podejścia dynamiczne tworzą dynamiczne wykresy zależności podczas działania programu i propagują zmiany wzdłuż tych wykresów. Najbardziej znanym podejściem jest samodopasowujące się obliczenie Acar. Kluczowa idea jest prosta: programy wykonują się na oryginalnych danych wejściowych w rozszerzonym środowisku wykonawczym, które śledzi zależności między wartościami na dynamicznym wykresie zależności; wyniki pośrednie są buforowane. (Jak można sobie wyobrazić, zwykle zajmuje to dużo pamięci, a wiele badań w tej dziedzinie dotyczy ograniczenia wykorzystania pamięci.) Później zmiany w danych wejściowych rozprzestrzeniają się za pomocą wykresów zależności od zmienionych danych wejściowych do wyników, aktualizując zarówno dane pośrednie, jak i ostateczne rezultaty; przetwarzanie to jest często bardziej wydajne niż ponowne obliczanie. Jednak tworzenie dynamicznych wykresów zależności narzuca duże obciążenie stałe w czasie wykonywania, od 2 do 30 w raportowanych eksperymentach.

Ponadto zawsze można spróbować „ręcznie” opracować wersję online danego algorytmu. To może być trudne.

^{(1) Y. Cai, PG Giarrusso, T. Rendel, K. Ostermann, Teoria zmian dla języków wyższego rzędu: inkrementalizacja λ-Calculi przez różnicowanie statyczne .}

Prawdopodobnie szukasz programowania adaptacyjnego . Zobacz także pracę doktorską Umut Acar . Nie jestem na bieżąco z tym obszarem pracy, ale powinienem zacząć, możesz gonić referencje.