はじめに
AtCoderのABC329のF問題を解いていて、
pythonのsetは、
小さい方（lengthが小さいset）を大きい方（lengthが大きいset）に
代入するようにupdateする方が実行速度が速いことを初めて知り、
本当にそうなのか？
と疑問に思ったので、調べてみました。
本当に代入する方向で計算量が変わるのか
実行時間を比較するために、以下のようなpythonファイルを作ってみました。
# set の作成
set_long = {i+10 for i in range(1, 10000001)}
set_short = {i for i in range(1, 11)}
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)
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メソッドの仕組みをぜひ教えていただけると幸いです。