Quand utiliser DAG (Directed Acyclic Graph) en programmation?

J'ai récemment trouvé un framework nommé ecto .

Dans ce cadre, un composant de base nommé "plasm" , qui est le graphe acyclique dirigé ecto.

Je me demande quel est l'avantage de ce mécanisme et dans quelles autres situations pouvons-nous exploiter le concept de DAG?

Bonne question.

• Le code peut être représenté par un DAG décrivant les entrées et les sorties de chacune des opérations arithmétiques effectuées dans le code; cette représentation permet au compilateur d'effectuer efficacement l'élimination des sous-expressions communes.
• La plupart des systèmes de gestion de contrôle de source implémentent les révisions en tant que DAG.
• Plusieurs langages de programmation décrivent des systèmes de valeurs liés entre eux par un graphe acyclique dirigé. Quand une valeur change, ses successeurs sont recalculés; chaque valeur est évaluée en fonction de ses prédécesseurs dans le DAG.
• Les DAG sont pratiques pour détecter les blocages car ils illustrent les dépendances entre un ensemble de processus et de ressources.
• Dans de nombreux algorithmes aléatoires en géométrie de calcul, l'algorithme conserve un DAG d'historique représentant les caractéristiques d'une construction géométrique remplacées par des entités à échelle plus fine; Il est possible de répondre aux questions d'emplacement de point, comme pour les deux structures de données ci-dessus, en suivant les chemins dans ce DAG.
• Une fois que nous avons le DAG en mémoire, nous pouvons écrire des algorithmes pour calculer le temps d'exécution maximum de l'ensemble.
• Lors de la programmation de systèmes de tableurs, le graphe de dépendance qui connecte une cellule à une autre si la première cellule stocke une formule utilisant la valeur de la seconde cellule doit être un graphe acyclique dirigé. Les cycles de dépendances sont interdits car ils empêchent les cellules impliquées dans le cycle d'avoir une valeur bien définie. De plus, exiger que les dépendances soient acycliques permet d'utiliser un ordre topologique pour planifier les recalculs des valeurs de cellules lorsque la feuille de calcul est modifiée.
• En utilisant DAG, nous pouvons écrire des algorithmes pour évaluer les calculs dans le bon ordre.

MODIFIER :

• L'ordre de calcul des cellules de formule lors du recalcul des valeurs de formule dans des feuilles de calcul peut être effectué à l'aide de DAG
• Git utilise des DAG pour le stockage de contenu, des pointeurs de référence pour les têtes, la représentation de modèles d'objet et le protocole distant.
• Les DAG sont utilisés dans l'ordonnancement de Trace: première approche pratique de l'ordonnancement global, l'ordonnancement de trace tente d'optimiser le chemin du flux de contrôle exécuté le plus souvent.
• Ecto est un framework de traitement qui utilise DAG pour modéliser les graphes de traitement de manière à ce qu'ils exécutent une exécution synchrone ordonnée. Le plasmide à Ecto est le DAG et le planificateur fonctionne dessus.
• Les DAG sont utilisés dans les logiciels en pipeline, technique utilisée pour optimiser les boucles, de manière parallèle au pipeline en matériel.

Bonnes ressources:

• 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

La réponse est que cela n’a pas grand-chose à voir avec la programmation. Cela concerne la résolution de problèmes.

Tout comme les listes chaînées sont des structures de données utilisées pour certaines classes de problèmes, les graphiques sont utiles pour représenter certaines relations. Les listes chaînées, les arbres, les graphiques et autres structures abstraites ne sont connectés à la programmation que dans le sens où vous pouvez les implémenter dans le code. Ils existent à un niveau d'abstraction supérieur. Il ne s’agit pas de programmation, mais d’application de structures de données à la résolution de problèmes.

Si vous voulez encore une relation avec la programmation, veuillez considérer les points suivants:

• DAG (connu sous le nom Wait-For-Graphs - plus de détails techniques ) sont pratiques pour détecter les blocages car ils illustrent les dépendances entre un ensemble de processus et de ressources (les deux sont des nœuds dans le DAG). Le blocage se produirait lorsqu'un cycle est détecté.
• Une fois que vous avez le DAG en mémoire, vous pouvez écrire des algorithmes pour:
  • assurez-vous que les calculs sont évalués dans le bon ordre ( tri topologique )
  • si les calculs peuvent être effectués en parallèle mais que chaque calcul a un temps d'exécution maximum, vous pouvez calculer le temps d'exécution maximum de l'ensemble

D'autres personnes ont appliqué DAG aux données, mais je pense que c'est au moins aussi applicable (sinon plus) au code. Mahbubur R Aaman mentionne cela, donc c'est vraiment plus un additif à sa réponse qu'une réponse complète en elle-même.

