Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Anton Shepelev <anton.txt@g{oogle}mail.com>
Newsgroups: comp.lang.c,sci.stat.math
Subject: Re: realloc() - frequency, conditions, or experiences about
 relocation?
Date: Mon, 8 Jul 2024 19:34:56 +0300
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <20240708193456.a1ebe2d0872239c525120d84@g{oogle}mail.com>
References: <v4ojs8$gvji$1@dont-email.me>
	<875xu8vsen.fsf@bsb.me.uk>
	<v4ovqf$j5hq$1@dont-email.me>
	<87zfrjvqp6.fsf@bsb.me.uk>
	<v4pb4v$lhgk$1@dont-email.me>
	<20240617180249.96dfaafa89392827aa162434@g{oogle}mail.com>
	<v4tuvf$1qto5$1@dont-email.me>
	<v4u7dm$1t2pu$1@dont-email.me>
	<20240620015347.9bdcc4df03ab63d096375450@gmail.moc>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 08 Jul 2024 18:34:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="46dbe6ab9786220f9431ea65e0802f88";
	logging-data="1007462"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18dW5OrM9YwP9VEUxwAYzRfAOolvMyNtVk="
Cancel-Lock: sha1:9pHXKQsEvabZtBG4GdPejG6e5Sg=
X-Newsreader: Sylpheed 3.7.0 (GTK+ 2.24.30; i686-pc-mingw32)
Bytes: 2500

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