0

I am writting a program in java for my application and i am concerned about speed performance . I have done some benchmarking test and it seems to me the speed is not good enough. I think it has to do with add ang get method of the arraylist since when i use jvm and press snapshot it tells me that it takes more seconds add and get method of arraylist.

I have read some years ago when i tool OCPJP test that if you want to have a lot of add and delete use LinkedList but if you want fast iteration use ArrayList. In other words use ArrayList when you will use get method and LinkedList when you will use add method and i have done that .

I am not sure anymore if this is right or not?!

I would like anybody to give me an advise if i have to stick with that or is there any other way how can i improve my performance.

Barlet South
  • 17
  • 1
  • 4

1 Answers1

0

I think it has to do with add ang get method of the arraylist since when i use jvm and press snapshot it tells me that it takes more seconds add and get method of arraylist

It sounds like you have used a profiler to check what the actual issues are -- that's the first place to start! Are you able to post the results of the analysis that might, perhaps, hint at the calling context? The speed of some operations differ between the two implementations as summarized in other questions. If the calls you see are really called from another method in the List implementation, you might be chasing the wrong thing (i.e. calling insert frequently near one end of an ArrayList that can cause terrible performance).

In general performance will depend on the implementation, but when running benchmarks myself with real-world conditions I have found that ArrayList-s generally fit my use case better if able to size them appropriately on creation.

LinkedList may or may not keep a pool of pre-allocated memory for new nodes, but once the pool is empty (if present at all) it will have to go allocate more -- an expensive operation relative to CPU speed! That said, it only has to allocate at least enough space for one node and then tack it onto the tail; no copies of any of the data are made.

An ArrayList exposes the part of its implementation that pre-allocates more space than actually required for the underlying array, growing it as elements are added. If you initialize an ArrayList, it defaults to an internal array size of 10 elements. The catch is that when the list outgrows that initially-allocated size, it must go allocate a contiguous block of memory large enough for the old and the new elements and then copy the elements from the old array into the new one.

In short, if you:

  • use ArrayList
  • do not specify an initial capacity that guarantees all items fit
  • proceed to grow the list far beyond its original capacity

you will incur a lot of overhead when copying items. If that is the problem, over the long run that cost should be amortized across the lack of future re-sizing ... unless, of course, you repeat the whole process with a new list rather than re-using the original that has now grown in size.

As for iteration, an array is composed of a contiguous chunk of memory. Since many items may be adjacent, fetches of data from main memory can end up being much faster than the nodes in a LinkedList that could be scattered all over depending on how things get laid out in memory. I'd strongly suggest trusting the numbers of the profiler using the different implementations and tracking down what might be going on.

Community
  • 1
  • 1
Del
  • 397
  • 2
  • 9
  • Hi, i am using add method only for adding files in a List. Then i do some calculation for eacj file and i get each file by using get method and then save it into a new arraylist. So basicslly i have two methods . One for adding all files and this method return a linkedlist and another one for performing operation over files. But in this method i need to get files from previous method so here i use get and this method return an arraylist which each element of this arrsylist is a 2D arraylist which hold operation for each file. I am not sure if i have to go with data structure – Barlet South Jun 19 '16 at 21:11
  • Just to make sure I understand ...first method returns `LinkedList`, and second method calls `get(i)` in a loop on that `LinkedList`? If so, that's your problem. the `get(i)` method is slow on a `LinkedList` because it must traverse **all** intermediate nodes to get to the _i_th item -- 1 for the first, 1st -> 2nd for the second ... across the whole list, this is O(n^2), or for N items in the list it takes N*N time (sum[1..n] => n^2). An `ArrayList` just computes an offset for O(1) (constant-time) access. You can/will learn this type of analysis in a Data Structures class. – Del Jun 19 '16 at 21:41
  • For a fix, consider using an `Iterator` to iterate over the `List` ... that's almost always what you want unless you explicitly use `ArrayList`. An `Iterator` is used with the "enhanced for loop" - `for (File f : myFileList) { ... }` – Del Jun 19 '16 at 21:45
  • No for get(i) i am using ArrayList not LinkedList. What i want really to understand is add(Object obj) of the arraylist has complexity O(1) or O(n) because i have read different articles and they said add method of arraylist has O(1) complexity amortized but i do not understand what does it mean amortized here – Barlet South Jun 19 '16 at 23:41
  • "amortized" means that in the long run, as the list is used it's O(1). The reason is that the list does not need to get resized if it does not grow. But for the single insertion that triggers a growth of the list, the cost is O(n) because every element must be touched in order to perform a full copy into a newly-allocated array. – Del Jun 20 '16 at 02:21