Il fattore di analisi della complessità del tempo per le prestazioni della cache di un algoritmo?

La complessità del tempo (notazione Big-O) non misura le prestazioni di un algoritmo. Invece, categorizza come la risorsa di un algoritmo utilizza ridimensiona con la dimensione dell'input. Questo ci consente di confrontare due algoritmi con un giudizio come "per alcuni input sufficientemente grandi, l'algoritmo A sarà sempre più veloce dell'algoritmo B". Possiamo fare questo giudizio senza nemmeno considerare implementazioni concrete degli algoritmi. In quanto tale, Big-O non si preoccupa dei dettagli di implementazione come la memorizzazione nella cache.

Tuttavia, assumiamo determinati dettagli di implementazione nel calcolo di Big-O. Per esempio. è normale presumere che ogni accesso alla memoria abbia un costo costante. Questo chiaramente non regge in un ambiente in cui le ricerche sono in realtà O (n) (ad esempio quando la memoria è rappresentata come una lista collegata). Se vuoi essere molto preciso nel calcolare Big-O, dobbiamo stilare un modello di costo che assegni un costo concreto per ogni operazione, sebbene ciò possa essere espresso in termini di alcune costanti indeterminate. Per esempio. di solito assumiamo che un carico di memoria abbia tempo di esecuzione concreto T(n) = c per una percentuale costante dic. Questa costante verrà eliminata quando si semplifica il Big-O. Per inciso, il caching non cambia la garanzia a tempo costante - finché c'è un limite superiore fisso per un'operazione, può essere considerato costante. Qui, questo sarebbe il costo di una lettura con cache miss.

Questo significa anche che Big-O non è adatto per confrontare prestazioni di algoritmi reali con carichi di lavoro noti. Due algoritmi potrebbero essere nella stessa classe di complessità, ma uno potrebbe sovraperformare l'altro di un fattore costante di 1000. O un algoritmo potrebbe avere una complessità lineare spettacolare, ma richiede così tanto pre-elaborazione che persino un algoritmo esponenziale è più veloce nella pratica (reale esempio: molti motori regex).

La complessità del tempo è un concetto matematico che si applica a un modello di calcolo. Normalmente, lo applichiamo alle macchine di Turing, che non hanno nulla come una cache, quindi la maggior parte dei normali risultati in termini di complessità temporale presuppongono effettivamente che non ci siano cache.

Ma puoi usare modelli più complessi se vuoi. Non sono a conoscenza di modelli matematici di uso comune che arrivino a imitare le cache della CPU, ma ci sono certamente "macchine di registro" che hanno una definizione matematicamente precisa, ma a differenza delle macchine di Turing, i registri sono separati dalla memoria principale. Sono stati dimostrati matematicamente equivalenti alle macchine di Turing in termini di decifrabilità, cioè quali calcoli possono eseguire, ma differiscono nelle complessità temporali con cui eseguono tali calcoli.

Ho il sospetto che le complessità temporali di una macchina di registro saranno un po 'più vicine alle "complessità temporali del mondo reale" che si ottengono quando è implicato il caching della CPU, poiché i registri sono probabilmente la forma più primitiva di caching della CPU. Ma quanto è vero dipenderà molto dai dettagli del modello che scegli. Capire quale modello matematico simuli meglio i calcoli del mondo reale è il tipo di cosa a cui i ricercatori accademici stanno ancora lavorando.