Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm writing something on how iterative Fibonacci is substantially better than recursive Fibonacci - a few lines. The main reason of this I find, as do many prominent researchers I believe, is that you don't recalculate values - space vs time. From this I thought ah ha! caching! But I'm not sure if it is caching, memoization, buffering or one of the others.

I personally think buffering to be the preloading of material before something is done with it vs caching and memorization being more of a processing based thing. The buffering notion is that I get from such a buffering a picture or a video.

What is the difference between buffering, memoization, caching and page filing?

share|improve this question
4  
An aside: A tail recursive fibonacci that uses the accumulator pattern instead of the naive recursion approach is at least as good as an iterative solution. I believe jxs.me/2010/06/28/tail-recursion-haskell contains a reasonable example. –  JasonTrue Apr 25 '12 at 17:34

2 Answers 2

up vote 2 down vote accepted

Caching is related to all the other concepts you mentioned, if you were talking about a hierarchy of concepts, caching would be the parent concept and memoization, some forms of buffering, and page files are specific forms of caching.

Memoization is storing precomputed values and then using those for looking up values rather than spending time to recalculate them. (time vs space tradeoff)

Buffering I assume you're referring to things like buffered IO, which can be used in software or hardware. In code, you can use buffered streams like in Java or C#, which will keep some amount of data in memory so programs don't have to wait for slow network/disk access. This isn't specifically caching.

Hardware buffers like in hard drives will cache a small amount of data for quick access. These are controlled by algorithms and predictions that if data was very recently used, it will probably be used again very soon.

Page files are a little different - it's a cache, but it's mainly to solve the problem of what happens when your program needs to have a lot of data in memory, but not enough memory to store that data? In environments with lots of different programs running, page files were created to solve this problem that you might have very limited RAM (shared by all apps) but significantly more storage space that could transparently be used for storing program data in addition to RAM (but significantly slower).

However, as Peter Smith mentioned, iterative vs. recursive algorithms aren't inherently memoized or anything (unless you're using constructs or languages that use transparent memoization). Recursive function calls require exponential function calls pushed onto the stack, and unless your language/compiler uses tail recursion elimination, this can be slower and also cause stack overflows.

You can memoize recursive or iterative solutions.

share|improve this answer

Iterative fibonacci vs recursive fibonacci has more to do with the fact that compilers typically don't transform non tail-end recursive functions into iterative functions. The difference between these two is keeping your variables on the stack (and in memory) for recursive, vs keeping two variables in registers saving tons of memory accesses for iterative.

It is not memoization since you don't keep a table of precalculated values (which could be done in either scenario). Memoization and caching to me are almost the same thing, both involving storing precomputed results under a key, unless by caching you get concerned about the physical CPU caches and worry about cache alignment.

Buffering is simply filling memory space via i/o from a slow device such as a network or hard drive, vs pure byte by byte stream processing which is slow due to lots of i/o accesses.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.