Quando utilizzare DAG (Directed Acyclic Graph) nella programmazione?

Bella domanda.

• Il codice può essere rappresentato da un DAG che descrive il input e output di ciascuna delle operazioni aritmetiche eseguite all'interno del codice; questa rappresentazione consente al compilatore di eseguire eliminazione della sottoespressione comune in modo efficiente.
• La maggior parte dei sistemi di gestione del controllo sorgente implementano le revisioni come DAG.
• Diversi linguaggi di programmazione descrivono sistemi di valori che sono collegati tra loro da un grafico aciclico diretto. Quando un valore cambiamenti, i suoi successori vengono ricalcolati; ogni valore è valutato come una funzione dei suoi predecessori nel DAG.
• I DAG sono utili nel rilevare i deadlock mentre illustrano il dipendenze tra un insieme di processi e risorse.
• In molti algoritmi randomizzati in geometria computazionale, il l'algoritmo mantiene un DAG storico che rappresenta le caratteristiche di alcuni costruzione geometrica che è stata sostituita da una scala più fine Caratteristiche; le domande sulla posizione del punto possono essere risolte, come per quanto sopra due strutture dati, seguendo i percorsi in questo DAG.
• Una volta che abbiamo il DAG in memoria, possiamo scrivere algoritmi su calcola il tempo massimo di esecuzione dell'intero set.
• Mentre si programmano i sistemi di fogli elettronici, il grafico delle dipendenze collega una cella a un'altra se la prima cella memorizza una formula utilizza il valore nella seconda cella deve essere un grafico aciclico diretto. I cicli di dipendenze non sono consentiti perché causano le celle coinvolto nel ciclo per non avere un valore ben definito. Inoltre, richiedere che le dipendenze siano aciclici consente un ordine topologico da utilizzare per pianificare il ricalcolo dei valori delle celle quando foglio di lavoro è cambiato.
• Usando DAG possiamo scrivere algoritmi per valutare i calcoli in l'ordine corretto.

EDIT:

• Ordine di valutazione delle celle formula quando si ricalcola i valori della formula nei fogli di calcolo può essere fatto utilizzando i DAG
• Git utilizza i DAG per l'archiviazione dei contenuti, i puntatori di riferimento per le teste, rappresentazione del modello a oggetti e protocollo remoto.
• I DAG vengono utilizzati durante la pianificazione di Trace: il primo approccio pratico per pianificazione globale, la pianificazione delle tracce tenta di ottimizzare il controllo percorso di flusso che viene eseguito più spesso.
• Ecto è un framework di elaborazione e utilizza DAG per modellare l'elaborazione grafici in modo che i grafici eseguano l'esecuzione sincrona. Plasma in Ecto è il DAG e Scheduler opera su di esso.
• I DAG vengono utilizzati nel pipelining del software, che è una tecnica utilizzata per ottimizzare i loop, in un modo che è parallelo al pipelining hardware.

Risorse buone:

• link
• link
• link
• link

La risposta è che non ha molto a che fare con la programmazione. Ha a che fare con la risoluzione dei problemi.

Proprio come le liste collegate sono strutture di dati usate per determinate classi di problemi, i grafici sono utili per rappresentare determinate relazioni. Gli elenchi collegati, gli alberi, i grafici e altre strutture astratte hanno solo una connessione alla programmazione in quanto è possibile implementarli in codice. Esistono ad un livello più alto di astrazione. Non si tratta di programmazione, si tratta di applicare strutture dati nella soluzione dei problemi.

Se vuoi ancora un po 'di relazione con la programmazione, considera i seguenti punti:

• DAG (noto come Wait-For-Graphs - altro dettagli tecnici ) sono utili nel rilevamento di deadlock in quanto illustrano le dipendenze tra un insieme di processi e risorse (entrambi sono nodi nel DAG ). Deadlock avverrebbe quando viene rilevato un ciclo.
• Una volta che hai il DAG in memoria, puoi scrivere algoritmi per:
  • assicurati che i calcoli siano valutati nell'ordine corretto ( ordinamento topologico )
  • se i calcoli possono essere eseguiti in parallelo ma ogni calcolo ha un tempo di esecuzione massimo, puoi calcolare il tempo massimo di esecuzione dell'intero set

Altre persone hanno applicato DAG ai dati, ma penso che sia almeno altrettanto applicabile (se non di più) al codice. Mahbubur R Aaman menziona questo, quindi questo è più un addendum alla sua risposta che una risposta completa da sola.

Mi viene in mente che qualsiasi programma per computer imperativo che sia privo di loop infiniti (grazie a @AndresF.) è un Dyc (Directed Acyclic Graph). Significa che i possibili percorsi di esecuzione del codice sono diretti (prima questo, poi quello), e aciclici (non si formano loop infiniti). Sono un grafico perché il percorso attraverso qualsiasi codice significativo è raramente semplice come un elenco o un albero.

