Algorithms For Dummies

Arranging cached computer data

Computers  are  often  processing  the  same  data  multiple  times.  Obtaining  data 

from  disk  or  the  Internet  requires  times  and  costs  computational  time. 

Consequently, it’s useful to store often-used data in local storage where it’s easier 

to access (and maybe already preprocessed). A cache, which is usually a series of 

memory slots or space on disk reserved for that need, fulfills the purpose.

For instance, when reviewing your web browser’s history, you likely notice that 

only a part of traffic is made of new websites, whereas you spend a large amount 

of time and page requests on sites you know well. Storing in cache some parts of 

commonly  seen  websites  (such  as  the  header,  background,  some  pictures,  and 

some pages that seldom change) can really improve your web experience because 

it reduces the need to download data again. All you need is the new data from the 

Internet because most of what you want to see is already somewhere in your com-

puter. (The cache of a web browser is a disk directory.)

The problem isn’t new. In the 1960s, László Bélády, a Hungarian computer scien-

tist working at IBM Research, hypothesized that the best way to store information 

in a computer for prompt reuse is to know what data is needed in the future and 

---

CHAPTER 15