はじめに
- この記事は、以下の問題の復習記事です
- AtCoder 218_d Rectangle
- いつもの感覚でListで処理したらTLE、解説ACでSetで処理したら通るので、どのくらい違うのか疑問に思って調べました。
ACのソースコード
- https://atcoder.jp/contests/abc218/submissions/25830932
- Setで実装するとAC
- いつもだとListでやりがち
- ○：p = set([tuple(input().split()) for _ in range(N)])
- ×：p = [(input().split()) for i in range(2000)]
テスト用データセットと計測の条件
- 以下の２パターンとする
- Set ○：p = set([tuple(i, i) for i in range(2000)])
- List ×：p = [(i, i) for i in range(2000)]
- テストデータセットとしては、単純に,(i,i)の点を2000個用意する
- 計測は、2点を選んで、他の２点を探索する部分だけを計測。（SetとListの入力部分を含まない）
計測結果
Setでの実行結果
- elapsed_time:0.4602658748626709[sec]
- elapsed_time:0.46323299407958984[sec]
- elapsed_time:0.5020439624786377[sec]
Listでの実行結果
- elapsed_time:210.26401782035828[sec]
- elapsed_time:225.0454020500183[sec]
- elapsed_time:206.4326469898224[sec]
結論
- こりゃListでTLEしたわけだ
- ポイントは以下の記事が参考になりました。inの処理が、ListだとO(N)、SetだとO(1)なのですね。勉強になりました。