I was wondering what the performance impact would be when using ArrayList.ListIterator(int index - 1), then it.next() in contrast to using ArrayList.get(int index)?
3 Answers
Why look at the implementations...
1: List.listIterator(int)
public ListIterator<E> listIterator(final int index) {
if (index<0 || index>size())
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
with
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
// [...]
and
public E next() {
checkForComodification();
try {
E next = get(cursor);
lastRet = cursor++;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
2: List.get(int)
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
Should be quite obvious, which one is faster. For details about performance impacts, I will have to agree with Mike. Profile it. Whatever the reason is, you'd like to use such a distinct access method just to access one item (?)
1 Comment
Unrealomega
It was more about curiosity than anything. Thanks though.
Profiled it on my machine, with an ArrayList of 10,000 integers.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
/**
*
* @author Michael Drogalis
*/
public class Launcher {
public static void main(final String[] args) {
List<Integer> sut = new ArrayList<Integer>();
Random generator = new Random();
for (int k = 0; k < 100000; k++) {
sut.add(generator.nextInt(64));
}
testGetMethod(sut, generator);
testIteratorMethod(sut, generator);
}
private static void testGetMethod(List<Integer> aList, Random aGenerator) {
for (int k = 0; k < 100000; k++) {
aList.get(aGenerator.nextInt(1000));
}
}
private static void testIteratorMethod(List<Integer> aList, Random aGenerator) {
for (int k = 0; k < 100000; k++) {
Iterator iterator = aList.listIterator(Math.abs(aGenerator.nextInt(100000) - 1));
iterator.next();
}
}
}
The get method took 6.47 ms to complete 10,000 fetches.
The Iterator style took 18.7 ms to completely 10,000 fetches.
They differ by a factor of nearly 3.
Edit:
Profiled each method 1,000 times. Here are some particularly interesting results:
get takes 2403 ms.
Iterator takes 3,661 ms.
Now it's a factor of 1.5. Interesting...
Reasonable results - for my machine. Test at your own risk.
4 Comments
Stan Kurilin
Hm.. I think it will be better if you will generate indexes before test and then use it for both method's tests.
Mike
Since it's a random access data structure, should it even matter?
Stan Kurilin
nextInt rather long operation. So it can have an influence on "factor"(it's only suggestion). In this case you can do some reasonable correction on your coefficient.
Mike
@Stas Kurilin Your point is interesting. However, in both retrievals I used nextInt(), so the drag factor is applied equally to both. That is, assuming that number a will never take longer than number b to generate.
Both find the result in O(1) (iaw - time does not depend on size of list). So if you just use it once, you won't notice a difference on small or big collections.
But the "ListIterator" solution creates extra objects and that is a waste of memory, because we have the get method that just takes the requested object from the backing array.
Comments
AbstractList.listIterator(int)compared toArrayList.get(int)