albero di ricerca di risparmio dello Stato di esecuzione

Question

Ho un albero,

 A 
    /\ 
    B C 
    /\ \ 
D E F 

rappresentato come una lista,

(A (B (D) (E)) (C (F))) 

In realtà è un albero molto grande quindi quello che vorrei fare è avviare la ricerca se non riesco a trovare quello che sto cercando in dire 100 ms salva stato, ritorna, fai un po 'di manutenzione e poi richiama di nuovo la ricerca e continua da dove ho lasciato. Fondamentalmente la simulazione con cui sto lavorando mi sta dando una certa quantità di tempo non sufficiente per completare la ricerca. Sto cercando idee/tecniche su come ottenere questo? (in Clojure, Java)

Answer 1

Il threading è probabilmente la soluzione più semplice, ma non è molto difficile gestirlo da solo su un singolo thread. Gli ambienti di "simulazione" che ti danno solo 100ms spesso non consentono nuovi thread, quindi questa è un'alternativa.

L'idea di base è creare una chiusura che rappresenti il ​​lavoro da eseguire per completare l'attività e restituire tale risultato invece di un risultato se non si ha tempo per terminare. Ecco uno schizzo: aggiunge una sequenza di numeri e viene interrotto ogni dieci operazioni anziché ogni 100ms.

(let [timer (atom 9)] 
    (defn keep-going? [] 
    (not= 0 (swap! timer #(mod (inc %) 10))))) 

(defn saving-addition [sum xs] 
    (if-let [[x & more] (seq xs)] 
    (let [next-thunk (fn [] (saving-addition (+ x sum) more))] 
     (if (keep-going?) 
     (next-thunk) 
     next-thunk)) 
    sum)) 

(defn monitor [xs] 
    (loop [thunk (saving-addition 0 xs)] 
    (if (fn? thunk) 
     (do 
     (println "Saving execution state") 
     (recur (thunk))) 
     thunk))) 

user> (monitor (range 25)) 
Saving execution state 
Saving execution state 
Saving execution state 
300 

Edit: Perché Clojure non ha ottimizzazione coda-call, la creazione di un tonfo e quindi chiamando utilizza fino stack. Se, come è probabile, sei in grado di eseguire più di qualche migliaio di passaggi prima di dover essere interrotto, otterrai uno stack overflow. L'unica soluzione realistica è quella di duplicare il corpo del thunk sia in un recur e nella continuazione, come

(defn saving-addition [sum xs] 
    (if-let [[x & more] (seq xs)] 
    (let [sum (+ x sum)] 
     (if (keep-going?) 
     (recur sum more) 
     #(saving-addition sum more))) 
    sum)) 

si potrebbe probabilmente astratto questo fuori con una macro se si doveva scrivere più tali funzioni "sospendibili".

Answer 2

Se non ti interessa il sovraccarico di un thread, metti la ricerca su un thread che fa un po 'di lavoro e poi restituisce di volta in volta.

Il vantaggio dei thread è che non è necessario salvare lo stato a livello di codice; il sistema lo farà per te.

Devi pagare per questo in complessità, in quanto il risultato della ricerca verrà in modo asincrono e dovrai arrangiare per ottenerlo in qualche modo. Potrebbe anche essere necessario impostare timer da 100 ms. Un sacco di codice. :)

Answer 3

cosa migliore da fare è quello di rendere i punti dove si può facilmente salvare lo Stato e riprendere successivamente (si può provare a rendere la funzione ricorsiva per trovare i migliori punti facilmente)

poi in quei punti è possibile scegliere per salvare lo stato o continuare