Conosco abbastanza bene dove usare Stacks, Queues e Trees nelle applicazioni software, ma non ho mai usato un Deque (Double Ended Queue) prima. Dove li incontrerei di solito in natura? Sarebbe negli stessi posti di una coda ma con gribbili extra?
Conosco abbastanza bene dove usare Stacks, Queues e Trees nelle applicazioni software, ma non ho mai usato un Deque (Double Ended Queue) prima. Dove li incontrerei di solito in natura? Sarebbe negli stessi posti di una coda ma con gribbili extra?
Un modo in cui viene utilizzato un deque è quello di "invecchiare". Viene in genere utilizzato come funzionalità di annullamento o cronologia. Una nuova azione è inserita nel deque. Gli oggetti più vecchi sono nella parte anteriore. Un limite alle dimensioni della deque forza la rimozione degli elementi nella parte anteriore ad un certo punto man mano che vengono inseriti nuovi elementi (invecchiando gli elementi più vecchi). Fornisce quindi un modo rapido per accedere a entrambe le estremità della struttura perché conosci immediatamente gli elementi più vecchi e più recenti per rimuovere la parte anteriore e commettere l'azione più vecchia in O (1) o annullare in O (1).
Ottima domanda. Non ricordo il corso di CS 102 che menziona una singola applicazione per la coda a doppio attacco.
Fino ad oggi, l'unica applicazione che conosco è lo scheduler di work-stealing menzionato nell'articolo Wikipedia .
Funziona essenzialmente come segue:
In un normale modello procedurale a thread singolo, ogni chiamata di funzione inserisce un record di attivazione su un cosiddetto stack di chiamate . Un record di attivazione contiene le variabili locali e i parametri di quella chiamata. Una volta completata la chiamata al metodo ("restituisce"), l'ultimo record di attivazione viene estratto dallo stack di chiamate.
Questo è particolarmente importante perché è così che viene implementata la ricorsione: la struttura della ricorsione è rappresentata nello stato corrente dello stack di chiamate.
Quando parallelizzi un algoritmo ricorsivo, possiamo sfruttare questa proprietà sostituendo lo stack di chiamate con una coda di chiamate. Ogni thread nel calcolo riceve la propria coda di chiamate e inserisce e spinge i record di attivazione come in un'esecuzione sequenziale.
Ma una volta che un thread ha terminato il suo lavoro (= la sua coda di chiamate è vuota), ruba funziona da un altro thread rimuovendo un record di attivazione dalla coda di chiamate di quel thread rimuovendo dal "sbagliato" fine.
Fondamentalmente, la coda di chiamate agisce come due stack di chiamate che ora servono due thread.
Leggi altre domande sui tag data-structures