Path: news.mathworks.com!newsfeed-00.mathworks.com!arclight.uoregon.edu!hammer.uoregon.edu!logbridge.uoregon.edu!newsfeed.stanford.edu!lnsnews.lns.cornell.edu!newsstand.cit.cornell.edu!not-for-mail
From: "Stephen Vavasis" <vavasis@cs.cornell.edu>
Newsgroups: comp.soft-sys.matlab
Subject: growing array in Matlab?
Date: Wed, 17 Aug 2005 11:16:22 -0400
Organization: Cornell University
Lines: 97
Sender: sav11@cornell.invalid
Message-ID: <ddvkd9$7ar$1@ruby.cit.cornell.edu>
Reply-To: "Stephen Vavasis" <vavasis@cs.cornell.edu>
NNTP-Posting-Host: dhcp99-23.cs.cornell.edu
X-Trace: ruby.cit.cornell.edu 1124291817 7515 128.84.99.23 (17 Aug 2005 15:16:57 GMT)
X-Complaints-To: newsmgr@cornell.edu
NNTP-Posting-Date: Wed, 17 Aug 2005 15:16:57 +0000 (UTC)
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2900.2180
X-RFC2646: Format=Flowed; Original
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180
Xref: news.mathworks.com comp.soft-sys.matlab:296418


A well-known issue with Matlab is that it performs badly if you repeatedly 
add elements to the end of an array like this:

a = [];
while <condition>
  a = [a; sin(x)];
end

 (run time is quadratic -- see the timings at the end of this email).  If 
you know in advance how large a should be, then you can simply declare it 
before the loop: a = zeros(total_a_size,1).  But if you don't know the size, 
you can use the following technique to implement arrays that grow 
exponentially:

a = [];
a_size = 0;
while <condition>
  a_size = a_size + 1;
  if a_size > length(a)
    a = [a;zeros(floor(0.4*a_size) + 4,1)];
  end
  a(a_size) = sin(x);
end
a = a(1:a_size);

This performs much better (see timings below).

The question is how to do this cleanly.  Is it possible to write a class 
that implements exponentially growing arrays efficiently?  I have an 
application that needs about ten such arrays.

Thanks,
Steve Vavasis


function a = testappend(n)
numtrial = 4;
avetime = 0;
for j = 1 : numtrial
  tic
  a = [];
  for j = 1 : n
    a = [a;sin(j)];
  end
  avetime = avetime + toc;
end
avetime = avetime / numtrial


function a = testappend2(n)
numtrial = 4;
avetime = 0;
for j = 1 : numtrial
  tic
  a = [];
  a_size = 0;
  for j = 1 : n
    a_size = j;
    if length(a) < a_size
      a = [a;zeros(max(a_size-length(a),floor(length(a)*.4))+4,1)];
      a(j) = sin(j);
    end
  end
  a = a(1:a_size);
  avetime = avetime + toc;
end
avetime = avetime / numtrial


>> testappend(4000);
avetime =
  1.2900e-001
>> testappend(8000);
avetime =
  6.9950e-001
>> testappend(16000);
avetime =
  2.3725e+000
>> testappend(32000);
avetime =
  1.1506e+001


>> testappend2(4000);
avetime =
  3.7500e-003
>> testappend2(8000);
avetime =
  7.7500e-003
>> testappend2(16000);
avetime =
  1.5500e-002
>> testappend2(32000);
avetime =
  5.4750e-002