概要
3/25(日)のABC90の問題Cについてのメモ
問題
AtCoder Beginner Contest 092 C：Traveling Plan
ざっくり言うと
- x軸上にN個の点$A_1,A_2,...,A_N$をとるよ
- 原点(0)→$A_1$→$A_2$→・・・→$A_N$→原点というふうに周るよ
- ただしある1点$A_i(i=1,2,...,N)$だけは訪れないよ
- 移動にかかる金額を前後の座標の差の絶対値$|A_{j+1}-A_j|$で表すよ
- $A_i$を訪れない時の移動総額をそれぞれの$i$について求めてね
考えた手順
- $A_i$を除いた座標のリストを作成する
- 1で作成したリストに対し ①右端に0を挿入したリスト ②左端に0を挿入したリスト をそれぞれ作る
- $|②-①|$を実行して$A_i$を訪れないときのそれぞれの移動にかかる金額を計算する
- 3で求めた金額の総和を取る
- 1〜4を全ての$1\leq i \leq N$について実行する
考えたコード
import numpy as np
def main():
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
ans = [np.sum(np.abs(np.r_[A[:i], A[i+1:], 0] \
- np.r_[0, A[:i], A[i+1:]])) \
for i in range(N)]
[print(ans[i]) for i in range(N)]
if __name__ == "__main__":
main()
補足
手順1,2: $A_i$を除き端に0を挿入したリストの作成
→ np.r_[A[:i], A[i+1:], 0]
手順3: 絶対値の計算
→ np.abs()
手順4: 総和
→ np.sum()
速さが足りない！！
＞＞＞ TLE ＜＜＜
制限時間(各テストケースにつき2秒)をオーバー。なんでや！(下で検証)
スマートな方
def main():
n = int(input())
a = list(map(int, input().split()))
a.append(0)
a.insert(0, 0)
costs = []
for i in range(n + 1):
costs.append(abs(a[i + 1] - a[i]))
s = sum(costs)
for i in range(n):
print(s - costs[i] - costs[i + 1] + abs(a[i] - a[i + 2]))
if __name__ == "__main__":
main()
実行時間は155ms
制限時間が2000msなので僕のプログラムの十数倍は速い。
アルゴリズム
1. リストaの両端に0(原点)を挿入
2. 0→$A_1$, $A_1$→$A_2$, ... , $A_N$→0の移動にかかる金額のリストを作成
3. 2で作成したリストの総和を計算
4. 3から$A_i$を脱落させたときの金額をすべての$i$について計算
こちらの方が速度が出る理由はよく分かっていない。
イメージでは数値計算をnumpyでしたりfor文を内包表記で書いたりした方が速い気がするのになぜだろう。
何が違うのか？
準備
遅いところを確かめるためまずはタイマーを準備
こちらの記事を参考に(という名のほぼ丸々コピー)させて頂きました。ありがとうございます。
def time(func):
import functools
import datetime
@functools.wraps(func)
def wrapper(*args, **kwargs):
start = datetime.datetime.today()
result = func(*args, **kwargs)
end = datetime.datetime.today()
print("processing time of function[{1}] is {0}".format(end-start, func.__name__))
return result
return wrapper
コードを分割してタイマーをセット
速度差を見たいので
n = 10000
a = [-5000, -4999, ... , 4998, 4999]
として入力の部分を省略。
・自分のコード
import time_measurer
import numpy as np
#セクション1
@time_measurer.time
def makeNdarray(a):
a = np.array(a)
return a
#セクション2
@time_measurer.time
def calculateCosts(a,n):
ans = [np.sum(np.abs(np.r_[a[:i], a[i+1:], 0] \
- np.r_[0, a[:i], a[i+1:]])) \
for i in range(n)]
return ans
#セクション3
@time_measurer.time
def printAns(ans,n):
[print(ans[i]) for i in range(n)]
@time_measurer.time
def main():
n = 10000
a = [i-5000 for i in range(n)]
a = makeNdarray(a)
ans = calculateCosts(a, n)
printAns(ans, n)
if __name__ == "__main__":
main()
セクション
1. 受け取ったリストaをnp.ndarrayに変換する時間
2. 答えを計算する時間
3. 答えを表示する時間
をそれぞれ測定。加えてmain()の総実行時間も測定
・速いコード
import time_measurer
#セクション1
@time_measurer.time
def makeCostList(pointList, n):
pointList.append(0)
pointList.insert(0,0)
costList = []
for i in range(n+1):
costList.append(abs(pointList[i+1] - pointList[i]))
return costList
#セクション2
@time_measurer.time
def CalculateCost(pointList, costList, n):
s = sum(costList)
for i in range(n):
print(s - costList[i] - costList[i+1] + abs(pointList[i] - pointList[i+2]))
@time_measurer.time
def main():
n = 10000
a = [i-5000 for i in range(n)]
costs = makeCostList(a,n)
CalculateCost(a, costs, n)
if __name__ == "__main__":
main()
セクション
1. 各移動の金額のリストを作る時間
2. 各$A_i$を訪れない時の金額を計算する時間
をそれぞれ測定。加えてmain()の総実行時間も測定
結果
| セクション | 自分のコード | 速いコード |
|---|---|---|
| 1 | 0.7 | 3.0 |
| 2 | 1215.5 | 923.3 |
| 3 | 1025.0 | - |
| main全体 | 2249.6 | 932.0 |
| 比率 | 1 | 0.4143 |
※単位は[ms]
ログ出力等の処理をセクション間で行っているため、main全体の実行時間のほうが各セクションの合計よりも長くなっている。
AtCoder上では自分のコードは2000ms以上かかり、速いコードは200ms以下で終了していたので10倍以上の速度差が出ると思ったが、そうはならなかった。環境の差？ なぜだろうか。絶対的な速度は環境によって大きく変わるだろうけど、その比率はほとんど変わらないはず。勝手な思い込みだろうか？ ともかく納得の行く理由が思いつかなかった。
どちらのコードも核となる計算部分は第2セクション。numpy使って数値計算して内包表記を使ったらより速度が出るのではと思ったがそうでもなかった。式の煩雑さのデメリットのほうが大きかった。
そして時間を食いまくっているのが答えを出力する部分。printだけを繰り返すと遅くなる？ 自分のコードのセクション3はprintのみ。速いコードのセクション2は計算した上でprintしている。繰り返し回数は同じなのに後者のほうが速い理由がわからない。
まとめ
分かったこと
- リストを初期化して要素をappendで追加していくと速い
- printのみの繰り返し処理は遅い
- numpyで計算すればいいってもんじゃない。シンプルな計算方法を考えることが大事
分からなかったこと
- AtCoder上では起こったはずの10倍以上の速度差が見られなかった理由
- print単体のループよりもprintと計算のループの方が速い理由
ここまで読んでくださってありがとうございました。