集合ってすげぇ〜〜〜 Atcoder abc236 C

結論

set()は今まで重複したものを確認するためだけに使ってたけど
処理速度を意識した上でも使える素晴らしい技術なんだなぁって思い知りました！

問題

AtCoder 鉄道のとある路線には N 個の駅が存在し、始点から終点に向かって i(1≤i≤N) 番目の駅の名前は$S_{i}$です。
普通列車は全ての駅に止まりますが、急行列車は全ての駅に止まるとは限りません。
具体的には、急行列車は M(M≤N) 個の駅にのみ止まり、j(1≤j≤M) 番目に止まる駅の名前は$T_{j}$です。
ただし、 $S_{1}$=$T_{1}$ かつ $S_{n}$=$T_{n}$ ​
、すなわち急行列車は始点と終点の両方に止まることが保証されます。
N 個の駅それぞれについて、その駅に急行列車が止まるかどうか判定してください。

俺の回答

C.py

n,m = map(int,input().split())
 
normal_train = list(input().split())
express_train = list(input().split())
 
for i in normal_train :
    ans = 'Yes' if i in express_train else 'No'
    print(ans)
n,m = map(int,input().split())

normal_train = list(input().split())
express_train = list(input().split())

for i in normal_train :
    ans = 'Yes' if i in express_train else 'No'
    print(ans)

C問題にしても簡単すぎひん？ってなりながら提出ボタン押したら
LTEになって「はぁ？？？」ってなった

まぁ処理量考えたら確かに全回しではダメなんかなぁとかよくわからず考えてて、とはいえこれ以外の回答を思いつかなかったので渋々答えを確認

##　解答

n, m = map(int, input().split())
s = input().split()
t = set(input().split())
for x in s:
    print("Yes" if x in t else "No")

?????

ほぼ俺の答えと一緒やんけ！ってなった。
唯一違うところはset()の部分くらい

実際自分のexpress_train = list(input().split())をsetに変えたらLTEにならず速攻処理が終わった。

検証

あんまり意味もよくわかってないので、一旦自分で処理を書いて動かしてみる

extra.py

import time

def check_test_func(s,group) :
    ans = []
    for i in s :
        if i in group :
            ans.append('a')

s = [ i for i in range(100) if i % 2 == 0]

list_t = [ i for i in range(10000000)]
set_t = set([ i for i in range(10000000)])

start = time.time()
check_test_func(s,list_t)
elapsed_time = time.time() - start
print("{:.03} ms in {}".format(elapsed_time * 1000, 'list_t'))

start = time.time()
check_test_func(s,set_t)
elapsed_time = time.time() - start
print("{:.03} ms in {}".format(elapsed_time * 1000, 'set_t'))

結果

0.125 ms in list_t
0.041 ms in set_t

集合って存在判定するの圧倒的に爆速なんやなぁ
理由はわからん

理由調べた

答えはいたってシンプルでPythonのsetはハッシュテーブルで実装されているから。らしい

ハッシュテーブルの俺のイメージは、ハッシュ値をキーにしてバリューを持っている感じ
なのでキー検索を行えるので、listで全探索して検索するより爆速なんだね…

集合は重複排除と論理演算系でしか今まで使ってなかったけど、
これからは探索時に上手いこと使える時があれば使っていくようにします！