Re: realloc() - frequency, conditions, or experiences about relocation?

I had plumb forgot about this solution of mine:

   p0 = 1-e^(L*x0)            ,
   p1 = 1-e^(L*x1)            ,
   x1 = k*x0 (by our strategy), =>
   p1 = 1-(1-p0)^k            .
>
which does not depend on the distribution and lets us
generalise this approach for any distribution:
>
              x1 = Q( 1 - ( 1 - CDF(x0) )^k )
where:
>
   x0    : the required size
   x1    : the new recommended capacity
   Q(p)  : the p-Quantile of the given distribution
   CDF(x): the CDF of the given distribution
   k>1   : balance between speed and space efficiency

Let us test it with the exponential distribution, for which:

  Q  (p) = -Ln( 1 - p )/L
  CDF(x) =  1 - e^(-Lx)

Substituting these into the equation for x1:

  x1 = Q ( 1 - ( 1 - ( 1 - e^(-Lx0)  ) )^k ) =
       Q ( 1 - ( e^(-Lx0)              )^k ) =
       Q ( 1 -   e^(-kLx0)                 ) =
      -Ln( e^(-kLx0) )/L                     = k*x0 (QED)

That is, my solution is a/the generalisation of the
exponential growth strategy.

--
()  ascii ribbon campaign -- against html e-mail
/\  www.asciiribbon.org   -- against proprietary attachments