Il me semble que tout programme informatique impératif est dépourvu de boucles infinies (grâce à @AndresF.) Est un graphe acyclique dirigé (DAG). Ce qui signifie que les chemins possibles d'exécution du code sont dirigés (d'abord ceci, ensuite cela) et acycliques (ne formant pas de boucles infinies). Il s’agit d’un graphe car le chemin d’un code significatif est rarement aussi simple qu’une liste ou un arbre.

J'ai travaillé chez XSLT pendant peut-être 4 ans. J'ai eu beaucoup de difficulté à expliquer pourquoi ce n'était pas un bon langage de programmation à usage général, mais DAG en est la raison. Plus précisément, XSLT est un langage piloté par les données. Vous définissez des fonctions (oui, au sens de la programmation fonctionnelle) mais vous n'appelez pas nécessairement ces fonctions à partir de votre code. XSLT définit plutôt une combinaison de sélection et d'itération des nœuds d'un document XML d'entrée. Cela permet à la structure des données d'entrée de déterminer quelles fonctions sont appelées et dans quel ordre.

C'était très intéressant et très cool jusqu'à ce que votre programme rencontre une condition de données que vous n'avez pas testée à 02h30 et que vous deviez vous réveiller pour la réparer. Lorsque vous laissez les données définir le DAG, la définition du DAG devient alors toutes les conditions d'entrée possibles, qui sont inestimables pour toute application métier non triviale. ils sont inimaginables.

Au début, je pensais que la programmation fonctionnelle n'était peut-être pas un DAG car l'ordre d'exécution n'est parfois pas clair ni même pensé par le programmeur. Mais un programme fonctionnel définit des dépendances. En fait, le caractère déclaratif de la programmation fonctionnelle pourrait être considéré comme ne définissant que les dépendances (a ^ 2 = b ^ 2 + c ^ 2) sans spécifier l'ordre d'exécution (peu importe que «b» ou «c» soit carré au début , tant qu’ils sont tous les deux carrés avant d’être additionnés).

Mais si la programmation fonctionnelle peut être délibérément vague en ce qui concerne l’ordre des opérations à un niveau détaillé, elle est extrêmement claire en ce qui concerne les dépendances. Ce sont les caractéristiques mêmes qui le rendent si sujet à la concurrence. Dans tous les cas, il y a toujours un graphe de chemins dans le code, et ce graphe est toujours dirigé (les dépendances doivent être évaluées avant les tâches dépendantes), donc je pense que DAG s'applique également dans ce cas.

Belle question - merci de poster!

Actuellement, DAG est sous-estimé dans la programmation. Historiquement, beaucoup de choses liées au développement ont été faites avec des arbres et des hiérarchies, car déplacer quelque chose dans une boîte est pratique pour que notre cerveau facilite la gestion de choses complexes. Mais si vous regardez les événements et la manière dont ils dépendent d'autres événements et états, vous obtiendrez le DAG, car tout dans notre vie et dans le programme peut dépendre de tout ce qui se trouve dans le passé mais pas dans le futur, de sorte que vous deviendrez parfaitement "acyclique". relations applicables au concept de DAG. Bien que cela soit rarement utilisé explicitement dans le développement, le garder à l’esprit aiderait à mieux comprendre les choses.

Je me demande quel est l'avantage de Plasm chez Ecto ...

DAG peut être utilisé pour modéliser une collection de tâches dans une séquence avec la contrainte que certaines tâches doivent être effectuées avant les autres. Ecto est un framework de traitement qui utilise DAG pour modéliser les graphes de traitement de manière à ce qu'ils exécutent une exécution synchrone ordonnée. Le plasmide à Ecto est le DAG et le planificateur fonctionne dessus.

Dans quelles autres situations pouvons-nous exploiter le concept de DAG?

• DAWG est une structure de données qui représente un ensemble de chaînes et permet une opération de requête qui teste si une chaîne donnée appartient à l'ensemble dans le temps proportionnellement à sa longueur.
• Git utilise des DAG pour le stockage de contenu, des pointeurs de référence pour les têtes, la représentation de modèles d'objet et un protocole distant.

En tant qu'exemple concret, notre logiciel est similaire à un IDE dans lequel l'utilisateur final peut définir une série d'opérations à effectuer sur une image (inspection par vision industrielle). Ces inspections peuvent être liées à d’autres inspections ou peuvent en dépendre. Etant donné que tout cela est configurable par l'utilisateur final, nous ne pouvons pas optimiser le traitement en parallèle au moment de la conception. En représentant ces inspections et dépendances en tant que DAG, nous pouvons optimiser le parallélisme de l'inspection globale pour obtenir des performances maximales au moment de l'exécution.

Juste pour un autre exemple, les règles de gestion de la mémoire dans les applications Cocoa sont définies de manière à ce que toutes les références fortes forment un graphe acyclique dirigé, ce qui permet de garantir l’absence de fuites.

Ajouter une autre réponse car vous n'avez pas vu de référence pour construire des systèmes tels makeque ceux qui utilisent DAG pour rechercher les dépendances pour la construction.

Plus de détails ici