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?
algorithms
data-structures
frameworks
graph
Po-Jen Lai
źródło
źródło
Odpowiedzi:
Fajne pytanie.
EDYTOWAĆ :
Dobre zasoby:
źródło
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:
źródło
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!
źródło
while (true) { print("hi"); }
? Może chcesz wykluczyć programy nie kończące się?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ę
źródło
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.
źródło
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.
źródło
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.
źródło
Dodając kolejną odpowiedź, ponieważ nie widziałem odwołania do budowania systemów, takich jak
make
który używa DAG do znajdowania zależności do budowania.Więcej informacji tutaj
źródło
make