CODEWITHSUNDEEP
javaarrayscollectionsarraylist
Hero
Hero

Reputation: 647

Is there any advantage of defining the size of Arraylist while instantiating

Is there any advantage of defining the size of Arraylist while instantiating .?

Please correct me if am wrong or if its a duplicate of possible other questions . I searched but I couldn't find what I was looking for .

Is it an advantage of defining the initial capacity of Arraylist. Its 10 by default I guess.

While resizing the Arraylist will it help if we declare while instantiating . Also how to potentially overcome the overhead of resizing of Arraylist internally.?

Upvotes: 5

Views: 2800

Answers (3)

Kyle
Kyle

Reputation: 4298

ArrayLists use arrays internally, so when an ArrayList needs additional capacity, it has to create a new array internally and copy the elements over to the new array.

You can overcome the overhead of resizing the ArrayList by estimating or finding the exact size of the ArrayList beforehand. Alternatively, you can make sure the ArrayList never grows beyond a specified size by handling your business logic and then removing elements whenever your ArrayList is at its maximum desired size. Finally, you can use a different data structure that does not use arrays internally to avoid your growth problem altogether.

Upvotes: 6

hyde
hyde

Reputation: 62906

Specifying initial capacity for ArrayList can and will improve performance if used right. If used wrong, it can hurt performance.

It is worth doing for example, if you are creating new ArrayList instances in a loop and know how to calculate the real final size, or a reasonable starting size.

But usually it is either not worth it, or even harmful:

  • If you allocate too much "defensively", memory use and initialization cost can be more than cost of resizes with default size.
  • If code evolves and ideal list size changes, but you forget to adjust the custom initial capacity, then optimisation can become pessimization.
  • The time you spend on micro-optimization like this is usually better spent on something else.
  • The average cost is constant per appended element: because size doubles, each element in the list has on average been moved just once (right before resize) or twice (right after resize). Usually processing the objects put to the list is many times more costly, so overall impact of resize is irrelevant.

For the uses where indexable array is a good option, ArrayList is basically as good as it gets.

LinkedList in particular may seem better for some cases, but it's not! It has bigger memory overhead (extra allocation per list item!), and as a result worse performance on average even for cases where it's supposedly efficient, and even LinkedList insert at end is not guaranteed O(1) in Java, because GC may kick in at allocation. It is good fit only for very special cases, such as some concurrent algorithms.

One optimization is sometimes possible: If you have ArrayList of boxed primitive type (like ArrayList<Integer>), consider using primitive type array (like int[]). This does not actually overcome the resize issue, but it avoids the overhead of the boxed instances. But this only applies to primitive types, not for example Strings.

You can also create custom List if you can live with some extra restrictions you can take advantage of. For example, if you are willing to increase access time (from direct index access to one extra lookup) and only need to insert or remove at the ends, you can create a custom List implementation which is internally ArrayList of plain arrays. So when you insert, and an internal array fills, you create a new array and insert there, instead of reallocating the old array. But due to the overhead of two-level structure, this is rarely an overall improvement, and would more realistically be an alternative to using a LinkedList (which, again, is right choice very rarely).

So in general, if ArrayList resize is problem, best cure to that is to get beefier computer ;). Another solution is to improve the overall algorithm, or in general improve performance otherwise (because the total performance is what matters, not isolated performance of some small detail).

It's interesting how this has actually changed from the "olden days" of computing. With interactive applications, you want some operations to happen within some real world time limit, so user experience does not suffer. With slower computers, array list resize would be too time-consuming at quite a small list size.

But CPU and memory performance have improved faster than typical list item counts, so something like one-time resize of a million element list is no problem: it's moving mere 4/8 megabytes when memory access speeds are measured in gigabytes per second.

Also, multi-threading has become more common, and worst-case response time of non-interactive threads doesn't really matter, it's more about overall throughput, as long as UI thread stays snappy. So if you are handling large data like that, it is often better to move data handling elsewhere (another thread, a real database) than try to optimize list operations in the UI thread.

Upvotes: 3

Andy Thomas
Andy Thomas

Reputation: 86509

If you know the capacity you need, providing it up front could improve performance. Otherwise, as you add elements, the list implementation might need to copy the internal array to one of larger size -- possibly repeatedly.

Upvotes: 7

Related Questions