Pythonで関数をつけると実行時間が減る

Question

最近競技プログラミングを始めた初心者です。

AtCoderで下のURLにある動的計画法の問題をPythonで解きました。
https://atcoder.jp/contests/dp/tasks/dp_b

下のようなコードを書くと、TLE(実行時間超過)となりました。

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
dp=[0]*N
 
for i in range(1,N):
	dp[i] = min(
		dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
	)
 
print(dp[N-1])

しかし、下のようにmain()をつけるとTLEになりませんでした。

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
 
	dp=[0]*N
 
	for i in range(1,N):
		dp[i] = min(
			dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
	    )
	print(dp[N-1])
main()

なぜmain()をつけただけでTLEにならなくなったのかご教授願いたいです。

Answer 1

ローカル変数の方がグローバル変数よりも参照速度が速いからです。

Local names are fater than global ones.
LOAD_CONST > LOAD_FAST > LOAD_NAME or LOAD_GLOBAL

• Understanding Python Bytecode | PyCon 2018 - YouTube

以下のコードを対話モード >>> にコピペして貼り付けると雰囲気が掴めるかもしれません。

global_variable = """
a = 0
for _ in range(10**2):
    a
"""

local_variable = """
def main():
    b = 0
    for _ in range(10**2):
        b
"""


import timeit
timeit.timeit(global_variable)
timeit.timeit(local_variable)

import dis
dis.dis(global_variable)
dis.dis(local_variable)

Comments

[onioni22]

回答ありがとうございました！