Associazione dati per valori booleani

Question

Associazione dati per valori booleani

#1 da (1 voti)

0

Ti stai chiedendo se c'è qualcosa di simile all'associazione dati ma per valori / trigger booleani. Sembra che potrebbe essere correlato a Diagrammi decisionali binari (BDD), ma sono precalcolati piuttosto che dinamici, credo.

Supponiamo di avere 100 o 1000 variabili booleane tutte correlate tra loro in un grafico. E uno di loro cambia. La cosa più semplice è quindi ricalcolare tutti i 1000 valori. Ma potrebbe essere più ottimale seguire invece la traccia dal nodo modificato alle cose che dipendono da esso. Ma di nuovo potrebbe portare a un lungo inseguimento in cui devi evitare di riaggiornare lo stesso booleano più di una volta, così potresti finire con più di 1000 operazioni.

Chiedersi se c'è qualcosa fatto su questo argomento. Come aggiornare in modo ottimale i valori booleani che dipendono l'uno dall'altro in un grafico complesso.

boolean graph data-binding

posta Lance Pollard 23.06.2018 - 02:49

fonte

1 risposta

Leggi altre domande sui tag boolean graph data-binding

È appropriato che un modello ottenga dati "in streaming" durante il rendering? Progettazione di un "servizio" Python usando multiprocessing e threading

score 1 · Accepted Answer

Ecco cosa sono in grado di capire dalla tua domanda:

Hai impostato un S di variabili booleane e un grafico delle dipendenze G . Se una delle variabili X in S cambia, vuoi ricalcolare solo altre variabili in S a seconda di X , e in un modo che non ricalcoli la stessa variabile due volte perché ciò che è dipeso è cambiato ancora una volta.

Soluzione : Puoi utilizzare DFS e Ordinamento topologico per gestirlo.

Supponiamo di avere le variabili A, B, C e D con bordi come

B -> A // i.e. A depends on B
D -> B // i.e. B depends on D

Se la direzione dei bordi è diversa, puoi sempre invertirli.

Quindi, se cambi D, vuoi aggiornare sia B che A ma non C.

È possibile eseguire un attraversamento DFS a partire da D e trovare tutti i nodi raggiungibili da D (ad esempio, tutto ciò che direttamente o indirettamente dipende da D). Lista ristretta di queste variabili, qualsiasi cosa oltre a queste non verrà aggiornata.

Ora ordina topologicamente tutto ciò che hai selezionato. In questo modo, tutto ciò che dipende da una variabile X verrà aggiornato prima di ricalcolare X .

In questo modo il tuo numero di calcoli non supererà mai il numero di variabili che hai