[Numpy-discussion] fast way of doing "cross-multiplications" ?

Eric Emsellem emsellem at obs.univ-lyon1.fr
Tue Jul 18 10:36:04 CDT 2006


thanks for the tips. (indeed your "add.reduce" is correct: I just wrote
this down too quickly, in the script I have a "sum" included).

And yes you are right for the memory issue, so I may just keep the loop
in and try to make it work on a fast PC...(or use parallel processes)

(is "sum" different than "add.reduce"?)

thanks again to both Bill Baxter and Perry Greenfield for their fast
(and helpful!) answers.

cheers

Eric

Perry Greenfield wrote:
>
> On Jul 18, 2006, at 10:23 AM, Eric Emsellem wrote:
>
>> Hi,
>>
>> I have a specific quantity to derive from an array, and I am at the
>> moment unable to do it for a too large array because it just takes too
>> long! So I am looking for an advice on how to efficiently compute such a
>> quantity:
>>
>> I have 3 arrays of N floats (x[...], y[..], z[..]) and I wish to do:
>>
>> result = 0.
>> for i in range(N) :
>>    for j in range(i+1,N,1) :
>>       result += 1. / sqrt((x[j] - x[i])**2 + (y[j] - y[i])**2 + (z[j] -
>> z[i])**2)
>>
>>
>> Of course the procedure written above is very inefficient and I thought
>> of doing:
>>
>> result = 0.
>> for i in range(N) :
>>    result += 1. / sqrt((x[i+1:] - x[i])**2 + (y[i+1:] - y[i])**2 +
>> (z[i+1:] - z[i])**2)
>>
>> Still, this is quite slow and not workable for very large arrays (> 10^6
>> floats per array).
>>
>> Any hint on how to speed things up here?
>>
>> Thanks in advance!
>>
>> Eric
>
> Perhaps I'm misunderstanding the last variant but don't you want
> something like:
>
> result = 0.
> for i in range(N) :
>    result += add.reduce(1. / sqrt((x[i+1:] - x[i])**2 + (y[i+1:] -
> y[i])**2 +
> (z[i+1:] - z[i])**2))
>
> instead since the expression yields an array with a decreasing size
> each iteration?
>
> But besides that, it seems you are asking to do roughly 10^12 of these
> computations  for 10^6 points. I don't see any way to avoid that given
> what you are computing. The solution Bill Baxter gives is fine (I
> think, I haven't looked at it closely), but the usual problem of doing
> it without any looping is that it requires an enormous amount of
> memory (~10^12 element arrays) if I'm not mistaken. Since your second
> example is iterating over large arrays (most of the time, not near the
> end), I'd be surprised if you can do much better than that (the
> looping overhead should be negligible for such large arrays). Do you
> have examples written in other languages that run much faster? I guess
> I would be surprised to see it possible to do more than a few times
> faster in any language without some very clever optimizations.
>
> Perry




More information about the Numpy-discussion mailing list