Come gestisco i valori dipendenti senza eseguire lo stesso calcolo due volte?

4

Sto lavorando su un'applicazione che è essenzialmente una calcolatrice, non il calcolatore palmare ma più un foglio di calcolo. Ci vorranno molti input attraverso diversi punti di vista e mostreremo le uscite dappertutto.

L'applicazione eseguirà molti calcoli. Questi calcoli dipendono principalmente dagli input dati dall'utente, ma possono anche dipendere dai risultati di altri calcoli.

Un altro requisito è che i calcoli offerti all'utente possono essere modificati in uno stile CMS. Ciò significa che all'avvio dell'applicazione caricheranno i calcoli e i relativi input necessari da un file chiamato contenuto dei calcoli.

Gli output dovrebbero essere sempre aggiornati, nel senso che se un utente aggiorna un valore, i calcoli che dipendono da questo input dovrebbero essere eseguiti di nuovo, inviando l'output ai suoi calcoli dipendenti e così via.

Finora, ho concepito un grafico diretto di calcoli in cui la relazione genitore-figlio rappresenta l'input e i suoi calcoli dipendenti. In questo modo, il processo che esegue un calcolo sarà in grado di verificare se ha dipendenti e di eseguirli.

Il problema con questo modello è che può portare a calcoli duplicati. Se un ingresso A ha due dipendenti B e C e un calcolo D dipende sia da B che da C, allora quando A viene aggiornato, D e i suoi dipendenti gireranno due volte.

Potrebbe valere la pena sapere che l'applicazione è costruita con un'architettura Redux su Javascript.

    
posta FaureHu 11.01.2017 - 20:35
fonte

3 risposte

6

Robert Harvey ha ragione, il tuo problema può essere risolto in modo elegante tramite la memoizzazione. Tuttavia, dal momento che il documento dell'articolo che ha citato sembra non essere più disponibile, cerco di darvi una breve spiegazione su come dovrebbe funzionare.

Diciamo che A è una variabile di input e calcoli B, C e D con valori memoizzati mB, mC e mD. Questi valori possono contenere il risultato del calcolo di B / C / D, oppure possono essere "non validi", il che significa che se viene richiesto il risultato di B, il calcolo corrispondente viene eseguito una volta, non di più, e il risultato viene memorizzato in mB . Quindi, quando viene richiesto di nuovo il risultato di B, mB verrà restituito direttamente senza un secondo calcolo.

Ogni volta che una cella come A viene aggiornata, il tuo programma deve fare una ricerca di grafico standard attraverso il grafico delle dipendenze a partire da A e contrassegnare tutti i nodi che possono raggiungere da lì come non validi (nel caso tu abbia descritto che raggiungerà B , C e D). E questo è tutto: non è necessario fare alcun calcolo in anticipo per B, C o D se il loro valore non è richiesto. E se questi valori sono richiesti, il meccanismo di memoizzazione descritto sopra impedirà qualsiasi calcolo duplicato, indipendentemente dall'ordine in cui i valori sono necessari.

    
risposta data 11.01.2017 - 22:39
fonte
2

Penso che tu sia sulla strada giusta con l'albero dei calcoli. Forse potresti anche memorizzare nella cache i valori calcolati nell'albero (o altrove, non ha molta importanza). Quindi, quando provi a eseguire un calcolo, controlli se ha un valore memorizzato nella cache, in tal caso: usalo, altrimenti: esegui il calcolo.

Quando l'utente modifica un valore, attiva un ricalcolo dell'albero, con i nuovi valori. Anche il controllo degli hit della cache (cioè lo stesso calcolo e gli stessi valori) durante il calcolo può aiutare a velocizzare le cose.

    
risposta data 12.01.2017 - 05:28
fonte
1

Questo dovrebbe essere davvero un commento sotto la risposta di Doc Brown, ma non ho ancora abbastanza reputazione per scrivere commenti.

C'è una libreria aggiuntiva per Redux chiamata Riseleziona che è progettata per affrontare proprio questo tipo di problema. Fornisce metodi di supporto per la creazione di un albero di funzioni memoizzate, che gli autori chiamano selettori .

La parte chiave è: non inserisci i valori calcolati nello stato Redux, solo gli input. Ogni volta che il tuo livello di vista deve utilizzare un valore derivato foo , chiama fooSelector(state) .

Poiché lo stato è immutabile in Redux, i selettori possono facilmente capire se i loro input sono stati modificati semplicemente controllando l'uguaglianza di riferimento con il set precedente di input. Alcuni di questi input possono essere il risultato di altri selettori.

Non è quindi necessario "contrassegnare i dati come non validi". Basta chiamare il selettore ogni volta che è necessario il suo risultato, e automaticamente farà la quantità minima di ricalcolo necessaria per restituire la risposta corretta.

In questo modo, la visualizzazione è garantita per rimanere in sincronia con i dati di input e non devi neanche pensare alle circostanze che causeranno la modifica dei risultati.

Per ulteriori dettagli, vedere la mia risposta a una domanda simile: Modello funzionale vs modello dati e React / Redux.

    
risposta data 25.02.2017 - 19:42
fonte

Leggi altre domande sui tag