Re: Vectorisation

[Jaroslav Hajek]

On Thu, Jul 8, 2010 at 1:07 PM, gastonjulia <address@hidden> wrote:
>
> Hi,
>
> thanks for all the suggestions.
>
> `count = accumarray (data(:,3), 1, [1, 20]);' was not quite working, but I
> looked up accumarray and found that `count_fast = accumarray
> (data(:,3),1:1);' did generate the same vector as for loop solution. I am
> still not quite sure about the arguments of accumarray but it does the job
> in 1.3 seconds, compared to the for loop which takes 43 seconds.
>
> So thanks very much,
> Gaston
>
> p.s.: if it is of any interest, here is the error message of count =
> accumarray (data(:,3), 1, [1, 20]);
> error: accumarray: inconsistent dimensions
> error: evaluating if command near line 67, column 3
> error: called from `accumarray' in file
> `/usr/share/octave/3.0.5/m/general/accumarray.m'
> error: evaluating assignment expression near line 4, column 7

This bug has been fixed since. Btw, accumarray has seen some
significant optimizations in 3.2.x (and more in 3.3.5x+). If speed is
of any concern to you, I strongly recommend you upgrade to at least
3.2.x.

I'm seeing this with 3.3.51+:

octave:1> data = ceil (20*rand(2e6, 5));
octave:2>  tic; count = zeros(1,20); for i = 1:length(data),
count(data(i, 3))++; endfor; toc
Elapsed time is 13.5815 seconds.
octave:3>  tic; count = accumarray (data(:,3), 1, [1, 20]); toc
Elapsed time is 0.0152099 seconds.

i.e. it's almost 900x faster than the interpreted loop. Note that in
Octave 3.0.5, accumarray uses an O(M+N*log(N)) algorithm. (where M is
number of bins and N number of indices). In 3.2.x, O(M+N) algorithm is
used in the summation case. In the development version, all non-sparse
paths are O(M+N) (using a cute trick with sort()), with sum/min/max
reductions being significantly faster. The approach suggested by Jordi
(and originally used in histc) is O(M*N).

regards

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz