Re: Reimplement the discrete distribution functions using lookup

[Jaroslav Hajek]

On Thu, Apr 15, 2010 at 11:50 PM, David Bateman <address@hidden> wrote:
> For information as a follow-up to the bug report
>
> https://savannah.gnu.org/bugs/?29545
>
> I reimplemented the discrete_cdf, discrete_pdf and discrete_inv function
> that are also used in the empirical_* and unid* functions. A short benchmark
> script is
>
> vmax = 1000;
> v = 1:vmax;
> p = rand(1,vmax);
> p = p / sum(p);
> for n = [100,500,1000,2000]
> x = ceil(vmax*rand(1,n));
> y = rand(1,n);
> tic
> discrete_cdf(x,v,p);
> t1 = toc;
> tic
> discrete_pdf(x,v,p);
> t2 = toc;
> tic
> q = discrete_inv(y,v,p);
> t3 = toc;
> fprintf ("N %i: CDF %f s, PDF %f s, INV %f s\n", n, t1, t2, t3);
> endfor
>
> which when run with a recent tip gives
>
> N 100: CDF 0.033175 s, PDF 0.018628 s, INV 0.022826 s
> N 500: CDF 0.064294 s, PDF 0.064881 s, INV 0.073642 s
> N 1000: CDF 0.128736 s, PDF 0.130771 s, INV 0.153936 s
> N 2000: CDF 0.273697 s, PDF 0.274693 s, INV 0.290557 s
>
> and after the changeset I just pushed
>
> N 100: CDF 0.005032 s, PDF 0.005660 s, INV 0.005447 s
> N 500: CDF 0.005283 s, PDF 0.004369 s, INV 0.005893 s
> N 1000: CDF 0.005880 s, PDF 0.006766 s, INV 0.006027 s
> N 2000: CDF 0.006776 s, PDF 0.006126 s, INV 0.005350 s
>
> There are probably other statistics functions that could profit from the
> same treatment
>
> Cheers
> David
>
>

Cool. A nice demonstration that using a better algorithm typically
brings the biggest speed-ups.

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz