Kiedy stosować programowanie DAG (Directed Acyclic Graph)?

37

Niedawno znalazłem framework o nazwie ecto .

W tej strukturze podstawowy komponent o nazwie „plazm” , którym jest ekto-kierowany wykres acykliczny. W eecto plazmę można obsługiwać za pomocą harmonogramu ecto.

Zastanawiam się, jakie są zalety tego mechanizmu iw jakich innych sytuacjach możemy wykorzystać koncepcję DAG?

Po-Jen Lai
źródło
6
Większość systemów zarządzania kontrolą źródła wdraża zmiany jako DAG.
Oded
1
Planowanie to cała gałąź problemów, które często dotyczą DAG .
TC1
1
Wiele rzeczy, które są reprezentowane jako drzewa, powinny naprawdę być reprezentowane jako DAG, biorąc pod uwagę dziwne, ale wciąż dość powszechne przypadki krawędzi.
Joachim Sauer
@ JoachimSauer np. Systemy plików z twardymi dowiązaniami
jk.

Odpowiedzi:

29

Fajne pytanie.

  • Kod może być reprezentowany przez DAG opisującą dane wejściowe i wyjściowe każdej z operacji arytmetycznych wykonywanych w kodzie; ta reprezentacja pozwala kompilatorowi na wydajną eliminację typowych podwyrażeń.
  • Większość systemów zarządzania kontrolą źródła wdraża zmiany jako DAG.
  • Kilka języków programowania opisuje systemy wartości, które są ze sobą powiązane za pomocą ukierunkowanego wykresu acyklicznego. Kiedy jedna wartość się zmienia, jej następcy są ponownie obliczani; każda wartość jest oceniana jako funkcja swoich poprzedników w DAG.
  • DAG są przydatne w wykrywaniu zakleszczeń, ponieważ ilustrują zależności między zestawem procesów i zasobów.
  • W wielu randomizowanych algorytmach geometrii obliczeniowej algorytm zachowuje historię DAG reprezentującą cechy niektórych konstrukcji geometrycznych, które zostały zastąpione późniejszymi cechami o mniejszej skali; Na zapytania dotyczące lokalizacji punktów można odpowiedzieć, podobnie jak w przypadku powyższych dwóch struktur danych, postępując zgodnie ze ścieżkami w tym DAG.
  • Kiedy już mamy DAG w pamięci, możemy pisać algorytmy, aby obliczyć maksymalny czas wykonania całego zestawu.
  • Podczas programowania systemów arkuszy kalkulacyjnych wykres zależności, który łączy jedną komórkę z drugą, jeśli pierwsza komórka przechowuje formułę wykorzystującą wartość w drugiej komórce, musi być ukierunkowanym wykresem acyklicznym. Cykle zależności są niedozwolone, ponieważ powodują, że komórki biorące udział w cyklu nie mają dobrze określonej wartości. Ponadto wymaganie acykliczności zależności pozwala na zastosowanie kolejności topologicznej do planowania ponownych obliczeń wartości komórek po zmianie arkusza kalkulacyjnego.
  • Za pomocą DAG możemy pisać algorytmy do oceny obliczeń we właściwej kolejności.

EDYTOWAĆ :

  • Porządkowanie oceny komórek formuł przy ponownym obliczaniu wartości formuł w arkuszach kalkulacyjnych można wykonać za pomocą DAG
  • Git używa DAG do przechowywania treści, wskaźników odniesienia dla głowic, reprezentacji modelu obiektowego i protokołu zdalnego.
  • DAG stosuje się przy planowaniu śledzenia: pierwsze praktyczne podejście do planowania globalnego, szeregowanie śledzenia próbuje zoptymalizować najczęściej wykonywaną ścieżkę sterowania.
  • Ecto jest strukturą przetwarzania i korzysta z DAG do modelowania wykresów przetwarzania, aby grafy wykonywały synchroniczne wykonywanie. Plazmą w Ecto jest DAG i Scheduler na nim działa.
  • DAG są używane w programowym przetwarzaniu potokowym, które jest techniką stosowaną do optymalizacji pętli, w sposób równoległy do ​​potokowania sprzętowego.

Dobre zasoby:

Md Mahbubur Rahman
źródło
1
Brak pętli? Myślę, że dopóki pętla się kończy, powinna się kwalifikować. Zamiast być A -> B -> C, może pójść A -> B -> A1 -> B1 -> A2 -> B2 -> C. Cykliczny w pewnym sensie, ale nie w innym. Bardziej jak spirala niż koło.
GlenPeterson
@GlenPeterson, Tak, masz rację. Zredagowałem swoją odpowiedź. Dziękuję za komentarz. :)
Md Mahbubur Rahman
Nadal nie uważam, że „prosta linia” jest konieczna. „G” w DAG oznacza Graph. Sprawdź moją odpowiedź poniżej. Przepraszam, że nie przeczytałem wystarczająco uważnie przed udzieleniem odpowiedzi, ale dałem +1 twojej odpowiedzi za twoją kompletność i ponad wszystko poziom oświecenia.
GlenPeterson
@GlenPeterson, przepraszam za pomyłkę. Zaktualizowałem swoją odpowiedź. Podoba mi się również twoja odpowiedź. Tak więc +1 do twojej odpowiedzi.
Md Mahbubur Rahman
3
Dzięki za +1. Nadal uważam, że cały kod jest DAG, nie ogranicza się do wyrażeń arytmetycznych. We / wy, wyjątki, interakcje wieloprocesowe i przerwania sprzętowe są po prostu innymi węzłami początkowymi lub końcowymi w ukierunkowanym (ponieważ są początkiem lub końcem), acykliczny (bez nieskończonych pętli) Wykres (skończony zestaw uporządkowanych par węzłów) . Interesującą kontynuacją pytania Ricky może być: „Czy istnieje poprawny i działający kod, który nie jest DAG”. Myślę, że odpowiedź brzmi „nie”, ale byłbym zachwycony, gdyby ktoś udowodnił, że się mylę.
GlenPeterson
12

Odpowiedź jest taka, że ​​nie ma wiele wspólnego z programowaniem. Ma to związek z rozwiązywaniem problemów.

Podobnie jak listy połączone są strukturami danych wykorzystywanymi dla niektórych klas problemów, wykresy są przydatne do reprezentowania pewnych relacji. Połączone listy, drzewa, wykresy i inne abstrakcyjne struktury mają tylko połączenie z programowaniem, dzięki czemu można je zaimplementować w kodzie. Istnieją na wyższym poziomie abstrakcji. Nie chodzi o programowanie, ale o stosowanie struktur danych w rozwiązywaniu problemów.

Jeśli nadal chcesz mieć jakiś związek z programowaniem, rozważ następujące punkty:

  • DAG (znany jako Wait-For-Graphs - więcej szczegółów technicznych ) jest przydatny w wykrywaniu zakleszczeń, ponieważ ilustrują zależności między zestawem procesów i zasobów (oba są węzłami w DAG). Zakleszczenie wystąpiłoby po wykryciu cyklu.
  • Gdy masz już DAG w pamięci, możesz pisać algorytmy do:
    • upewnij się, że obliczenia są oceniane we właściwej kolejności ( sortowanie topologiczne )
    • jeśli obliczenia można wykonać równolegle, ale każde obliczenie ma maksymalny czas wykonania, można obliczyć maksymalny czas wykonania całego zestawu
Vaibhav Agarwal
źródło
1
Aby ponownie pokazać, że wykracza to poza zakres samego programowania, zastanów się, w jaki sposób tablice umieszczasz na tablicy w relacyjnej bazie danych, aby mentalnie analizować długość ścieżki od 1 tabeli do drugiej, jest to odpowiednik mentalnego użycia DAG do określenia wydajności twój model danych
Jimmy Hoffa
6

