<div dir="ltr">Cool, thanks for looking at this.  P2 might still be better even if the whole dataset is in memory because of cache misses.  Partition, which I guess is based on quickselect, is going to run over all of the data as many times as there are bins roughly, whereas p2 only runs over it once.  From a cache miss standpoint, I think p2 is better?  Anyway, it might be worth maybe coding to verify any performance advantages?  Not sure if it should be in numpy or not since it really should accept an iterable rather than a numpy vector, right?<div><br></div><div>Best,</div><div><br></div><div>Neil</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 15, 2015 at 12:40 PM, Jaime Fernández del Río <span dir="ltr"><<a href="mailto:jaime.frio@gmail.com" target="_blank">jaime.frio@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"><div class="gmail_extra"><div class="gmail_quote"><span class="">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></span><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><span class="HOEnZb"><font color="#888888"><div><br></div><div>Jaime</div><div><br></div></font></span></div><span class="">-- <br><div>(\__/)<br>( O.o)<br>( > <) Este es Conejo. Copia a Conejo en tu firma y ayúdale en sus planes de dominación mundial.</div>
</span></div></div>
<br>_______________________________________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@scipy.org">NumPy-Discussion@scipy.org</a><br>
<a href="http://mail.scipy.org/mailman/listinfo/numpy-discussion" target="_blank">http://mail.scipy.org/mailman/listinfo/numpy-discussion</a><br>
<br></blockquote></div><br></div>