4

I have a simple doubt , Arraylist increase its size with factor ( 2,1.5 or old_capacity*3/2 +1 or what ever) as it got full , and add new element in it. Then why dont it decrease it size dynamically if number is removed by some factor. Like if I have 10000 element in arraylist and at particular time all the elements are removed , only 100 elements are their in array list now It still hold 10000 object memory. Why i have to call trimTosize() or something? why it is not their automatically? Did I miss something .. ? Please dont tell me how to do it, I want to know why we have to do it ?? Thanks

umesh
  • 231
  • 1
  • 14

3 Answers3

6

Then why dont it decrease it size dynamically if number is removed by some factor.

For performance reasons. Allocating memory is always an expensive operation. The logic behind not deallocating it, is that if your data structure has reached a given size, even if you remove elements, then it will probably reach that size again in the future.

Deallocating maybe also expensive too(this depends on the implementation but it's generally true. See realloc for C), because you may need to release the whole chunck of previously allocated memory, and then reallocate a new chunck for the resized structure.

Heisenbug
  • 38,762
  • 28
  • 132
  • 190
  • I know you didn't downvote it, what is wrong with the answer http://stackoverflow.com/a/16188893/1115584 ? – AmitG Apr 24 '13 at 10:03
0

Because if you have a list with, say, a million members, and remove one, do you really want to copy 999,999 references to a new array?

Edit: To address a concern in the comments - the problem with having some threshold at which the collection 'automatically' resizes is that it makes performance management difficult.

If I remove an element from an arraylist, I exepct that operation to take a certain amount of time. The 499,999th removal should take a similar amount of time to the 500,000th removal. If I really want to resize a collection at some point I can do that by using the provided method - but then its under my control.

pauljwilliams
  • 19,079
  • 3
  • 51
  • 79
  • can somebody comment for downvote? or can author explain? – AmitG Apr 24 '13 at 09:59
  • I didn't downvote it. I think that he wanted to say more or less what I wrote in my answer. Maybe he should improve a little bit the answer to make it more clear. – Heisenbug Apr 24 '13 at 10:05
  • my doubt was not removing 1 or 2 numbers, but what if it decrease by some factor.. like become 1/2 the size or something.. doesn't it worth it to reallocate.. I know it a open ended question , but we can showcase our facts.. which help people to understand .. – umesh Apr 24 '13 at 10:15
  • it may worth to reallocate in that case for saving space. But like you said exists trimTosize() method to do that. The choice is left to the user. – Heisenbug Apr 24 '13 at 10:20
  • I totally agree with ans given above, but i will make it same ans other way around, " If I add an element from an arraylist, I exepct that operation to take a certain amount of time. The 1,000,000th addition should take a similar amount of time to the 1,000,001th addition." Continue in below comment... – umesh Apr 25 '13 at 08:58
  • but if list is full it try to allocate another 500,000 spaces for just 1 element. So should it will affect time. So if time is the issue, then i think it will hit in addition also , at some point. I am not criticising above ans, I just try to understand y every body is talking about the profit and time performance only in case of allocation , these all profit we can get if we have proper mechanism to find at what level how much list should decrease. M I behaving like stubborn?? but seriously , no body can see the positive side of that ?? – umesh Apr 25 '13 at 08:59
0

If an ArrayList is full and you want to add a new element there is no other way than increasing its size. If you delete entrys and the sizes gets smaller there is no actual need to resize it - leaving it at its size will be the more performant way. Maybe new items will be added soon?

If you want it to become smaller you can still use trimToSize().

Therefore it makes sense to increase its size automatically but it does not to decrease it automatically.

das Keks
  • 3,723
  • 5
  • 35
  • 57