Cosa motiva il modello RAM?
Sembra che la maggior parte dell'analisi algoritmica odierna venga eseguita in modelli con accesso casuale in tempo costante, come la parola modello RAM. Non so molto di fisica, ma da fonti popolari ho sentito dire che dovrebbe esserci un limite all'archiviazione delle informazioni per volume e alla velocità di trasferimento delle informazioni, quindi le RAM non sembrano essere fisicamente realizzabili. I computer moderni hanno tutti questi livelli di cache che direi li rendono non molto simili alla RAM. Allora perché gli algoritmi teorici dovrebbero essere impostati nella RAM?
Risposte
Consentitemi di dare un punto di vista diverso rispetto a vonbrand. Tutto ciò che hai detto è vero: il modello RAM non è realistico per una serie di ragioni, e mentre è possibile difenderne diversi aspetti, una tale difesa non arriva davvero al nocciolo della questione.
Il nocciolo della questione - e la risposta alla tua domanda - è che il modello RAM è la cosa migliore che abbiamo. Rispetto ad altri modelli accettati, modella in modo più accurato il calcolo della vita reale. In particolare, il motivo per cui abbiamo adottato il modello RAM è stato principalmente una risposta alle macchine di Turing, poiché abbiamo scoperto che l'uso di macchine di Turing porta a problemi artificialmente difficili da risolvere in termini di complessità temporale. Il modello RAM risolve chiaramente questo problema evidente, e quindi è stato accettato, anche se rimane tutt'altro che perfetto.
Un classico esempio che illustra il problema evidente delle macchine di Turing è il problema dell'uguaglianza delle stringhe: dato input
$$ w_1 \# w_2$$
dove $w_1, w_2$ sono sequenze binarie e $\#$ è un separatore, che determina se $w_1 = w_2$. Si può dimostrare che qualsiasi macchina di Turing per il problema dell'uguaglianza prende$O(n^2)$tempo. Questo è scomodo, perché le macchine di Turing sono ciò a cui tutti pensano come il modello universale di calcolo, eppure nessun ingegnere del software o ricercatore di algoritmi crede che l'uguaglianza delle stringhe$O(n^2)$tempo. Allora cosa succede? L'uguaglianza delle stringhe dovrebbe essere lineare, quindi inventiamo un nuovo modello dove si trova e la migliore soluzione disponibile in questo momento è la parola RAM machine.
Forse un giorno in futuro troveremo un modello migliore, uno che sia semplice, concettualmente chiaro e migliori la RAM nella sua capacità di modellare la complessità computazionale della vita reale. Per ora, possiamo solo accontentarci del meglio che abbiamo.
Come prima approssimazione approssimativa, puoi prendere il tempo per accedere a una parola in memoria come costante, indipendentemente dagli accessi precedenti. Cioè, il modello RAM.
Hai ragione, le macchine odierne non sono simili alla RAM, ripaga (anche profumatamente) organizzare l'accesso ai dati in modo che sia il più sequenziale possibile o spremere l'ultimo bit di informazioni da un (breve!) Segmento di memoria prima di manipolarlo il prossimo. Ma raramente hai il margine di manovra per farlo, i tuoi accessi alla memoria sono essenzialmente casuali e il modello non è così lontano dalla verità. Inoltre le macchine odierne hanno molte più di una CPU, il modello ne ha solo una. E poi c'è l'elaborazione vettoriale (facendo la stessa operazione su un vettore di dati, non uno per uno) come fanno le "istruzioni multimediali" (e ancor di più usando le schede grafiche per l'elaborazione).
Un po 'di discussione è data ad esempio dalla ricerca binaria di Khoung è un caso patologico per le cache . Come vedi, analizzare anche algoritmi semplici e ben compresi con modelli di tempo di accesso alla memoria più realistici è scoraggiante.
Il modello RAM è motivato dall'analisi asintotica di algoritmi progettati come calcoli in memoria a thread singolo.
Ottimizzare le prestazioni per set di istruzioni specifici, cache e quant'altro è una cosa. L'altra cosa è essere preparati per la crescita della dimensione del problema. Per stimare la scalabilità del tuo algoritmo in memoria, probabilmente devi ignorare i piccoli fattori e concentrarti su quelli grandi$\mathcal{O}$notazione. Grande$\mathcal{O}$ non ottimizzerà tutto per te, ma almeno potrebbe dirti che la tua soluzione si adatta bene (o che dovresti provare qualcosa di diverso).
La RAM presuppone un piccolo set di istruzioni fisso, in cui opera ogni operazione $\mathcal{O}(1)$. Nota che questo è un buon modello se ci interessa solo la crescita asintotica:
Il set di istruzioni di una moderna CPU non è piccolo, ma possiamo fingere che lo sia effettivamente. Questi codici operativi aggiuntivi non fanno differenza nel grande$\mathcal{O}$ notazione.
Le CPU possono avere istruzioni il cui tempo di esecuzione dipende dall'ingresso. Ancora una volta, possiamo ignorarli, perché possiamo modellarli usando istruzioni più semplici senza influire su big$\mathcal{O}$complessità. Lo stesso vale per i livelli di cache: le loro prestazioni sono ancora limitate da qualche piccola costante, quindi funzionano$\mathcal{O}(1)$ per definizione.
Sì, non puoi accedere alla memoria in tempo costante se continua a crescere. Fortunatamente, questo non è mai richiesto grazie al buon senso. Nessuno sta indicizzando l'intera Internet nella memoria non persistente di una macchina single-threaded solitaria.