[Numpy-discussion] Find n closest values

[Eelco Hoogendoorn]

That's pretty cool; and it makes sense that way. Still, couldn't you fold
this kind of computation into a shader?

Have you looked at vispy btw? I think its a really nice initiative; having
a high quality vector graphics module in there would make it even better.
Would be nice if those projects could be merged.


On Sun, Jun 22, 2014 at 9:51 PM, Nicolas P. Rougier <
Nicolas.Rougier at inria.fr> wrote:

>
> Actually, it's already working pretty well but it slows down when you're
> doing a lot of zoom in/out.
>
> The trick is that rendering is done using shader (OpenGL) and this
> computation is used to give information to the shader to where to draw
> antialiased lines. In the end, this shader is able to draw any amiunt of
> grids/ticks (as in matplotlib). Some old example are available from here:
> https://github.com/rougier/gl-agg
>
> I tested your solution and it is faster by only a tiny amount but the way
> you wrote it might open the door for other improvements. Thanks.
>
>
> Nicolas
>
> On 22 Jun 2014, at 21:14, Eelco Hoogendoorn <hoogendoorn.eelco at gmail.com>
> wrote:
>
> > Protip: if you are writing your own rasterization code in python, be
> prepared to forget about performance altogether.
> >
> > Something like numba or other c-like extension will be necessary unless
> you are willing to leave big gobs of performance on the table; and even
> with pure C you will get nowhere close to the performance of super-duper
> optimized library code you are used to.
> >
> > But before you go down that rabbit hole, its probably worth thinking
> about whether you can get an existing rendering framework to do what you
> want to do.
> >
> >
> > On Sun, Jun 22, 2014 at 8:30 PM, Nicolas P. Rougier <
> Nicolas.Rougier at inria.fr> wrote:
> >
> > Thanks, I'll try your solution.
> >
> > Data (L) is not so big actually, it represents pixels on screen and (I)
> represents line position (for grids). I need to compute this quantity
> everytime the user zoom in or out.
> >
> >
> > Nicolas
> >
> >
> > On 22 Jun 2014, at 19:05, Eelco Hoogendoorn <hoogendoorn.eelco at gmail.com>
> wrote:
> >
> > > Well, if the spacing is truly uniform, then of course you don't really
> need the search, and you can do away with the extra log-n, and there is a
> purely linear solution:
> > >
> > > def find_closest_direct(start, end, count, A):
> > >     Q = (A-start)/(end-start)*count
> > >     mid = ((Q[1:]+Q[:-1]+1)/2).astype(np.int)
> > >     boundary = np.zeros(count, np.int)
> > >     boundary[mid] = 1
> > >     return np.add.accumulate(boundary)
> > >
> > > I expect this to be a bit faster, but nothing dramatic, unless your
> datasets are huge. It isn't really more or less elegant either, id say.
> Note that the output isn't 100% identical; youd need to do a little
> tinkering to figure out the correct/desired rounding behavior.
> > >
> > >
> > > On Sun, Jun 22, 2014 at 5:16 PM, Nicolas P. Rougier <
> Nicolas.Rougier at inria.fr> wrote:
> > >
> > > Thanks for the answer.
> > > I was secretly hoping for some kind of hardly-known numpy function
> that would make things faster auto-magically...
> > >
> > >
> > > Nicolas
> > >
> > >
> > > On 22 Jun 2014, at 10:30, Eelco Hoogendoorn <
> hoogendoorn.eelco at gmail.com> wrote:
> > >
> > > > Perhaps you could simplify some statements, but at least the
> algorithmic complexity is fine, and everything is vectorized, so I doubt
> you will get huge gains.
> > > >
> > > > You could take a look at the functions in scipy.spatial, and see how
> they perform for your problem parameters.
> > > >
> > > >
> > > > On Sun, Jun 22, 2014 at 10:22 AM, Nicolas P. Rougier <
> Nicolas.Rougier at inria.fr> wrote:
> > > >
> > > >
> > > > Hi,
> > > >
> > > > I have an array L with regular spaced values between 0 and width.
> > > > I have a (sorted) array I with irregular spaced values between 0 and
> width.
> > > >
> > > > I would like to find the closest value in I for any value in L.
> > > >
> > > > Currently, I'm using the following script but I wonder if I missed
> an obvious (and faster) solution:
> > > >
> > > >
> > > > import numpy as np
> > > >
> > > > def find_closest(A, target):
> > > >     idx = A.searchsorted(target)
> > > >     idx = np.clip(idx, 1, len(A) - 1)
> > > >     left = A[idx - 1]
> > > >     right = A[idx]
> > > >     idx -= target - left < right - target
> > > >     return idx
> > > >
> > > > n, width = 256, 100.0
> > > >
> > > > # 10 random sorted values in [0,width]
> > > > I = np.sort(np.random.randint(0,width,10))
> > > >
> > > > # n regular spaced values in [0,width]
> > > > L = np.linspace(0, width, n)
> > > >
> > > > print I[find_closest(I,L)]
> > > >
> > > >
> > > >
> > > > Nicolas
> > > > _______________________________________________
> > > > NumPy-Discussion mailing list
> > > > NumPy-Discussion at scipy.org
> > > > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> > > >
> > > > _______________________________________________
> > > > NumPy-Discussion mailing list
> > > > NumPy-Discussion at scipy.org
> > > > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> > >
> > > _______________________________________________
> > > NumPy-Discussion mailing list
> > > NumPy-Discussion at scipy.org
> > > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> > >
> > > _______________________________________________
> > > NumPy-Discussion mailing list
> > > NumPy-Discussion at scipy.org
> > > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> >
> > _______________________________________________
> > NumPy-Discussion mailing list
> > NumPy-Discussion at scipy.org
> > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> >
> > _______________________________________________
> > NumPy-Discussion mailing list
> > NumPy-Discussion at scipy.org
> > http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20140622/d1a7b1fd/attachment.html>