Python 的递减循环 运行 是否比递增循环慢？
Does Python's decrement loop run slower than increment loop?
我正在解决 leetcode 的帕斯卡三角问题。我观察到两个 for 循环分别执行相同的任务，但用递减循环解决它给了我一个低效的解决方案。
Given a non-negative index k where k ≤ 33, return the kth index row of
the Pascal's triangle.
Note that the row index starts from 0.
增量循环解决方案
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
result = [1 for _ in range(rowIndex+1)]
for i in range(2,rowIndex+1):
for j in range(1,i):
result[i-j] = result[i-j]+result[i-j-1]
return result
递减循环解决方案
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
result = [1 for _ in range(rowIndex+1)]
for i in range(2,rowIndex+1):
for j in range(i-1,0,-1):
result[j] = result[j]+result[j-1]
return result
这是真的吗？
首先，这里有一个函数 returns 帕斯卡三角形的单行列表，而不计算前一行。它为整数 n >= 0.
提供正确的输出
def pascal(n):
''' Row n of Pascal's triangle '''
p = 1
row = [p]
for i in range(1, n+1):
p = p * n // i
n -= 1
row.append(p)
return row
# test
for n in range(8):
print(n, pascal(n))
输出
0 [1]
1 [1, 1]
2 [1, 2, 1]
3 [1, 3, 3, 1]
4 [1, 4, 6, 4, 1]
5 [1, 5, 10, 10, 5, 1]
6 [1, 6, 15, 20, 15, 6, 1]
7 [1, 7, 21, 35, 35, 21, 7, 1]
下面是一些使用标准 timeit 模块的代码，比较了各种方法的时间。
from __future__ import print_function
from timeit import Timer
def getRow_inc(rowIndex):
result = [1] * (rowIndex + 1)
for i in range(2, rowIndex + 1):
for j in range(1, i):
result[i-j] = result[i-j] + result[i-j-1]
return result
def getRow_dec(rowIndex):
result = [1] * (rowIndex + 1)
for i in range(2, rowIndex + 1):
for j in range(i-1, 0, -1):
result[j] = result[j] + result[j-1]
return result
def pascal(n):
''' Row n of Pascal's triangle '''
p = 1
row = [p]
for i in range(1, n+1):
p = p * n // i
n -= 1
row.append(p)
return row
funcs = (getRow_inc, getRow_dec, pascal)
def time_test(size, loops):
timings = []
for func in funcs:
t = Timer(lambda: func(size))
result = sorted(t.repeat(3, loops))
timings.append((result, func.__name__))
timings.sort()
for result, name in timings:
print('{0:10} : {1}'.format(name, result))
print()
def verify(size):
return getRow_inc(size) == getRow_dec(size) == pascal(size)
loops = 8192
size = 2
for i in range(6):
print('Size:', size, 'Loops:', loops, verify(size))
time_test(size, loops)
size <<= 1
loops >>= 1
python 2.6输出
Size: 2 Loops: 8192 True
pascal : [0.043977975845336914, 0.044337987899780273, 0.044638156890869141]
getRow_inc : [0.051661968231201172, 0.051739931106567383, 0.05926203727722168]
getRow_dec : [0.051797866821289062, 0.052932977676391602, 0.053112030029296875]
Size: 4 Loops: 4096 True
pascal : [0.030641078948974609, 0.031950950622558594, 0.035629987716674805]
getRow_dec : [0.053617000579833984, 0.054769992828369141, 0.056906938552856445]
getRow_inc : [0.058582067489624023, 0.059936046600341797, 0.066784143447875977]
Size: 8 Loops: 2048 True
pascal : [0.024718999862670898, 0.024795055389404297, 0.024961948394775391]
getRow_dec : [0.071218013763427734, 0.072144031524658203, 0.073839902877807617]
getRow_inc : [0.085191011428833008, 0.085605144500732422, 0.093863964080810547]
Size: 16 Loops: 1024 True
pascal : [0.021828889846801758, 0.021852970123291016, 0.022058010101318359]
getRow_dec : [0.11763501167297363, 0.12208914756774902, 0.13960886001586914]
getRow_inc : [0.15797996520996094, 0.16045904159545898, 0.1609339714050293]
Size: 32 Loops: 512 True
pascal : [0.027434110641479492, 0.027448892593383789, 0.027502059936523438]
getRow_dec : [0.21527910232543945, 0.21595311164855957, 0.25867199897766113]
getRow_inc : [0.29518985748291016, 0.30337095260620117, 0.30416202545166016]
Size: 64 Loops: 256 True
pascal : [0.029985904693603516, 0.030019044876098633, 0.030050039291381836]
getRow_dec : [0.44218015670776367, 0.46946215629577637, 0.49126601219177246]
getRow_inc : [0.63355302810668945, 0.63923096656799316, 0.68472099304199219]
python 3.6输出
Size: 2 Loops: 8192 True
pascal : [0.04358131700064405, 0.04425547199934954, 0.04470863800088409]
getRow_inc : [0.05114753599991673, 0.051217224998254096, 0.05178851000164286]
getRow_dec : [0.05115222699896549, 0.051395288999628974, 0.05416869800319546]
Size: 4 Loops: 4096 True
getRow_dec : [0.057865087997925, 0.08918459000051371, 0.11932526199962012]
pascal : [0.05869485400035046, 0.06098903500242159, 0.0629262660004315]
getRow_inc : [0.0613923060009256, 0.06144011699871044, 0.08097989900124958]
Size: 8 Loops: 2048 True
pascal : [0.023705500996584306, 0.024017232997721294, 0.0252248659999168]
getRow_dec : [0.07945838300292962, 0.07997345200055861, 0.10279535600056988]
getRow_inc : [0.0951986139989458, 0.10361288200147101, 0.12552303700067569]
Size: 16 Loops: 1024 True
pascal : [0.022952020000957418, 0.022961610000493238, 0.024299886001244886]
getRow_dec : [0.13245858099980978, 0.13321232800080907, 0.13570772599996417]
getRow_inc : [0.17226859199945466, 0.17394291900200187, 0.20096674900196376]
Size: 32 Loops: 512 True
pascal : [0.023837570999603486, 0.03626328599784756, 0.04858057100136648]
getRow_dec : [0.25379533899831586, 0.25503273499998613, 0.25983839800028363]
getRow_inc : [0.3346854230003373, 0.33851587800018024, 0.37444046800010256]
Size: 64 Loops: 256 True
pascal : [0.024329154002771247, 0.024376211000344483, 0.025199785999575397]
getRow_dec : [0.5039554230024805, 0.5147428849995777, 0.529499655996915]
getRow_inc : [0.6677602630006731, 0.6715008999999554, 0.6890275240002666]
我正在解决 leetcode 的帕斯卡三角问题。我观察到两个 for 循环分别执行相同的任务，但用递减循环解决它给了我一个低效的解决方案。
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
Note that the row index starts from 0.
增量循环解决方案
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
result = [1 for _ in range(rowIndex+1)]
for i in range(2,rowIndex+1):
for j in range(1,i):
result[i-j] = result[i-j]+result[i-j-1]
return result
递减循环解决方案
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
result = [1 for _ in range(rowIndex+1)]
for i in range(2,rowIndex+1):
for j in range(i-1,0,-1):
result[j] = result[j]+result[j-1]
return result
这是真的吗？
首先，这里有一个函数 returns 帕斯卡三角形的单行列表，而不计算前一行。它为整数 n >= 0.
def pascal(n):
''' Row n of Pascal's triangle '''
p = 1
row = [p]
for i in range(1, n+1):
p = p * n // i
n -= 1
row.append(p)
return row
# test
for n in range(8):
print(n, pascal(n))
输出
0 [1]
1 [1, 1]
2 [1, 2, 1]
3 [1, 3, 3, 1]
4 [1, 4, 6, 4, 1]
5 [1, 5, 10, 10, 5, 1]
6 [1, 6, 15, 20, 15, 6, 1]
7 [1, 7, 21, 35, 35, 21, 7, 1]
下面是一些使用标准 timeit 模块的代码，比较了各种方法的时间。
from __future__ import print_function
from timeit import Timer
def getRow_inc(rowIndex):
result = [1] * (rowIndex + 1)
for i in range(2, rowIndex + 1):
for j in range(1, i):
result[i-j] = result[i-j] + result[i-j-1]
return result
def getRow_dec(rowIndex):
result = [1] * (rowIndex + 1)
for i in range(2, rowIndex + 1):
for j in range(i-1, 0, -1):
result[j] = result[j] + result[j-1]
return result
def pascal(n):
''' Row n of Pascal's triangle '''
p = 1
row = [p]
for i in range(1, n+1):
p = p * n // i
n -= 1
row.append(p)
return row
funcs = (getRow_inc, getRow_dec, pascal)
def time_test(size, loops):
timings = []
for func in funcs:
t = Timer(lambda: func(size))
result = sorted(t.repeat(3, loops))
timings.append((result, func.__name__))
timings.sort()
for result, name in timings:
print('{0:10} : {1}'.format(name, result))
print()
def verify(size):
return getRow_inc(size) == getRow_dec(size) == pascal(size)
loops = 8192
size = 2
for i in range(6):
print('Size:', size, 'Loops:', loops, verify(size))
time_test(size, loops)
size <<= 1
loops >>= 1
python 2.6输出
Size: 2 Loops: 8192 True
pascal : [0.043977975845336914, 0.044337987899780273, 0.044638156890869141]
getRow_inc : [0.051661968231201172, 0.051739931106567383, 0.05926203727722168]
getRow_dec : [0.051797866821289062, 0.052932977676391602, 0.053112030029296875]
Size: 4 Loops: 4096 True
pascal : [0.030641078948974609, 0.031950950622558594, 0.035629987716674805]
getRow_dec : [0.053617000579833984, 0.054769992828369141, 0.056906938552856445]
getRow_inc : [0.058582067489624023, 0.059936046600341797, 0.066784143447875977]
Size: 8 Loops: 2048 True
pascal : [0.024718999862670898, 0.024795055389404297, 0.024961948394775391]
getRow_dec : [0.071218013763427734, 0.072144031524658203, 0.073839902877807617]
getRow_inc : [0.085191011428833008, 0.085605144500732422, 0.093863964080810547]
Size: 16 Loops: 1024 True
pascal : [0.021828889846801758, 0.021852970123291016, 0.022058010101318359]
getRow_dec : [0.11763501167297363, 0.12208914756774902, 0.13960886001586914]
getRow_inc : [0.15797996520996094, 0.16045904159545898, 0.1609339714050293]
Size: 32 Loops: 512 True
pascal : [0.027434110641479492, 0.027448892593383789, 0.027502059936523438]
getRow_dec : [0.21527910232543945, 0.21595311164855957, 0.25867199897766113]
getRow_inc : [0.29518985748291016, 0.30337095260620117, 0.30416202545166016]
Size: 64 Loops: 256 True
pascal : [0.029985904693603516, 0.030019044876098633, 0.030050039291381836]
getRow_dec : [0.44218015670776367, 0.46946215629577637, 0.49126601219177246]
getRow_inc : [0.63355302810668945, 0.63923096656799316, 0.68472099304199219]
python 3.6输出
Size: 2 Loops: 8192 True
pascal : [0.04358131700064405, 0.04425547199934954, 0.04470863800088409]
getRow_inc : [0.05114753599991673, 0.051217224998254096, 0.05178851000164286]
getRow_dec : [0.05115222699896549, 0.051395288999628974, 0.05416869800319546]
Size: 4 Loops: 4096 True
getRow_dec : [0.057865087997925, 0.08918459000051371, 0.11932526199962012]
pascal : [0.05869485400035046, 0.06098903500242159, 0.0629262660004315]
getRow_inc : [0.0613923060009256, 0.06144011699871044, 0.08097989900124958]
Size: 8 Loops: 2048 True
pascal : [0.023705500996584306, 0.024017232997721294, 0.0252248659999168]
getRow_dec : [0.07945838300292962, 0.07997345200055861, 0.10279535600056988]
getRow_inc : [0.0951986139989458, 0.10361288200147101, 0.12552303700067569]
Size: 16 Loops: 1024 True
pascal : [0.022952020000957418, 0.022961610000493238, 0.024299886001244886]
getRow_dec : [0.13245858099980978, 0.13321232800080907, 0.13570772599996417]
getRow_inc : [0.17226859199945466, 0.17394291900200187, 0.20096674900196376]
Size: 32 Loops: 512 True
pascal : [0.023837570999603486, 0.03626328599784756, 0.04858057100136648]
getRow_dec : [0.25379533899831586, 0.25503273499998613, 0.25983839800028363]
getRow_inc : [0.3346854230003373, 0.33851587800018024, 0.37444046800010256]
Size: 64 Loops: 256 True
pascal : [0.024329154002771247, 0.024376211000344483, 0.025199785999575397]
getRow_dec : [0.5039554230024805, 0.5147428849995777, 0.529499655996915]
getRow_inc : [0.6677602630006731, 0.6715008999999554, 0.6890275240002666]