<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Apr 15, 2015 at 8:06 AM, Neil Girdhar <span dir="ltr"><<a href="mailto:mistersheik@gmail.com" target="_blank">mistersheik@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">You got it.  I remember this from when I worked at Google and we would process (many many) logs.  With enough bins, the approximation is still really close.  It's great if you want to make an automatic plot of data.  Calling numpy.partition a hundred times is probably slower than calling P^2 with n=100 bins.  I don't think it does O(n) computations per point.  I think it's more like O(log(n)).</div></blockquote><div><br></div><div>Looking at it again, it probably is O(n) after all: it does a binary search, which is O(log n), but it then goes on to update all the n bin counters and estimations, so O(n) I'm afraid. So there is no algorithmic advantage over partition/percentile: if there are m samples and n bins, P-2 that O(n) m times, while partition does O(m) n times, so both end up being O(m n). It seems to me that the big thing of P^2 is not having to hold the full dataset in memory. Online statistics (is that the name for this?), even if only estimations, is a cool thing, but I am not sure numpy is the place for them. That's not to say that we couldn't eventually have P^2 implemented for histogram, but I would start off with a partition based one.</div><div><br></div><div>Would SciPy have a place for online statistics? Perhaps there's room for yet another scikit?</div><div><br></div><div>Jaime</div><div><br></div></div>-- <br><div class="gmail_signature">(\__/)<br>( O.o)<br>( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus planes de dominación mundial.</div>
</div></div>