Kiedy stosować programowanie DAG (Directed Acyclic Graph)?

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?

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:

• http://www.biomedcentral.com/1471-2288/8/70
• http://www.ncbi.nlm.nih.gov/pubmed/12453109
• http://www.ericsink.com/vcbe/html/directed_acyclic_graphs.html
• http://xlinux.nist.gov/dads/HTML/directAcycGraph.html

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

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!

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ę

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.

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.

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.

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