Re: algorithm efficiency (memory allocation issue?)

[Paul Kienzle]

Matcompat has repmat(A,m,n) which repeats the matrix blockwise m x n
times.  In your case use repmat(f,n,1).

You could also use kron(ones(n,1),f), but this is slower than repmat,
even with matcompat's improved kron function.

An old packaged version of matcompat is available at

        http://users.powernet.co.uk/kienzle/octave/matcompat

Matcompat has since been incorporated into octaveSF at

        http://sf.net/projects/octave

but is only available in CVS as we have not yet built a package out of it.

Paul Kienzle
address@hidden

---
## Copyright (C) 2000 Paul Kienzle
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 2 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with this program; if not, write to the Free Software
## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

## -*- texinfo -*-
## @deftypefn {Function File} {} repmat (@var{A}, @var{m}, @var{n})
## @deftypefnx {Function File} {} repmat (@var{A}, address@hidden @var{n}])
## Form a block matrix of size @var{m} by @var{n}, with a copy of matrix
## @var{A} as each element.  If @var{n} is not specified, form an 
## @var{m} by @var{m} block matrix.
## @end deftypefn

## Author: Paul Kienzle <address@hidden>
## Created: July 2000

## 2001-06-27 Paul Kienzle <address@hidden>
## * cleaner, slightly faster code

function x = repmat (b, m, n)
  if (nargin < 2 || nargin > 3)
    usage ("repmat (a, m, n)");
  endif

  if nargin == 2
    if is_scalar (m)
      n = m;
    elseif (is_vector (m) && length (m) == 2)
      n = m (2);
      m = m (1);
    else
      error ("repmat: only builds 2D matrices")
    endif
  endif

  [rb, cb] = size (b);
  if (isempty (b))
    x = zeros (m*rb, n*cb);
  else
    x = b ([1:rb]' * ones(1,m), [1:cb]' * ones(1,n));
  endif

endfunction
---


On Wed, Jun 27, 2001 at 01:51:21AM -0700, Aaron Brick wrote:
> 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
-------------------------------------------------------------