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
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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
On So, 20140622 at 17:16 +0200, Nicolas P. Rougier wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
I doubt it is faster, but if you got scipy anyway, using KDTree may be pretty idiomatic.
 Sebastian
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr> wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
Also, if you use scipy.spatial.KDTree, make sure to use cKDTree; the native python kdtree is sure to be slow as hell.
On Sun, Jun 22, 2014 at 7:05 PM, Eelco Hoogendoorn < hoogendoorn.eelco@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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr> wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
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@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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
Protip: if you are writing your own rasterization code in python, be prepared to forget about performance altogether.
Something like numba or other clike 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 superduper 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@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@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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr> wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that
would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
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/glagg
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@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 clike 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 superduper 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@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@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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
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@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/glagg
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@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 clike 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 superduper 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@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@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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr> wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function
that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn <
hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
On 22 Jun 2014, at 22:52, Eelco Hoogendoorn hoogendoorn.eelco@gmail.com wrote:
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.
I'm part of vispy actually, those are side experiments for this project.
Nicolas
On Sun, Jun 22, 2014 at 9:51 PM, Nicolas P. Rougier Nicolas.Rougier@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/glagg
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@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 clike 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 superduper 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@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@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 logn, and there is a purely linear solution:
def find_closest_direct(start, end, count, A): Q = (Astart)/(endstart)*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@inria.fr wrote:
Thanks for the answer. I was secretly hoping for some kind of hardlyknown numpy function that would make things faster automagically...
Nicolas
On 22 Jun 2014, at 10:30, Eelco Hoogendoorn hoogendoorn.eelco@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@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
I would echo KDTree, but one way I think you can simplify the existing code you have is to shift the values of L by half the spacing, then you shouldn't need the check for left and right values.
Cheers! Ben Root
On Sun, Jun 22, 2014 at 4:22 AM, Nicolas P. Rougier < Nicolas.Rougier@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 _______________________________________________ NumPyDiscussion mailing list NumPyDiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
participants (4)

Benjamin Root

Eelco Hoogendoorn

Nicolas P. Rougier

Sebastian Berg