Re: [Numpy-discussion] speed of numpy.ndarray compared to Numeric.array
To John:
Did you try larger arrays/tuples? I would guess that makes a significant difference.
No I didn't, due to the fact that these values are coordinates in 3D (x,y,z). In fact I work with a list/array/tuple of arrays with 100000 to 1M of elements or more. What I need to do is to calculate the distance of each of these elements (coordinates) to a given coordinate and filter for the nearest. The brute force method would look like this: #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def bruteForceSearch(points, point): minpt = min([(vec2Norm(pt, point), pt, i) for i, pt in enumerate(points)], key=itemgetter(0)) return sqrt(minpt[0]), minpt[1], minpt[2] #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def vec2Norm(pt1,pt2): xDis = pt1[0]-pt2[0] yDis = pt1[1]-pt2[1] zDis = pt1[2]-pt2[2] return xDis*xDis+yDis*yDis+zDis*zDis I have a more clever method but it still takes a lot of time in the vec2norm-function. If you like I can attach a running example. To Ben:
Don't know how much of an impact it would have, but those timeit statements for array creation include the import process, which are going to be different for each module and are probably not indicative of the speed of array creation.
No, the timeit statements counts the time for the statement in the first argument only, the import-thing isn't included in the time. Thomas This email and any attachments are intended solely for the use of the individual or entity to whom it is addressed and may be confidential and/or privileged. If you are not one of the named recipients or have received this email in error, (i) you should not read, disclose, or copy it, (ii) please notify sender of your receipt by reply email and delete this email and all attachments, (iii) Dassault Systemes does not accept or assume any liability or responsibility for any use of or reliance on this email.For other languages, go to http://www.3ds.com/terms/email-disclaimer.
On Mon, Jan 10, 2011 at 5:09 PM, EMMEL Thomas <Thomas.EMMEL@3ds.com> wrote:
To John:
Did you try larger arrays/tuples? I would guess that makes a significant difference.
No I didn't, due to the fact that these values are coordinates in 3D (x,y,z). In fact I work with a list/array/tuple of arrays with 100000 to 1M of elements or more. What I need to do is to calculate the distance of each of these elements (coordinates) to a given coordinate and filter for the nearest.
Note that for this exact problem, there are much better methods than brute force (O(N^2) for N vectors), through e.g. kd-trees, which work very well in low-dimension. This will matter much more than numeric vs numpy cheers, David
On Mon, Jan 10, 2011 at 5:09 PM, EMMEL Thomas <Thomas.EMMEL@3ds.com> wrote:
To John:
Did you try larger arrays/tuples? I would guess that makes a significant difference.
No I didn't, due to the fact that these values are coordinates in 3D (x,y,z). In fact I work with a list/array/tuple of arrays with 100000 to 1M of elements or more. What I need to do is to calculate the distance of each of these elements (coordinates) to a given coordinate and filter for the nearest.
Note that for this exact problem, there are much better methods than brute force (O(N^2) for N vectors), through e.g. kd-trees, which work very well in low-dimension. This will matter much more than numeric vs numpy
cheers,
David
David, Yes, of course and my real implementation uses exactly these methods, but there are still issues with the arrays. Example: If I would use brute-force it will take ~5000s for a particular example to find all points in a list of points. Theoretically it should be possible to come to O(N*log(N)) with would mean ~2s in my case. My method need ~28s with tuples, but it takes ~30s with Numeric arrays and ~60s and more with numpy.ndarrays! I just use the brute-force method since it delivers the most reusable results for performance testing, the other methods are a bit dependent on the distribution of points in space. Thomas This email and any attachments are intended solely for the use of the individual or entity to whom it is addressed and may be confidential and/or privileged. If you are not one of the named recipients or have received this email in error, (i) you should not read, disclose, or copy it, (ii) please notify sender of your receipt by reply email and delete this email and all attachments, (iii) Dassault Systemes does not accept or assume any liability or responsibility for any use of or reliance on this email.For other languages, go to http://www.3ds.com/terms/email-disclaimer.
On Mon, Jan 10, 2011 at 6:04 PM, EMMEL Thomas <Thomas.EMMEL@3ds.com> wrote:
Yes, of course and my real implementation uses exactly these methods, but there are still issues with the arrays.
Did you try kd-trees in scipy ? David
-----Original Message----- From: numpy-discussion-bounces@scipy.org [mailto:numpy-discussion- bounces@scipy.org] On Behalf Of David Cournapeau Sent: Montag, 10. Januar 2011 10:15 To: Discussion of Numerical Python Subject: Re: [Numpy-discussion] speed of numpy.ndarray compared toNumeric.array
On Mon, Jan 10, 2011 at 6:04 PM, EMMEL Thomas <Thomas.EMMEL@3ds.com> wrote:
Yes, of course and my real implementation uses exactly these methods, but there are still issues with the arrays.
Did you try kd-trees in scipy ?
David
David, No, I didn't, however, my method is very similar and as far as I understood kd-trees, they need some time for pre-conditioning the search-area and this is the same as I did. In fact I think my method is more or less the same as a kd-tree. The problem remains that I need to calculate the distance of some points at a certain point in my code (when I am in a leaf of a kd-tree). For example when I use 100000 points I end up in a leaf of my kd-tree where I need to calculate the distance for only 100 points or less (depends on the tree). The problem still remains and I use cProfile to get into the details. Most of the time it takes is in vec2Norm, everything else is very short but I need to call it as often as I have points (again 100000) and this is why 100000*0.001s takes some time. For numpy.ndarray this is 0.002s-0.003s, for Numeric.array 0.001-0.002s and for tuple ~0.001s (values from cProfile). And, by the way, the same problem appears when I need to calculate the cross-product of several vectors. In this case I have a geometry in 3D with a surface of thousands of triangles and I need to calculate the normal of each of these triangles. Again, doing a loop over tuples is faster than arrays, although in this case numpy.cross is twice as fast as Numeric.cross_product. Thomas This email and any attachments are intended solely for the use of the individual or entity to whom it is addressed and may be confidential and/or privileged. If you are not one of the named recipients or have received this email in error, (i) you should not read, disclose, or copy it, (ii) please notify sender of your receipt by reply email and delete this email and all attachments, (iii) Dassault Systemes does not accept or assume any liability or responsibility for any use of or reliance on this email.For other languages, go to http://www.3ds.com/terms/email-disclaimer. This email and any attachments are intended solely for the use of the individual or entity to whom it is addressed and may be confidential and/or privileged. If you are not one of the named recipients or have received this email in error, (i) you should not read, disclose, or copy it, (ii) please notify sender of your receipt by reply email and delete this email and all attachments, (iii) Dassault Systemes does not accept or assume any liability or responsibility for any use of or reliance on this email.For other languages, go to http://www.3ds.com/terms/email-disclaimer.
Hey, On Mon, 2011-01-10 at 08:09 +0000, EMMEL Thomas wrote:
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def bruteForceSearch(points, point):
minpt = min([(vec2Norm(pt, point), pt, i) for i, pt in enumerate(points)], key=itemgetter(0)) return sqrt(minpt[0]), minpt[1], minpt[2]
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def vec2Norm(pt1,pt2): xDis = pt1[0]-pt2[0] yDis = pt1[1]-pt2[1] zDis = pt1[2]-pt2[2] return xDis*xDis+yDis*yDis+zDis*zDis
I have a more clever method but it still takes a lot of time in the vec2norm-function. If you like I can attach a running example.
if you use the vec2Norm function as you wrote it there, this code is not vectorized at all, and as such of course numpy would be slowest as it has the most overhead and no advantages for non vectorized code, you simply can't write python code like that and expect it to be fast for these kind of calculations. Your function should look more like this: import numpy as np def bruteForceSearch(points, point): dists = points - point # that may need point[None,:] or such for broadcasting to work dists *= dists dists = dists.sum(1) I = np.argmin(dists) return sqrt(dists[I]), points[I], I If points is small, this may not help much (though compared to this exact code my guess is it probably would), if points is larger it should speed up things tremendously (unless you run into RAM problems). It may be that you need to fiddle around with axes, I did not check the code. If this is not good enough for you (you will need to port it (and maybe the next outer loop as well) to Cython or write it in C/C++ and make sure it can optimize things right. Also I think somewhere in scipy there were some distance tools that may be already in C and nice fast, but not sure. I hope I got this right and it helps, Sebastian
Hey back...
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~ ~~~
def bruteForceSearch(points, point):
minpt = min([(vec2Norm(pt, point), pt, i) for i, pt in enumerate(points)], key=itemgetter(0)) return sqrt(minpt[0]), minpt[1], minpt[2]
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~ ~~~~
def vec2Norm(pt1,pt2): xDis = pt1[0]-pt2[0] yDis = pt1[1]-pt2[1] zDis = pt1[2]-pt2[2] return xDis*xDis+yDis*yDis+zDis*zDis
I have a more clever method but it still takes a lot of time in the vec2norm-function. If you like I can attach a running example.
if you use the vec2Norm function as you wrote it there, this code is not vectorized at all, and as such of course numpy would be slowest as it has the most overhead and no advantages for non vectorized code, you simply can't write python code like that and expect it to be fast for these kind of calculations.
Your function should look more like this:
import numpy as np
def bruteForceSearch(points, point): dists = points - point # that may need point[None,:] or such for broadcasting to work dists *= dists dists = dists.sum(1) I = np.argmin(dists) return sqrt(dists[I]), points[I], I
If points is small, this may not help much (though compared to this exact code my guess is it probably would), if points is larger it should speed up things tremendously (unless you run into RAM problems). It may be that you need to fiddle around with axes, I did not check the code. If this is not good enough for you (you will need to port it (and maybe the next outer loop as well) to Cython or write it in C/C++ and make sure it can optimize things right. Also I think somewhere in scipy there were some distance tools that may be already in C and nice fast, but not sure.
I hope I got this right and it helps,
Sebastian
I see the point and it was very helpful to understand the behavior of the arrays a bit better. And your attempt improved the bruteForceSearch which is up to 6 times faster. But in case of a leaf in a kd-tree you end up with 50, 20, 10 or less points where the speed-up is reversed. In this particular case 34000 runs take 90s with your method and 50s with mine (not the bruteForce). I see now the limits of the arrays but of course I see the chances and - coming back to my original question - it seems that Numeric arrays were faster for my kind of application but they might be slower for larger amounts of data. Regards Thomas This email and any attachments are intended solely for the use of the individual or entity to whom it is addressed and may be confidential and/or privileged. If you are not one of the named recipients or have received this email in error, (i) you should not read, disclose, or copy it, (ii) please notify sender of your receipt by reply email and delete this email and all attachments, (iii) Dassault Systemes does not accept or assume any liability or responsibility for any use of or reliance on this email.For other languages, go to http://www.3ds.com/terms/email-disclaimer.
Hi, On 01/10/2011 09:09 AM, EMMEL Thomas wrote:
No I didn't, due to the fact that these values are coordinates in 3D (x,y,z). In fact I work with a list/array/tuple of arrays with 100000 to 1M of elements or more. What I need to do is to calculate the distance of each of these elements (coordinates) to a given coordinate and filter for the nearest. The brute force method would look like this:
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def bruteForceSearch(points, point):
minpt = min([(vec2Norm(pt, point), pt, i) for i, pt in enumerate(points)], key=itemgetter(0)) return sqrt(minpt[0]), minpt[1], minpt[2]
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def vec2Norm(pt1,pt2): xDis = pt1[0]-pt2[0] yDis = pt1[1]-pt2[1] zDis = pt1[2]-pt2[2] return xDis*xDis+yDis*yDis+zDis*zDis
I am not sure I understood the problem properly but here what I would use to calculate a distance from horizontally stacked vectors (big): ref=numpy.array([0.1,0.2,0.3]) big=numpy.random.randn(1000000, 3) big=numpy.add(big,-ref) distsquared=numpy.sum(big**2, axis=1) Pascal
Hi, Spatial hashes are the common solution. Another common optimization is using the distance squared for collision detection. Since you do not need the expensive sqrt for this calc. cu. On Mon, Jan 10, 2011 at 3:25 PM, Pascal <pascal22p@parois.net> wrote:
Hi,
On 01/10/2011 09:09 AM, EMMEL Thomas wrote:
No I didn't, due to the fact that these values are coordinates in 3D (x,y,z). In fact I work with a list/array/tuple of arrays with 100000 to 1M of elements or more. What I need to do is to calculate the distance of each of these elements (coordinates) to a given coordinate and filter for the nearest. The brute force method would look like this:
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def bruteForceSearch(points, point):
minpt = min([(vec2Norm(pt, point), pt, i) for i, pt in enumerate(points)], key=itemgetter(0)) return sqrt(minpt[0]), minpt[1], minpt[2]
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ def vec2Norm(pt1,pt2): xDis = pt1[0]-pt2[0] yDis = pt1[1]-pt2[1] zDis = pt1[2]-pt2[2] return xDis*xDis+yDis*yDis+zDis*zDis
I am not sure I understood the problem properly but here what I would use to calculate a distance from horizontally stacked vectors (big):
ref=numpy.array([0.1,0.2,0.3]) big=numpy.random.randn(1000000, 3)
big=numpy.add(big,-ref) distsquared=numpy.sum(big**2, axis=1)
Pascal _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
participants (5)
-
David Cournapeau -
EMMEL Thomas -
Pascal -
René Dudfield -
Sebastian Berg