Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Initial Capacity of ArrayList

 
Ankush Kaundal
Ranch Hand
Posts: 36
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12146
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
what's wrong with just using what size you think it needs to be?
 
Marco Ehrentreich
best scout
Bartender
Posts: 1294
IntelliJ IDE Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 36
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But still is there any way to find out the optimal initial capacity or it is just hit and trial?
 
Paul Clapham
Sheriff
Posts: 21133
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1294
IntelliJ IDE Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10422
63
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Volodymyr Lysenko
Ranch Hand
Posts: 511
1
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic