aspose file tools*
The moose likes Beginning Java and the fly likes Initial Capacity of ArrayList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Initial Capacity of ArrayList" Watch "Initial Capacity of ArrayList" New topic
Author

Initial Capacity of ArrayList

Ankush Kaundal
Ranch Hand

Joined: May 12, 2011
Posts: 36

Is there any logic which can help us in deciding ideal initial capacity of an ArrayList if we know the approximate no. of data entries to be stored?
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11422
    
  16

what's wrong with just using what size you think it needs to be?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Marco Ehrentreich
best scout
Bartender

Joined: Mar 07, 2007
Posts: 1282

Well, if you only know the approximate number of elements you want to add to an ArrayList the best thing you can probably do is use this approximate number as an initial capacity and perhaps add some more just to be sure. In the end you are trying to avoid many reallocations inside the list, so for large numbers of elements I'd say an approximate number is better than nothing.

Marco
Ankush Kaundal
Ranch Hand

Joined: May 12, 2011
Posts: 36

But still is there any way to find out the optimal initial capacity or it is just hit and trial?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18675
    
    8

The "optimal" initial capacity would depend on what it is that you want to optimize. If you clarified that, you might see your way towards the answer.
Marco Ehrentreich
best scout
Bartender

Joined: Mar 07, 2007
Posts: 1282

Ankush, you have to be aware that there's almost always not the one and only optimal solution which fits all situations. Depending on your needs and requirements there are often trade-offs and you have to decide on a case-by-case basis what could be an optimal solution for your problem.

Regarding your example with ArrayList it could be optimal to calculate the exact inital size for the ArrayList and avoid excessive reallocation of memory. But under certain circumstances it could be better to avoid preallocation of too much memory and use a low initial size. I'd even argue that for the average application in a typical environment which handles only a moderate amount of data and doesn't have special performance requirements the optimal 'solution' is to keep the code as simple as possible and simply ignore the initial size at the cost of potential reallocations of memory.

Marco
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8016
    
  22

Ankush Kaundal wrote:But still is there any way to find out the optimal initial capacity...?

One other thing that's worth noting: the array that you're trying so hard to "get right" is an array of references, not an array of objects. On my old clunker that means that for every bit of "capacity" that I save, I'm saving 4 bytes. On 64-bit Java that might be 8 (not sure how it works out references).

So: if I'm out by 1,000? I've wasted 4-8k. My Dell dinosaur has 3 Gig to play with. Even most cellphones these days have at least 32 Meg, so it's a drop in the ocean.

What's slightly more important - but only slightly - is avoiding re-allocations, since that involves not only allocating a new array, but copying the contents of the old one.

So my usual rule of thumb: if you can, make sure that your estimate is always an overestimate.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Volodymyr Levytskyi
Ranch Hand

Joined: Mar 29, 2012
Posts: 505
    
    1

Is there any logic which can help us in deciding ideal initial capacity of an ArrayList if we know the approximate no. of data entries to be stored?


Yes, there is!
Please cover my tutorial to know ArrayList profoundly.
You will find answer not only to this but to many other situations


True person is moral, false is right!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Initial Capacity of ArrayList