7

根据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我的意思是使用forsize>=FILL_THRESHOLD而不是 for有什么显着的性能优势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

4

2 回答 2

3

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

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

这是因为list.set(i, obj)可能会更昂贵，itr.set(obj)但在后者中，您将隐含管理迭代器的开销。由于复杂度可以是线性的O(n)，list.set(i, obj)因此用于更大的列表可能是一个有效的问题。

于 2012-09-05T03:40:32.653 回答
1

Java 1.2 引入了集合框架，Java 1.3 使用了 ListIterator 的直接方法：

public static void fill(List list, Object o) {
    for (ListIterator i = list.listIterator(); i.hasNext(); ) {
        i.next();
        i.set(o);
    }
}

阈值是在 Java 1.4 中与RandomAccess标记接口一起引入的（所有这些都基于 Oracle 网站上的 JDK 遗留代码）。

我认为这是对旧垃圾收集算法的优化——这些旧算法对创建新对象（例如 ListIterator）有相当大的惩罚。因此，对非 O(1) 列表使用 setter 是有意义的。

颇具讽刺意味的是，Java 1.4.1引入了一个新的垃圾收集器，它使得对象创建对于像迭代器这样的短期对象来说更便宜。

于 2012-09-05T05:50:45.207 回答