How fast is add method and get method for each child of the List

Question

I am working on my java application and i am concerned about performance speed especially because i have a lot of data structures like List, Map and so on.

I know that complexity of add(Object obj) method of LinkedList is O(1) (the main reason to use LinkedList) and the complexity of get(int index) method of ArrayList is O(1) (the main reason to use ArrayList).

I found the article below on internet :

Try to follow these rules while optimizing ArrayList performance of your code:

Add elements to the end of the list
Remove elements from the end too
Avoid contains, indexOf and remove(Object) methods
Even more avoid removeAll and retainAll methods
Use subList(int, int).clear() idiom to quickly clean a part of the list

Now what i need to know is what does it mean add elements to the end of the list because as far as i am concerned if we do not use index as parameter of the add method so in other words if we use add(Object obj) method then elements are always added to the end.

I have those two methods below and i am wondering if the performance of those methods when we will have 1000 files will be desirable or not . If not is there any way how to improve the performance

I have used profiler like jvm to measure speed performance but i am still not sure if this is the best performance i can achieve or not

public List<int[][]> AllSharesForFiles (int n , int k,List<File> file) {

    sharesHolder = new LinkedList<int[][]>();
    try{    

        for(int i=0;i<file.size();i++) {

            byte[]secret = f.readingTheFile(file.get(i));  // We call the method which read the file

            //method which evaluate the shares of each byte of the file   
            shar1= s.calculateThresholdScheme(secret, n,k,new    RndGeneratorAllAlgorithm(new RandomGeneratorSHA1()),two);

            sharesHolder.add(shar1);
        }

    } catch (IOException e) {

        e.printStackTrace();

    }   

    return sharesHolder;
}

/*Look for the possibilities to return a 2D array instead of one dimensional array
 * 
 */
public List<int[][]> AllSharesForEachFile (int n , int k,List<int [] []> f) {

    sharesHolder1 = new LinkedList<int[][]>();
    int s=f.size();
    int l=f.get(1)[0].length;     

    for (int i = 0; i < n; i++) {

        someValue=new int[s][l];

        for(int j=0;j<f.size(); j++){

            someValue[j]=f.get(j)[i];

        }
        sharesHolder1.add(someValue);
    }



    return sharesHolder1;
}

Reading the files is what could make your code perform slowly. Compare to the IO operations, adding and removing elements from array cost nothing. — Mikhail Chibel, Jun 19 '16 at 22:05
I am done with performance of IO operation so i have optimised it and got the result i wanted. Now i am concerned of add and get method . Is it right that get method for array list and add method for linked list has complexity O(1) or there exists some exceptions? — ENIO MARKU, Jun 19 '16 at 22:08

score 2 · Accepted Answer · edited May 23 '17 at 10:33

2

ArrayList is preferable to LinkedList for the vast majority of use cases. Have a look at this Q&A for a discussion on their performance difference.

In short, ArrayList have amortised complexity of O(1) for add(Object o). They also have the benefit of having a better cache locality since all the items are allocated in a single chunk of memory rather than being scattered all over the heap, which is quite costly since it requires extra indirection.

Said that, it's good that you worry about performance but if all you have to work with is a list of 1000 items you're probably going to see a little difference between the two implementations. Your list is not that big and you're also mixing operations on the list with I/O operations, which are surely going to dominate the execution time of your application.

edited May 23 '17 at 10:33

Community

1
1

answered Jun 19 '16 at 22:12

mariosangiorgio

5,520
4
32
46

So in other words you are telling me that the performance speed of a list of about 1000 items (and i am sure this is the biggest list i can have on my application) is not to worry in terms of data structure methods and what is real concern is IO operation like for instance reading the file – ENIO MARKU Jun 19 '16 at 22:34
1

Agreed about IO dominating the performance of this. However, you can limit any cost of resizing the ArrayList by setting it's initial size. If you know you are getting 1000 files, set the list size to 1000 in the constructor. – AngerClown Jun 19 '16 at 22:45
are you telling that if i use in my code this: sharesHolder = new LinkedList(file.size()); it will improve my performance? – ENIO MARKU Jun 19 '16 at 23:03
@ENIOMARKU For sure not. 0. There's no such constructor. 1. In 99% of cases, the most fruitful optimization for `LinkedList` is replacing it by `ArrayList`. 2. Pre-sizing `ArrayList` helps sometimes, but I'd bet it's not measurable in your case. Just forget it. 3. `file.size()` is too much, unless you need as many elements as there are bytes in the file. 4. Optimization is fun, but measure what you're doing. Optimizing blindly is wasting time. – maaartinus Jun 21 '16 at 02:40

How fast is add method and get method for each child of the List

1 Answers1