Re: algorithm efficiency (memory allocation issue?)

[Gert Van den Eynde]

Hi Aaron,

I think you can speed things up if you allocate the complete memory needed 
before starting the loop. Doing a 

wave = zeros(n*length(f))

before starting the loop, that is.

Bye,

Gert


On Wed, 27 Jun 2001 01:51:21 -0700, Aaron Brick said:

> hello all,
>  
>  i wrote a simple routine to reproduce a vector many times (i couldn't find
>  any built-in method of copying and aggregating whole vectors - let me know,
>  please, if i missed it). i included a progress meter and was surprised to
>  note that the algorithm ran hugely slower as time went on, perhaps in O(n^2)
>  time. i can only suspect that it had to do with memory allocation and having
>  to copy the whole data set into a new space at each iteration, but it seems
>  like allocating logarithmically bigger spaces as need grows would make more
>  sense. anywya, without knowing implementation details, i'd like to know what
>  i can do to avoid this slowdown. here is the code. f is a vector (of rows)
>  and n is the number of times to reproduce it. try running the command
>  "multiply ( (1:200)', 100 )" for a dramatic demonstration of the slowdown.
>  
>  function wave = multiply ( f, n )
>  
>       current = 0;
>       for i = ( 1 : n ) 
>               for j = ( 1 : rows (f) )
>                       wave ( ++current ) = f ( j );
>               endfor
>               fprintf ( stderr, "%d ", i );
>       endfor
>       fprintf ( stderr, "\n\n" );
>  
>  endfunction
>  
>  thanks!
>  
>  aaron.
>                             - | | | | | | | | | | -
>                             -                     -
>                             -                     -
>                             -     aaron brick     -
>                             -    address@hidden    -
>                             -                     -
>                             -                     -
>                             - | | | | | | | | | | -
>  
>  
>  
>  -------------------------------------------------------------
>  Octave is freely available under the terms of the GNU GPL.
>  
>  Octave's home on the web:  http://www.octave.org
>  How to fund new projects:  http://www.octave.org/funding.html
>  Subscription information:  http://www.octave.org/archive.html
>  -------------------------------------------------------------
>  



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------