The most common "hot spots" such middle element will be cached from the OS and looking them up will be for free.
Il problema qui è che non verranno memorizzati solo gli "hot spot", ma anche quegli elementi direttamente prima e dopo, che sono piuttosto improbabili come punti caldi. Quindi stai sprecando spazio (limitato!) Nella cache.
Le cache sono per lo più orientate ai blocchi, cioè non puoi caricare solo una piccola parte in esse, ma interi blocchi contemporaneamente.
Considera questo esempio:
x x x x x x x x x x x x x x x x
Questo è il tuo grande array ordinato, ogni x un elemento di esso. La tua cache ha due "blocchi", ognuno degli elementi di dimensione 2. È possibile caricare / scaricare un intero blocco e solo da indirizzi pari (gli elementi 0 e 1 possono essere caricati come un blocco, 1 e 2 non). Gli elementi memorizzati nella cache sono contrassegnati come c nel seguente esempio utilizzato meno di recente come strategia di sostituzione dei blocchi. ^ segna l'elemento che stiamo attualmente esaminando.
Ora facciamo una ricerca binaria per il primo elemento:
-
Take (in alto) mid element:
x x x x x x x x c c x x x x x x
^
-
Maggiore, recurse left:
x x x x c c x x c c x x x x x x
^
-
Maggiore, recurse left:
x x c c c c x x x x x x x x x x
^
-
Maggiore, recurse left:
c c c c x x x x x x x x x x x x
^
- Maggiore, recurse left, unico elemento di corrispondenza trovato (nessuna modifica alla cache).
Abbiamo caricato un totale di 8 elementi (4 blocchi) nella cache. 3 di essi non sono nemmeno stati visualizzati , ma sono stati caricati perché si trovavano accanto a un elemento che abbiamo esaminato.
Ora supponiamo di aver prima provato l'elemento centrale e gli elementi centrali della metà sinistra e destra:
x x x x x x x x x x x x x x x x
\ | /
\ | /
s s s
Ignoriamo l'attività cache di questa operazione perché viene eseguita una sola volta. Quindi i suoi costi saranno ammortizzati su molte ricerche.
Ora eseguiamo nuovamente una ricerca binaria per il primo elemento, ma questa volta ne inizi uno in questi esempi:
-
Esaminiamo l'elemento mid, che carica anche il primo nella cache e recurse left.
c c s
-
Consideriamo il primo elemento, che è maggiore di quello cercato, e quindi sappiamo che dobbiamo cercare nella regione marcata dell'intero array:
x x x x x x x x x x x x x x x x
| |
-
Facciamo una ricerca binaria nella regione contrassegnata, iniziando con il suo elemento centrale, e recurse left:
x x c c x x x x x x x x x x x x
| ^ |
-
Guardiamo l'elemento contrassegnato e abbiamo bisogno ancora una volta di recurse a sinistra per trovare l'elemento, anche se questo non porterà a nuovi carichi di cache:
c c c c x x x x x x x x x x x x
| ^ |
Abbiamo caricato un totale di 6 elementi (3 blocchi), di cui solo uno solo non è stato esaminato.