For loop instead while loop in Collections

user_3448171 0
Viewed 126

I've got a questions about Collections.class and "copy" method.

1) Why we are checking size of a source list in second if conditional on below code and why it is must be less than 10? Why is it so important?

2) What is more, why we are using for loop in this conditional instead while - while (hasNext())

public static <T> void copy(List<? super T> dest, List<? extends T> src) {
    int srcSize = src.size();
    if (srcSize > dest.size()) {
        throw new IndexOutOfBoundsException("Source does not fit in dest");
    } else {
        if (srcSize < 10 || src instanceof RandomAccess && dest instanceof RandomAccess) {
            for (int i = 0; i < srcSize; ++i) {
                dest.set(i, src.get(i));
            }
        } else {
            ListIterator<? super T> di = dest.listIterator();
            ListIterator<? extends T> si = src.listIterator();

            for (int i = 0; i < srcSize; ++i) {
                di.next();
                di.set(si.next());
            }
        }
    }
}

Why we are using

collections java
3 Answers

1) 10 is a constant that represents a cut-off between small lists and larger lists. If a List doesn't support random access (which means it doesn't support O(1) time for list.get(i)), get(i) could be expensive, so you only want to use it if the list is small. LinkedList is an example of a List that doesn't support random access.

2) Both for and while loops are possible, but when the Lists support random access (or are small enough), it might be more efficient to use get and set instead of creating iterators.

user_12215710

The comment above some of the constants gives a good insight here

Many of the List algorithms have two implementations, one of which is appropriate for RandomAccess lists, the other for "sequential." Often, the random access variant yields better performance on small sequential access lists. The tuning parameters below determine the cutoff point for what constitutes a "small" sequential access list for each algorithm. The values below were empirically determined to work well for LinkedList. Hopefully they should be reasonable for other sequential access List implementations. Those doing performance work on this code would do well to validate the values of these parameters from time to time.

The bit I've bolded is particularly relevant, I think. 10 as the threshold is not arbitrary, they came to it via a series of measurements and observations, just as all good performance optimisations should be. What is considered a "small" list also differs based on the context.

user_18985630

2) What is more, why we are using for loop in this conditional instead while - while (hasNext())

I'm assuming that this question refers to the last for-loop in the quoted code, the one that loops over the iterators:

        ListIterator<? super T> di = dest.listIterator();
        ListIterator<? extends T> si = src.listIterator();

        for (int i = 0; i < srcSize; ++i) {
            di.next();
            di.set(si.next());
        }

Most conventional iterator loops look something like this:

            Iterator<T> it = src.iterator();
            while (it.hasNext()) {
                T t = it.next();
                // process t
            }

This code doesn't do that. Indeed, it doesn't call hasNext() at all on either iterator, which is pretty unusual. (The iterators are instances of ListIterator instead of Iterator because of the need to call the set() method. Use of a ListIterator is irrelevant to the question of loop control, which applies to Iterator as well.)

The reason that hasNext() isn't called in the loop is that the code already knows the sizes of the collection. It knows the number of elements to be copied, which is srcSize. It's already checked the destination size to make sure it's sufficiently large to receive all the elements. Thus, the loop can call si.next() and di.next() up to srcSize times without having to call any hasNext() methods. The only way that a next() call could fail is if one of the collection's iterators is implemented incorrectly.

(The loop could also fail if one of the lists changes size concurrently. Hmmm. This code clearly assumes that the neither list's size changes during the iteration.)

Under the assumption that the lists' sizes don't change, there's no reason to call any hasNext() methods. Since the number of elements to be copied is known, a counted for-loop can be used, and it's more efficient because it avoids any method calls as part of the loop control logic. That is, i < srcSize and ++i are compiled in-line compared to something like while (si.hasNext()) which of course requires a method call.

user_14411220
Related