We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpSyntax Questions › I need to understand.....
Pages: 1 2 
I need to understand..... (Read 2087 times)
Re: I need to understand.....
Reply #15 - Jan 15th, 2006, 7:03pm
 
Yea, it's mathematically proven (and easily) that doubling the size of the array is faster.  Each insert takes amortized O(1), or constant, time, whereas with the method you proposed, each insert takes O(n), or linear, time.  In short, when you add a new element with your method, it copies all the existing (n) entries, which takes some constant * n time.  If you double the array, you take that same time to copy the data, but it's spaced out such that for n inserts, you do n copies total, rather than n copies for each insert (n*n total).

Vector uses this method, hence it will win hands down in every case except 2 elements.  (You don't even have to double it, you just need to make it some fraction larger than current size, like 125%, 150%, or 300%.)

Try changing your code from +1 to *2 and you'll probably get better speed than Vector, then again, who knows.  You'll need to add an extra variable for 'count' or something that keeps track of how many objects have been stored in the array (since its .length will merely be the capacity).

Marcello
Pages: 1 2