Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

For loop instead while loop in Collections

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

like image 821
Janek Avatar asked Jan 01 '23 11:01

Janek


2 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.

like image 139
Eran Avatar answered Jan 05 '23 16:01

Eran


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.

like image 26
Michael Avatar answered Jan 05 '23 14:01

Michael