Double After Full

An algorithm for space allocation:

When a container gets full, reallocate with twice as much space as last time.

It sounds like it will be too greedy to work out. In practice, it's usually a good space/time tradeoff.

Mathematical Basis.

This scheme of doubling memory is denoted as x2

See basic Mathematics text for 'sum of geometric series'. Note how this demonstrates the lie of big O analysis. Big O notation ignores all 'k' values, but for the x1.001 algorithm the 'k' is likely to actually be the only important part for many practical values of N.

A more controversial but accurate statement and analysis. Conclusion: Known uses/references: Lack of uses: I am not Knuth, but I don't think anyone else authoring this page is either: In general, if when you run out of space you allocate k times as much again, then (in the limit of large N)

We can redline the bogosity meter and claim that the best overall efficiency comes when the product of these two inefficiency factors is as small as possible; that means you're minimizing k/log(k), which happens when k=e. Ha.

(In reality, you should take little notice of this sort of analysis. Try some different schemes and measure.) False. This type of analysis is as (not more) important as experimenting. Anyone who does (or is only capable of) only one of the two is doomed to mediocrity.

Suppose your data structures can shrink as well as grow. You might think that you should double your allocation when you fill up, and halve your allocation when you can. That's a bad idea, because if the size happens to wobble around near the boundary you'll spend all your time growing and shrinking. So you should build in some hysteresis: grow and shrink by a factor of k, but don't shrink until you're too large by a factor of k1, where k1>k.

Example: Double when full, halve when one quarter full.

View edit of November 13, 2014 or FindPage with title or text search