python - Pythonで2つのセットが等しいかどうかをチェックする時間の複雑さ

Question

この質問を読んで、Pythonが次のような式を評価するのに（漸近的に言えば）どれくらいの時間がかかるのだろうと思いました

{1,2}=={2,1}

つまり、セット クラスの 2 つのインスタンスが等しいかどうかを確認します。

Answer 1

セット間の比較は、1848 行の関数によって実装されますset_richcomparesetobject.c。等式が次のように実装されていることがわかります。

1. セットのサイズが同じでない場合は、false を返します。

2. 両方のセットがハッシュされていて、ハッシュが異なる場合は、false を返します。

3. コールしset_issubsetます。

2 つのセットのサブセット テストは次のようになります。

while (set_next(so, &pos, &entry)) {
    int rv = set_contains_entry((PySetObject *)other, entry);
    if (rv == -1)
        return NULL;
    if (!rv)
        Py_RETURN_FALSE;
}
Py_RETURN_TRUE;

最初のセットのすべての要素を反復処理してから、他のセットの各要素を検索することで機能することがわかります。そのため (多くのハッシュ衝突がない限り)、これは最初のセットのサイズに比例します。