Inne osoby zastosowały DAG do danych, ale myślę, że jest to co najmniej tak samo odpowiednie (jeśli nie bardziej) kodowanie. Mahbubur R Aaman wspomina o tym, więc tak naprawdę jest to bardziej uzupełnienie jego odpowiedzi niż pełna odpowiedź sama w sobie.

Przychodzi mi do głowy, że jakikolwiek imperatywny program komputerowy wolny od nieskończonych pętli (dzięki @AndresF.) Jest Directed Acyclic Graph (DAG). Oznacza to, że możliwe ścieżki wykonania kodu są skierowane (najpierw to, potem to) i acykliczne (nie tworząc nieskończonych pętli). Są to wykresy, ponieważ ścieżka przez dowolny znaczący kod rzadko jest tak prosta jak lista lub drzewo.

Pracowałem w XSLT przez może 4 lata. Miałem okropny czas, próbując wyjaśnić, dlaczego nie był to dobry język programowania ogólnego przeznaczenia, ale powodem jest DAG. W szczególności XSLT jest językiem opartym na danych. Definiujesz funkcje (tak, w sensie programowania funkcjonalnego), ale niekoniecznie wywołujesz te funkcje ze swojego kodu. Zamiast tego XSLT ustawia kombinację wyboru i iteracji węzłów wejściowego dokumentu XML. Pozwala to strukturze danych wejściowych określić, które funkcje są wywoływane i w jakiej kolejności.

Było to bardzo interesujące i bardzo fajne, dopóki twój program nie napotkał warunku danych, którego nie testowałeś o 2:30 i musiałeś się obudzić i naprawić. Gdy pozwolisz, aby dane definiowały DAG, wówczas definicja DAG staje się wszystkimi możliwymi warunkami wejściowymi - które dla każdej nietrywialnej aplikacji biznesowej są nieobliczalne; są niewyobrażalne.

Na początku myślałem, że programowanie funkcjonalne może nie być DAG, ponieważ programista czasami nie jest jasny, a nawet nie myślał o nim. Ale program funkcjonalny określa zależności. W rzeczywistości deklaratywny charakter programowania funkcjonalnego można uznać za definiowanie tylko zależności (a ^ 2 = b ^ 2 + c ^ 2) bez określania kolejności wykonywania (nie ma znaczenia, czy „b” czy „c” jest najpierw podniesione do kwadratu , o ile oba są podniesione do kwadratu przed zsumowaniem).

Ale chociaż programowanie funkcjonalne może być celowo niejasne co do kolejności operacji na poziomie szczegółowym, jest wyjątkowo jasne na temat zależności. Są to cechy, które sprawiają, że jest tak podatny na współbieżność. W każdym razie nadal istnieje wykres ścieżek w kodzie, który jest nadal kierowany (zależności muszą być ocenione przed zadaniami zależnymi), więc myślę, że DAG również tam ma zastosowanie.

Ładne pytanie - dziękuję za wysłanie wiadomości!

GlenPeterson
źródło
1
Jest to imperatyw zaprogramować DAG Twoim zdaniem: while (true) { print("hi"); }? Może chcesz wykluczyć programy nie kończące się?
Andres F.
5

Obecnie DAG jest niedoceniany w programowaniu. Historycznie wiele rzeczy związanych z rozwojem powstało z drzew i hierarchii, ponieważ przenoszenie czegoś w pudełku jest wygodne dla naszego mózgu, aby ułatwić zarządzanie złożonymi rzeczami. Ale jeśli spojrzysz na wydarzenia i to, jak zależą one od innych wydarzeń i stanów, dostaniesz DAG, ponieważ wszystko w naszym życiu i programie może zależeć od wszystkiego w przeszłości, ale nie w przyszłości, dzięki czemu uzyskasz idealnie „acykliczny” relacje do zastosowania w koncepcji DAG. Chociaż rzadko jest to wyraźnie używane w pracach programistycznych, należy o tym pamiętać, aby lepiej zrozumieć sytuację

