Python / countとCounterの処理速度の違いとは？ (ABC194 C問題より)

Question

#問題
AtCoder 194 Beginners Contest C問題より：

この問題で、各項の絶対値が200以下ということを利用して、-200 < i < j < 200となる (i, j) を用いた二重ループを組み、与えられた数列中のiとjの数の積に (i - j)**2 を掛けて足し合わせるという方法を取りました。最初にトライしたのが以下のコードです：

N = int(input())

X = list(map(int, input().split()))

ans = 0
for i in range(-200, 201):
	for j in range(i + 1, 201):
		ans += X.count(i) * X.count(j) * (i - j) ** 2

print(ans)

これだと、処理自体は上手くいくものの、2206msの実行時間を要し、タイムオーバーとなってしまいました。

次に、.count()メソッドが時間を食っているのではないかと推測し、Collections より Counter を用いることにしました。以下がそのコードです：

from collections import Counter

N = int(input())

X = list(map(int, input().split()))

cnt = Counter(X)

ans = 0
for i in range(-200, 201):
	for j in range(i + 1, 201):
		ans += cnt[i] * cnt[j] * (i - j) ** 2

print(ans)

この場合、実行時間は163msと、圧倒的に早くなりました。

#質問
①以上のようなケースの場合、countとCounterの両メソッドにおけるそれぞれの処理の所要時間差が、どういった違いに起因するのでしょうか？

②2つ目のコードについて、最初 cnt = Counter(X) を指定しないで、forループ中に直接 ans += Counter(X)[i] * Counter(Y)[j] * (i - j) ** 2 のようにしていたのですが、こうすると処理は1つ目のコードと同様に非常に遅くなりました。上のトライの結果を参考にすると、Counterの処理速度は非常に速いものと思われましたが、それでもループの中に組み込んでしまうとやはり処理が重くなる原因になってしまうのでしょうか？

初学者の為稚拙な内容の質問とも思われますが、調べても自分の得たい情報に行き着くことができませんでした。お力添え頂ける箇所が御座いましたら、ご教授のほど何卒よろしくお願い申し上げます。

Answer 1

ループの前に一回だけ数えるか、ループの中で毎回数えるかの違いです。

cnt = Counter(X)は、Xの要素をキーとして回数をバリューとする辞書を作ります。
ループの中では、この辞書からデータを取ってくるだけなので高速です。
1番目ののコードは二重ループの中で毎回回数を数えています。
forループの中で Counter(X)[i]とかやれば、毎回回数を数えるので同じように遅くなります。

Comments

[kay_ventris4]

なるほど！
.count()メソッドを用いようにも、同様にループの中でいちいち回す必要があった為処理が遅くなったからだったんですね。
ご丁寧にありがとうございました。