16

奇妙なことに、デフォルトの JDK 6 実装はAbstractList::equals() 、2 つのリストが同じサイズであるかどうかを最初にチェックしないようです。

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;
    ListIterator<E> e1 = listIterator();
    ListIterator e2 = ((List) o).listIterator();
    while(e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

両方のリストに多数のアイテムが含まれている場合、またはアイテムの比較に時間がかかる場合、一方のリストが他方よりも短いことに気付く前に、それらすべてを比較します。これは、compare を 1 つも呼び出さずに等式を作成できた可能性があるため、非常に効率が悪いように思えます。

特に、多くの場合、リストのサイズはほとんどの場合異なります。さらに、ほとんどの JavaList実装は O(1)size()パフォーマンスを備えています (サイズをキャッシュに保持する LinkedList でさえも)。

このデフォルトの実装には正当な理由がありますか?

4

1 に答える 1

12

equals メソッドの操作は詳細に指定されており、O(n) の動作が必要です。これは、サイズ メソッドが O(1) であるサブクラスでは最適ではないかもしれませんが、一部のサブクラスでは、サイズ メソッド自体が O(n) であり、要求された動作は実際には低下します。いずれにせよ、仕様は明確であり、この変更を行うことはできません。

サブクラスは必要に応じて equals をオーバーライドし、必要に応じてサイズ比較を挿入できることに注意してください。

参照。

于 2013-09-23T11:32:48.790 に答える