Maksee
źródło
2

Zastanawiam się, jaka jest zaleta Plazmy w Ecto ...

DAG może być używany do modelowania zbioru zadań w sekwencji z ograniczeniem, że niektóre zadania muszą być wykonane przed innymi. Ecto jest strukturą przetwarzania i korzysta z DAG do modelowania wykresów przetwarzania, aby grafy wykonywały synchroniczne wykonywanie. Plazma w Ecto jest DAG i Scheduler działa na niego.

w jakich innych sytuacjach możemy wykorzystać koncepcję DAG?

  • DAWG jest strukturą danych, która reprezentuje zestaw ciągów i pozwala na operację zapytania, która sprawdza, czy dany ciąg należy do zestawu w czasie proporcjonalnym do jego długości.
  • Git używa DAG do przechowywania treści, wskaźników odniesienia dla głowic, reprezentacji modelu obiektu i protokołu zdalnego.
theD
źródło
Chociaż minęło dużo czasu ... ale myślę, że ta odpowiedź naprawdę pomaga mi zrozumieć ducha eecto. Muszę to wskazać. Dzięki!
Po-Jen Lai,
0

Jako przykład ze świata rzeczywistego nasze oprogramowanie jest podobne do IDE, w którym użytkownik końcowy może zdefiniować serię operacji, które zostaną wykonane na obrazie (inspekcja obrazu maszynowego). Inspekcje te mogą zależeć od innych inspekcji lub mogą zależeć od nich inspekcje. Ponieważ wszystko to jest konfigurowane przez użytkownika końcowego, nie możemy dokonywać optymalizacji przetwarzania równoległego w czasie projektowania. Reprezentując te inspekcje i zależności jako DAG, możemy zoptymalizować równoległość ogólnej inspekcji w celu uzyskania maksymalnej wydajności w czasie wykonywania.

Dave Nay
źródło
-1

Dla jeszcze jednego przykładu reguły zarządzania pamięcią w aplikacjach Cocoa są tworzone tak, aby wszystkie silne referencje tworzyły ukierunkowany wykres acykliczny, który ma na celu zagwarantowanie braku wycieków.

millenomi
źródło
-2

Dodając kolejną odpowiedź, ponieważ nie widziałem odwołania do budowania systemów, takich jak makektóry używa DAG do znajdowania zależności do budowania.

Więcej informacji tutaj

dlmeetei
źródło
Czy powiedziałem coś złego, dlaczego został odrzucony
dlmeetei
Odrzuciłeś raczej stare pytanie z raczej słabą odpowiedzią. Jeśli masz ochotę napisać odpowiedź, która brzmi „dodając to, ponieważ nikt inny o tym nie wspominał ...” i masz tylko jedno zdanie, nie jest to dobra odpowiedź. Spróbuj w pełni odpowiedzieć na pytanie i wyjaśnić, w jaki sposób aplikacja korzysta z DAG, jak działa ten projekt i dlaczego został wybrany w porównaniu z innymi opcjami. Najlepiej, jeśli treść ma kilka akapitów.
Ok, pozwól mi rozwinąć to później
dlmeetei
Ok, zamiast powtarzać, właśnie zaktualizowałem link, który szczegółowo opisuje, w jaki sposób jest używany w narzędziach takich jakmake
dlmeetei
Linki mają nieprzyjemny zwyczaj stania się nieaktualne lub nieudane. Jeśli tak się stanie, wrócisz do miejsca, w którym zacząłeś - krótka jednowierszowa odpowiedź, która niewiele pomaga. Czy możesz streścić treść linku, aby ta odpowiedź mogła stać się samodzielna? (Zachowaj link, upewnij się, że odpowiedź jest dobra, nawet bez linku).
Dan Pichelman