log(n) amortized growth for containers

[Andrei Alexandrescu via Digitalmars-d]

Many thanks to Jason Causey and Jakob Ovrum for their work on heaps and 
Randomized Slide to Front.

Here's a quick thought on growth schedule for arrays. The classic 
approach is to grow by a geometric schedule. For example: 1, 2, 4, 8, 
16, etc. That way, n memory moves are necessary for achieving a capacity 
equal to n, so on average we spend a constant amount of time per 
appended element.

The main disadvantage with this growth schedule is there are on average 
n/2 slack memory slots. Also, a growth factor of 2 is unfriendly to the 
memory allocator (long discussion) so a smaller one (such as the golden 
cut or less) would be better.

Anyhow, I was thinking why O(1) amortized growth and not O(log n)? The 
latter is considered scalable all right and the hope is to get a 
corresponding reduction in the slack memory space.

To figure a growth schedule that leads to log(n) work per element, a 
differential equation must be solved:

s(n) / s'(n) = log(x)

where s(n) will be the (continuous extension of the) growth schedule's 
sum, i.e. s(n) = f(1) + f(2) + ... + f(n). In other word, s(n) is how 
many elements we moved around, and s'(n) is the capacity after n steps. 
The division gives us how much work was done per element.

To verify, if s(n) = n, you get O(n) work per element, i.e. quadratic 
behavior for linear capacity growth. If s(n) = 2^n, you get O(1) work 
per element.

So I entered the equation above in Wolfram:

https://www.wolframalpha.com/input/?i=y%28x%29+%2F+y%27%28x%29+%3D+log%28x%29

So the growth schedule is exponential of the LogIntegral(n). Let's write 
it as:

f(n) = 2^^li(n)

Not too nice, but easy to tabulate for the relevant ranges. Let's take a 
look at the slack space at capacity f(n):

slack(f(n)) = f(n) - f(n - 1)

Sadly the expression doesn't seem to simplify and I couldn't find a good 
online plotter that can plot 2^^li(x). Here's what Mathematica free shows:

https://www.wolframalpha.com/input/?i=2%5Eli%28x%29+-+2%5Eli%28x+-+1%29

Compare with:

https://www.wolframalpha.com/input/?i=2%5Ex+-+2%5E%28x+-+1%29

The slack elements seem to grow considerably slower, which is great.

Does anyone know of a plotter that supports logarithmic integral? Of 
course better ideas about all of the above are welcome!


Thanks,

Andrei