pythonの処理速度について

Question

AtCoder競プロ典型90問、10問目score sum queries についてですが、私の回答は以下です。

n = int(input())

CP = [list(map(int, input().split())) for _ in range(n)]

q = int(input())

for i in range(q):
  lans = 0
  rans = 0
  l, r = map(int, input().split())
  for j in range(l-1, r):
    if CP[j][0] == 1:
      lans += CP[j][1]
    else:
      rans += CP[j][1]
  print(lans, rans)

これではTLEになってしまいます。そして、以下のコード

n = int(input())

C = []
P = []
for i in range(n):
    c, p = map(int,input().split())
    C.append(c)
    P.append(p)

q = int(input())

L = []
R = []
for i in range(q):
    l, r = map(int,input().split())
    L.append(l-1)
    R.append(r)

tmp1 = 0
tmp2 = 0
sum_score = [[0, 0]]
for i in range(n):
    if C[i] == 1:
        tmp1 += P[i]
    else:
        tmp2 += P[i]
    sum_score.append([tmp1, tmp2])

for k in range(q):
    A = sum_score[R[k]][0] - sum_score[L[k]][0]
    B = sum_score[R[k]][1] - sum_score[L[k]][1]
    print(str(A) + " " + str(B))

これだとACになります。まだまだ初心者で処理速度のことがよくわかっていないのですが、後者の方がかなり速くなるのはなぜですか？素人考えでは後者の方が面倒くさい処理をしているように感じてしまいます。for文を二重にすることは処理速度の面では悪手でしょうか。そして、処理を速くするために学ぶべき知識があれば教えていただけると嬉しいです。よろしくお願いします。

Answer 1

• 後者の方がかなり速くなるのはなぜですか

成績データを累積していくのを一回で済ませているからです。

• 素人考えでは後者の方が面倒くさい処理をしているように感じてしまいます。

一般的に、高速化してチューニングしたコードは、最初に作る低速なコードに比べて行数が多くなります。
人手でお菓子を作って箱につめるのは手順は簡単ですが遅いですね。これを材料の混ぜ合わせ、加熱、デコレーション、箱詰めのような作業に分割し、工場ラインを作って大量生産すると、手順は複雑になりますが高速化します。それと同じようなものです。

• for文を二重にすることは処理速度の面では悪手でしょうか。

Pythonではたいていの場合悪手です。

数値計算などの場合は、一重ループを二重ループにしてSIMD化することで高速になることは多いですが、これも手動でやるのではなくコンパイラの最適化に任せた方がたいていより速くなります。

• 処理を速くするために学ぶべき知識があれば教えていただけると嬉しいです。

１　良いアルゴリズムを覚えましょう。

アルゴリズムの教科書などで基礎勉強をした方が、結局は速く良いコードが書けるようになります。
ネット上の記事は嘘をかいているものも多いので、ちゃんとした本を買って読んだ方がよいですよ。

２ 計算量オーダーを理解しましょう。

たとえば、こういうのを読みましょう。これも、ちゃんと本を買って勉強した方がよいでしょう。

３　自分のところでちゃんと流して測定しましょう。

チューニングを失敗する人の大半は、測定をせずに、思い込みでチューニングします。そして、性能に関係ないところをチューニングして、無駄に自分の時間を使っています。