14

最近、いくつかの Java コレクションが size() メソッドの一定時間操作を持たないという事実に驚いています。

コレクションの同時実装では、同時実行性 (ConcurrentLinkedQueue、ConcurrentSkipListSet、LinkedTransferQueue などのサイズは O(n)) のトレードオフとしていくつかの妥協点があることを知りましたが、これは API ドキュメントで適切に文書化されています。

私が気になったのは、一部のコレクションのメソッドによって返されるビューのメソッド サイズのパフォーマンスです。たとえば、TreeSet.tailSetは、要素が fromElement 以上のバッキング セットの部分のビューを返します。私が非常に驚いたのは、返された SortedSet の size の呼び出しが時間的に線形であること、つまり O(n) だということです。少なくともそれは、OpenJDK のソース コードから掘り出すことができたものです。 TreeSet では、TreeMap のラッパーとして実装され、TreeMap 内には、サイズ メソッドが次のような EntrySetView クラスがあります。

abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
    private transient int size = -1, sizeModCount;

    public int size() {
        if (fromStart && toEnd)
            return m.size();
        if (size == -1 || sizeModCount != m.modCount) {
            sizeModCount = m.modCount;
            size = 0;
            Iterator i = iterator();
            while (i.hasNext()) {
                size++;
                i.next();
            }
        }
        return size;
    }

    ....
}

これは、サイズが最初に呼び出されるのは O(n) であり、バッキング マップが変更されない限りキャッシュされることを意味します。API ドキュメントでこの事実を見つけることができませんでした。より効率的な実装は、サブツリー サイズのキャッシュでメモリのトレードオフを伴う O(log n) です。このようなトレードオフはコードの重複 (TreeMap のラッパーとしての TreeSet) を回避するために行われているため、パフォーマンス上の理由からそれらを行うべきではない理由がわかりません。

TreeSet の OpenJDK 実装の私の (非常に簡単な) 分析が正しいか間違っているかは無視して、そのような多くの操作、特に完全に予想外の操作のパフォーマンスに関する詳細で完全なドキュメントがあることを知りたいですか?

4

1 に答える 1

3

たとえば、TreeSet.tailSet要素が より大きいか等しいバッキング セットの部分のビューを返しますfromElement。私が非常に驚いたのは、size返されたの呼び出しSortedSetが時間的に線形であること、つまりO(n).

私にとって、それは驚くべきことではありません。javadoc の次の文を検討してください。

「返されたセットはこのセットによってサポートされているため、返されたセットの変更はこのセットに反映され、その逆も同様です。」

テール セットはバッキング セットの動的ビューであるため、実際にはそのサイズを動的に計算する必要があります。別の方法では、バッキング セットに変更が加えられたときに、現存するすべてのテールセット (およびヘッドセット) ビューのサイズを調整する必要があります。これにより、バッキング セットの更新のコストが高くなり、ストレージ管理の問題が発生します。(ビューのサイズを更新するために、バッキング セットはすべての既存のビュー セットへの参照を必要とします。これは潜在的な隠しメモリ リークです。)

これで、ドキュメントに関するポイントが得られました。しかし実際には、javadocs はビュー コレクションの複雑さについて何も述べていません。そして、実際、それTreeSet.size()がO(1)!であることさえ文書化していません。実際には、add、 、removeおよびcontains操作の複雑さのみを説明しています。

そのような多くの操作、特に完全に予期しない操作のパフォーマンスに関する詳細で完全なドキュメントがあることを知りたいですか?

私の知る限り、いいえ。確かに、Sun / Oracleからではありません...

于 2013-03-29T13:16:07.257 に答える