(Python,競技プログラミング) setを用いたコードのTLEの理由をご教示ください。

Question

前提

競技プログラミング(AtCoder)にて、なぜTLEが発生するのか分からないため質問させていただきます。
AtCoder Beginner Contest 299E問題(リンク)を解いていました。
提出コードがTLEするためコードテストをしていると、どうやら以下の配列distanceを作成する過程で時間がかかっているようでした。
配列distanceは、全ての頂点を始点として幅優先探索を行うことでdistance[i][j] = 地点iからの最短距離がjとなる地点の集合となる配列です。
distance[i][j]の中身をlistにし、追加前に存在確認をすることで重複を無くすようにするとパフォーマンスが改善することからsetの影響で時間が掛かっているのかなとは思うのですが、具体的な原因がはっきりしません。
もしよろしければ、どのような原因で時間が掛かっているのかご教示いただければ幸いです。

該当のソースコード

import collections

# 入力
N,M = map(int,input().split())

# グラフ生成
graph = {i:[] for i in range(1,(N+1))}
for _ in range(M):
    u,v, = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

# distance[i][j] = 地点iからの最短距離がjとなる地点のset
distance = [ collections.defaultdict() for _ in range(N+1) ]

# 全ての頂点を始点としてBFS
for i in range(1,N+1):
    queue = collections.deque()
    ans = [-1]*(N+1)
    distance[i][0] = {i}
    queue.append(i)
    ans[i] = 0
    while queue:
        q = queue.popleft()

        if not graph[q]:
            continue
        for x in graph[q]:
            if ans[x] == -1:
                queue.append(x)
                ans[x] = ans[q]+1
                if ans[x] in distance[i]:
                    distance[i][ans[x]].add(x)
                else:
                    distance[i][ans[x]] = {x}

試したこと

テストケース(リンク)をコードテストした結果が以下になります。
PyPy3:実行時間 2065 ms, メモリ 893200 KB
Python: 実行時間 8713 ms, メモリ 870412 KB

Answer 1

distanceで保持しなければならないsetの数が多すぎるのが原因だと思われます。

リンクされたテストケースは、2000個の頂点を一直線上に並べた構造になっています。
そうなると、distanceの要素数は2000、distanceの各要素の要素数は1000-1999(平均1500程度)なので、distance内に含まれるsetの総数は、300万程度になります。

ここまで数が多いと、それぞれの要素がsetかlistかという些細な差でも、パフォーマンスへの影響は大きくなります。

Comments

[taryo]

ご回答いただきありがとうございます。
下記のようなコードを用意して、'distance[i]=set()'の部分を'= []', '=[i]', '=set()', '= {i}'の4種試してみたところ、順に約1000ms,1300ms,1000ms,2000msといった実行時間でした。
要素入りのsetを多く持つとlistに比べてやや重たくなってしまうのですね…
大変勉強になりました。ありがとうございました。
'''
distance = dict()
for i in range(1,2000*2000):
　　　distance[i] = set()
'''