Is duplicating an ArrayList or using a ListIterator faster when trying to manipulate an ArrayList?

Question

I have multiple ArrayLists with lots of data and I need to manipulate the data quickly and efficiently. My code currently makes a duplicate of the original ArrayList so that I can make changes (avoiding ConcurrentModificationException). This approach seems somewhat inefficient.

I've looked into ListIterators and they seem much more "clean" and efficient. I ran a quick test to see which is actually faster and it seems duplicating the original ArrayList may be faster. Is this true or is my test flawed in some way? If it is true, does it only hold for smaller ArrayLists?

The test I ran is below:

long startTime, stopTime;

ArrayList<ArrayList<String>> array = new ArrayList<>();

ArrayList<String> a1 = new ArrayList<>();
ArrayList<String> a2 = new ArrayList<>();
ArrayList<String> a3 = new ArrayList<>();

for (int i = 0; i < 5; i++) {
    a1.add(Integer.toString(i));
    a2.add(Integer.toString(i));
    a3.add(Integer.toString(i));
}

array.add(a1);
array.add(a2);
array.add(a3);

startTime = System.nanoTime();

ArrayList<ArrayList<String>> arrayCopy = new ArrayList<>();
for (int i = 0; i < array.size(); i++) {
    ArrayList<String> line = array.get(i);
    arrayCopy.add(i, new ArrayList<>(line.size()));
    for (int j = 0; j < line.size(); j++) {
        arrayCopy.get(i).add(j, line.get(j));
    }
}

for (int j = 0; j < array.size(); j++) {
    for (int i = 0; i < array.get(j).size(); i++) {
        if (array.get(j).get(i).equals("2")) {
            arrayCopy.get(j).add(i, "1.5");
        }
    }
}

stopTime = System.nanoTime() - startTime;

System.out.println(arrayCopy.get(0));
System.out.println(arrayCopy.get(1));
System.out.println(arrayCopy.get(2));

System.out.println(stopTime);

ArrayList<ArrayList<String>> brray = new ArrayList<>();

ArrayList<String> b1 = new ArrayList<>();
ArrayList<String> b2 = new ArrayList<>();
ArrayList<String> b3 = new ArrayList<>();

for (int i = 0; i < 5; i++) {
    b1.add(Integer.toString(i));
    b2.add(Integer.toString(i));
    b3.add(Integer.toString(i));
}

brray.add(b1);
brray.add(b2);
brray.add(b3);

startTime = System.nanoTime();
for (ArrayList<String> s : brray) {
    ListIterator<String> i = s.listIterator();
    while (i.hasNext()) {
        if (i.next().equals("1")) {
            i.add("1.5");
        }
    }
}

stopTime = System.nanoTime() - startTime;

System.out.println(b1);
System.out.println(b2);
System.out.println(b3);

System.out.println(stopTime);

Running the code five times gave me times (in nano seconds) of 73307, 46916, 77705, 76606 and 82470 for the duplicating method and 307888, 319984, 304590, 363235 and 280032 for the ListIterator method.

Where is the original data coming from? Do you do any type of parsing? You could make the "copies" and do some "manipulation" while you loop through and initialize your initial array. — gonzo, Dec 01 '15 at 16:04
http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — assylias, Dec 01 '15 at 16:04
One difference would be that if you add an element via the list iterator you'll iterate over that as well, i.e. you have 6 instead of 5 iterations. — Thomas, Dec 01 '15 at 16:07
@gonzo Yeah I do some parsing but it's minimal. I could create another ArrayList when I'm doing that but it'll simply reduce to another add method call. — user2929779, Dec 01 '15 at 16:10

score 1 · Accepted Answer · answered Dec 01 '15 at 16:41

1

I'm not sure without looking at their implementation but from some tests:

For larger sizes, ListIterator will beat out ArrayList method.

For smaller sizes, just creating the ListIterator takes longer than the ArrayList method.

Also, time benchmarks are kind of questionable, because there is a lot more to it than just the program itself. Especially those in the 10^(-3) seconds.

answered Dec 01 '15 at 16:41

Brendan

303
1
6

Yeah I code a ListIterator approach for my situation and the difference is quite noticeable. With my small test up ahead, creating the ListIterator was what caused it to take so long. – user2929779 Dec 01 '15 at 18:31

score 0 · Answer 2 · answered Dec 01 '15 at 17:08

Take a look in to ArrayList implementation. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.add%28java.lang.Object%29

You need much more items to make a good test. The ArrayList uses array inside and creates by default an array of 10 item. So your add/get etc. methodes have a complexity of O(1). You can look into listIterator method. It use the same approach. I guess, you don't need to use iterator when you use ArrayList explicitly but when you use List interface, because the implementation can be different.

Is duplicating an ArrayList or using a ListIterator faster when trying to manipulate an ArrayList?

2 Answers2