help-octave
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Vectorizing loops


From: Jordi Gutiérrez Hermoso
Subject: Re: Vectorizing loops
Date: Thu, 12 Jan 2012 15:23:00 -0500

On 12 January 2012 14:59, andrewcd <address@hidden> wrote:
> My problem:  I'm trying to simulate diffusion of a thing in space, and to do
> that I need to calculate the Euclidian distance between all of the nodes.  I
> have it below in loop format.

This is a classic use case of broadcasting. In 3.6.0, probably to be
released later today, you can do

    points = rand(100,3);
    distances = sqrt(sumsq(permute(p, [1,3,2]) - permute(p, [3, 1, 2]), 3))

In older versions of Octave, you have to force the broadcasting for -
with bsxfun(@minus, a, b) instead of a - b.

But this won't work for 1e6 people. Then you would need to store
around 1e12 entries, maybe 5e11, but that won't be much better. This
exceeds the default 32-bit index size Octave, and compiling 64-bit
indexing is a difficult task I have never seen anyone succeed at.

Can you do better than finding all pairwise differences? For example,
if you are only interested in the nearest neighbours of each entry,
you can use metric trees to obtain an O(n log n) algorithm instead of
O(n^2).

HTH,
- Jordi G. H.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]