はじめに

pythonのsetは、
小さい方（lengthが小さいset）を大きい方（lengthが大きいset）に
代入するようにupdateする方が実行速度が速いことを初めて知り、

本当にそうなのか？

と疑問に思ったので、調べてみました。

本当に代入する方向で計算量が変わるのか

実行時間を比較するために、以下のようなpythonファイルを作ってみました。

set_set.py

# set の作成
set_long = {i+10 for i in range(1, 10000001)}
set_short = {i for i in range(1, 11)}

short2long_update_set.py

set_long = {i+10 for i in range(1, 10000001)}
set_short = {i for i in range(1, 11)}

# 大きいsetに小さいsetを代入する
set_long.update(set_short)

long2short_update_set.py

set_long = {i+10 for i in range(1, 10000001)}
set_short = {i for i in range(1, 11)}

# 小さいsetに大きいsetを代入する
set_short.update(set_long)

まずは、setを作るのにどれくらい時間がかかるのかを測ります。

ターミナル

$ time python3 set_set.py 
python3 set_set.py  0.38s user 0.24s system 77% cpu 0.794 total

次に、set_long（大きいset）にset_short（小さいset）を代入するときの時間を測ります。

ターミナル

$ time python3 short2long_update_set.py
python3 short2long_update_set.py  0.38s user 0.24s system 75% cpu 0.820 total

これを見ると、setを作るのにかかる時間とほとんど変わらない時間でupdateできていることが分かります。
つまり、代入の処理にはほとんど時間がかかっていないと言えます。

さらに、set_short（小さいset）にset_long（大きいset）を代入するときの時間を測ります。

ターミナル

$ time python3 long2short_update_set.py
python3 long2short_update_set.py  0.54s user 0.77s system 66% cpu 1.989 total

これを見ると、set_longにset_shortを代入するときより、実行にかなり長い時間がかかっていることが分かります。

以上から、

大きい方（lengthが大きいset）を小さい方（lengthが小さいset）に
代入するようにupdateするより、

小さい方（lengthが小さいset）を大きい方（lengthが大きいset）に
代入するようにupdateする方が、

実行速度が速いことが確認できました。

どうして実行速度がこんなにも違うのか疑問に感じたのですが、
pythonのドキュメントを読んでもいまいち分からず...。

updateメソッドは、元のsetに代入したい要素を一つずつaddしている？と考えると、
なんとなくイメージできそうです。

詳しい方がいれば、updateメソッドの仕組みをぜひ教えていただけると幸いです。