java - 为什么java中Collections的fill(),copy(),reverse(),shuffle()是这样实现的

Question

根据javadoc... Collections.fill() 写成如下:

public static <T> void fill(List<? super T> list, T obj) {
        int size = list.size();

        if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
            for (int i=0; i<size; i++)
                list.set(i, obj);
        } else {
            ListIterator<? super T> itr = list.listIterator();
            for (int i=0; i<size; i++) {
                itr.next();
                itr.set(obj);
            }
        }
    }

很容易理解为什么他们不使用 listIterator

if (size < FILL_THRESHOLD || list instanceof RandomAccess) 

截至 RandomAccess 的条件。但是size < FILL_THRESHOLD有什么用呢？在上面？

我的意思是，与使用 iterator 相比，是否有显着的性能优势？对于 size>=FILL_THRESHOLD而不是 size < FILL_THRESHOLD ？

我也看到了 Collections.copy() 的相同方法:

 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");

        if (srcSize < COPY_THRESHOLD ||
            (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());
            }
        }
    }

仅供引用:

 private static final int FILL_THRESHOLD           =   25;

 private static final int COPY_THRESHOLD           =   10;

以下相同的方法:

 public static void reverse(List<?> list)
 public static void shuffle(List<?> list, Random rnd) 

编辑:

我的困惑是 size<FILL_THRESHOLD部分，不适用于 RandomAccess

Answer 1

我想这是因为通用列表并不意味着是 ArrayList。不能保证设置随机索引在常数 O(1) 时间内完成。同时构建迭代器并对其进行处理有其开销。

总而言之，对于小型列表，您可以通过节省创建迭代器本身的开销来牺牲这样一个事实，即使用迭代器可以降低访问连续元素的复杂性。

这是因为 list.set(i, obj) 可能比 itr.set(obj) 更昂贵，但在后者中你会隐含管理迭代器。由于复杂性可以是线性的 O(n)，因此对较大的列表使用 list.set(i, obj) 可能实际上是一个问题。