50

タイプの複数の反復を実行しています：

masterSet=masterSet.union(setA)

セットが大きくなるにつれて、これらの操作を実行するのにかかる時間も長くなります (予想どおりだと思います)。

setA の各要素がすでに masterSet にあるかどうかを確認するのに時間がかかると思いますか?

私の質問は、masterSet に setA の要素がまだ含まれていないことがわかっている場合、これをより迅速に行うことができるかということです。

[アップデート]

この質問がまだ意見を集めていることを考えると、以下のコメントと回答からいくつかのことを片付けたいと思いました。

反復するとき、それがどのように構築されたか (チェックを処理する必要なし) とは異なることがわかって いる多くの反復がありましたが、いくつかの反復では一意性チェックが必要でした。setAmasterSet

masterSet.union()今回は一意性チェックを気にしないように手順に「伝える」方法があるかどうか疑問に思いました。これはmasterSet、これらの要素が間違いなく明確であるというプログラマーの主張をすぐに信頼してこれらの要素を追加することとは異なることを知っているからです。.unionWithDistinctSet()何らかの別の " " プロシージャまたは何かを呼び出すことによってパスパスが発生します。

masterSet.update(setA)回答は、これは不可能であり（実際には設定操作はとにかく十分に高速である必要があります） 、ユニオンの代わりに使用することを示唆していると思います。

私はそれらの線に沿った最も明確な回答を受け入れ、当時抱えていた問題を解決し、私の人生を続けましたが、私の仮説.unionWithDistinctSet()が存在する可能性があるかどうかを知りたいですか?

4

4 に答える 4

88

を使用set.updateして、マスター セットをその場で更新できます。これにより、常に新しいセットを割り当てる必要がなくなるため、set.union...

>>> s = set(range(3))
>>> s.update(range(4))
>>> s
set([0, 1, 2, 3])

もちろん、これをループで実行している場合:

masterSet = set()
for setA in iterable:
    masterSet = masterSet.union(setA)

次のようなことを行うと、パフォーマンスが向上する場合があります。

masterSet = set().union(*iterable)

最終的に、セットのメンバーシップ テストは O(1) (平均的な場合) であるため、要素が既にセットに含まれているかどうかをテストしても、実際には大きなパフォーマンス ヒットにはなりません。

于 2013-06-05T12:07:10.043 に答える
8

mgilson が指摘しているように、update別のセットからセットをその場で更新するために使用できます。それは実際には少し早くうまくいきます：

def union():
    i = set(range(10000))
    j = set(range(5000, 15000))
    return i.union(j)

def update():
    i = set(range(10000))
    j = set(range(5000, 15000))
    i.update(j)
    return i

timeit.Timer(union).timeit(10000)   # 10.351907968521118
timeit.Timer(update).timeit(10000)  # 8.83384895324707
于 2013-06-05T12:13:38.733 に答える
6

要素が一意であることがわかっている場合、セットが必ずしも最適な構造であるとは限りません。

単純なリストは、拡張がはるかに高速です。

masterList = list(masterSet)
masterList.extend(setA)
于 2013-06-05T12:23:33.913 に答える
1

確かに、__eq__(..)メソッドが非常に高価な場合、このチェックを省略することで大きな節約になる可能性があります。CPython 実装で__eq__(..)は、同じ番号にハッシュされるセット内のすべての要素で呼び出されます。(参考:のソースコードset)

ただし、セットの整合性を侵害する別の方法が開かれるため、この機能は 100 万年以内に存在することはありません。これに伴う問題は、(通常は無視できる) パフォーマンスの向上よりもはるかに重要です。これがパフォーマンスのボトルネックであると判断された場合、C++ 拡張機能を作成し、その STL を使用することは難しく<set>ありません。これにより、1 桁以上高速になるはずです。

于 2015-08-02T14:13:05.827 に答える