Page 1 of 1

Caching: In Laymans Terms Please...

Posted: Fri Mar 19, 2004 3:28 pm
by randomblink
Ok, I have heard caching discussed on many different forums.
Is there someone here who can explain fairly simply what it means?
Why would I use it?
What is the best method?
etc...

I would be happy to look up something if someone could let me know what the best information source out there is... thanks...

Posted: Fri Mar 19, 2004 3:36 pm
by Illusionist
have you tried googling??
Results 4 and 5 look promising!

googling...

Posted: Fri Mar 19, 2004 3:37 pm
by randomblink
d'oh!
Yeah, I am an idiot sometimes... chuckle. Thanks...

Posted: Fri Mar 19, 2004 3:42 pm
by Illusionist
lol, nP, jsut remember, Google is your friend!!

Posted: Sun Mar 21, 2004 9:38 am
by eletrium
cache P Pronunciation Key (ksh)
n.
A hiding place used especially for storing provisions.
A place for concealment and safekeeping, as of valuables.
A store of goods or valuables concealed in a hiding place: maintained a cache of food in case of emergencies.

----------------------------------------------------
That's where the word comes from. Remember computer vocabulary comes from real world stuff, and understanding the source helps to learn the meaning in computers. My personal favorite is Domain. You see and hear that word in 10,000 different places in computing, and it always means something slightly different. But it is based on the definition:

do·main P Pronunciation Key (d-mn)
n.
A territory over which rule or control is exercised.
A sphere of activity, concern, or function; a field: the domain of history.

Network domain = Territory of the Network. Or something along those lines.

----------------------------------------

Cacheing - In a computer sense, cacheing is just storing information close at hand so that you can retrieve it fast. It is a VERY general term and has VERY general useage.

function doSomething{
variable V = functionGetValue;
while i < V do BLah
}

you can just keep calling the function functionGetValue, but since you KNOW you're going to be repeatedly calling it, you store it in a local variable to save you from calling it.

HERE IS THE ABSOLUTE KEY TO CACHES!!!!

Anything you do on a computer costs you time. Make sure when you cache that you ask yourself: Is the overhead in doing this MORE then the time savings of not having to recall it?

-------------------------

Now, if you have a set of data that is complex, you can't just store it in a single local variable. You need some form of electronic structure in which to store the data. That is an entire college course in itself. Data Structures.

How much of a difference can it make? Lets do the math.

Take five variable 1-5.

1 2 3 4 5

Using a computer, find 4.

Is 1 = 4? No
Is 2 = 4? No
Is 3 = 4? No
Is 4 = 4? Yes found.

That search cost you 4 comparisons. On average, given that search method, you will take 3 comparisons to find your number as long as it is random. (Sometimes you look fo r1 and only cost you 1 comparison, others you eat all 5.)

No big deal at this point. If this were in a program I'd use an array and just search that way. 3 Comparisons is nothing.

Now, pump that number up to 2 Billion. Now on AVERAGE, you have to spend 1 billion comparisons to find your number. Ruh roh.

You need to find a more efficient means of storing that data. NOW, spending extra time ORDERING your data and PUTTING it in a more complex structure will cost you more computing time. BUT, the time SAVINGS will most likely be worth it.

Which "Data Structure" is best? Depends on the situation. How do you figure out which is best for which situation? Make a bunch of different ones and test them out in your situation. It is the ONLY way to know for sure. Switching one in for another is very easy if you program things correctly (Common interfaces).

How much time CAN you save? Imagine your simplest of structures: Binary Search Tree. You store data in a "Node", and each "Node" has a pointer (or reference) to two other nodes. Normally called Left and Right.

The first piece of data goes into the root node. The next piece of data is added using this method: If it is GREATER then the data in the node, it goes in its OWN node to the RIGHT of the root node. If it is LESS then the root node it goes in its own node to the LEFT of the root node.

In a perfect situation, the data fills in like a pyramid (more complex structures are trees that Guarantee that it fills in perfectly, called balancing, but that's advanced).

Your first level has one node, your second level has 2, your third level has 4, your fourth level has 8. And so on. Now, imagine your data is on the fourth level down from the root.

Is my value the same as the root node? No
Is my value greater then or less then the root node? Greater than. Go RIGHT.

Is my value the same as the node to the root's right? No.
Is my value greater then or less then the node to the root's right? Less then than. Go LEFT.

And so on. At most, if the tree is 4 levels, you will have at MOST 4 of these sets of comparisons. (A 4 level tree is not near worth the effort btw, but it is easier to think of).

NOW, imagine that you had that 2 billion things of data again. In a perfectly balanced search tree, a tree that is 32 levels deep holds 2147483648 Nodes. In a linear search, you had 1 billion comparisons. In the binary search tree you just went to 32 at Worst.

Now that you can see the difference in doing things the right way and doing things the wrong way in terms of speed, think on it some more and let it sink in. Then go read up on data structures in a good text book or something.

Posted: Sun Mar 21, 2004 10:59 pm
by randomblink
wow....
That was very detailed and extremely helpful...
Thanks a bunch man... way cool of ya...

Posted: Mon Mar 22, 2004 10:05 am
by eletrium
Sorry about that. You caught me overcaffeinated. :(