Ho lavorato in XSLT per forse 4 anni. Ho passato un brutto periodo cercando di spiegare perché non era un buon linguaggio di programmazione generico, ma il DAG è la ragione. In particolare, XSLT è un linguaggio basato sui dati. Definite le funzioni (sì, nel senso di programmazione funzionale) ma non chiamate necessariamente queste funzioni dal vostro codice. Piuttosto, XSLT imposta una combinazione di selezione e iterazione attraverso i nodi di un documento XML di input. Ciò consente alla struttura dei dati di input di determinare quali funzioni vengono chiamate e in quale ordine.

Questo è stato molto interessante e molto interessante finché il tuo programma non ha riscontrato una condizione di dati per cui non hai eseguito il test alle 2:30 del mattino e hai dovuto svegliarlo e sistemarlo. Quando si lascia che i dati definiscano il DAG, la definizione del DAG diventa tutte le possibili condizioni di input, che per qualsiasi applicazione aziendale non banale sono oltre incalcolabili; sono inimmaginabili.

All'inizio pensavo che la programmazione funzionale potesse non essere un DAG perché a volte l'ordine di esecuzione non è chiaro, o addirittura pensato dal programmatore. Ma un programma funzionale definisce le dipendenze. In effetti, la natura dichiarativa della programmazione funzionale potrebbe essere pensata come la definizione di sole dipendenze (a ^ 2 = b ^ 2 + c ^ 2) senza specificare l'ordine di esecuzione (non importa se 'b' o 'c' è al quadrato prima , purché siano entrambi squadrati prima di essere aggiunti insieme).

Ma mentre la programmazione funzionale può essere deliberatamente vaga sull'ordine delle operazioni a livello dettagliato, è squisitamente chiara sulle dipendenze. Queste sono le caratteristiche che lo rendono così suscettibile alla concorrenza. In ogni caso, c'è ancora un grafico di percorsi attraverso il codice, e quel grafico è ancora diretto (le dipendenze devono essere valutate prima delle attività dipendenti), quindi penso che anche DAG si applichi lì.

Bella domanda: grazie per aver pubblicato!

Attualmente DAG è sottovalutato nella programmazione. Storicamente molte cose legate allo sviluppo sono state fatte con alberi e gerarchie perché spostare qualcosa in una scatola è conveniente per il nostro cervello per rendere più facile la gestione di cose complesse. Ma se guardi gli eventi e come dipendono da altri eventi e stati, otterrai DAG perché qualsiasi cosa nella nostra vita e nel programma può dipendere da qualsiasi cosa nel passato, ma non in futuro, così otterrai perfettamente "aciclico" le relazioni devono essere applicabili al concetto di DAG. Anche se questo raramente è stato usato esplicitamente nello sviluppo, avendo questo in mente avrebbe aiutato a capire meglio le cose

I am wondering what's the advantage of Plasm in Ecto...

DAG può essere utilizzato per modellare una raccolta di attività in una sequenza con il vincolo che determinate attività devono essere eseguite prima delle altre. Ecto è un framework di elaborazione e utilizza DAG per modellare i grafici di elaborazione in modo che i grafici eseguano l'esecuzione sincrona ordinata. Plasma in Ecto è il DAG e Scheduler funziona su di esso.

in what other situations can we exploit the concept of DAG?

• DAWG è una struttura dati che rappresenta un insieme di stringhe e consente un'operazione di query che verifica se una determinata stringa appartiene al set in tempo proporzionale alla sua lunghezza.
• Git utilizza i DAG per l'archiviazione del contenuto, i puntatori di riferimento per le teste, la rappresentazione del modello a oggetti e protocollo remoto.

Come esempio reale, il nostro software è simile a un IDE in cui l'utente finale può definire una serie di operazioni da eseguire su un'immagine (ispezione della visione artificiale). Queste ispezioni possono avere dipendenze da altre ispezioni o possono dipendere da ispezioni. Poiché questo è tutto configurabile dall'utente finale, non possiamo effettuare ottimizzazioni per l'elaborazione parallela in fase di progettazione. Rappresentando queste ispezioni e dipendenze come DAG, possiamo ottimizzare il parallelismo dell'ispezione globale per ottenere le massime prestazioni in fase di esecuzione.

Solo per un altro esempio, le regole di gestione della memoria nelle app Cocoa sono fatte in modo che tutti i riferimenti forti formino un grafo aciclico diretto, fatto per garantire l'assenza di perdite.

Aggiungi un'altra risposta in quanto non hai visto un riferimento per creare sistemi come make che utilizza DAG per scoprire le dipendenze per la costruzione.

Maggiori dettagli qui