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、上記の使用は何ですか？

iteratorforsize>=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 の Web サイトの JDK のレガシー コードに基づいています)。

これは古いガベージ コレクション アルゴリズムの最適化だと思います。これらの古いアルゴリズムには、新しいオブジェクト(ListIterator など)を作成するためのかなり重いペナルティがありました。したがって、非 O(1) リストにセッターを使用することは理にかなっています。

むしろ皮肉なことに、Java 1.4.1は新しいガベージ コレクターを導入しました。これにより、イテレーターなどの存続期間の短いオブジェクトのオブジェクト作成が大幅に安価になりました。

于 2012-09-05T05:50:45.207 に答える