我正在解决这个leetcode问题链接，我们应该在其中找到longest increasing sub-sequence in a list or array。我用两种方法解决了这个问题。
while循环for循环即使（i，j）或循环的值完全相同，但是对于
while loop更长的输入，该程序比该for程序花费更多的时间。我不确定为什么吗？
为循环
import time
start_time = time.time()
class Solution(object):
# using dP
def lengthOfLIS1(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print Solution().lengthOfLIS1([1] * 1249 + [101] + [1] * 1250)
print("--- %s seconds ---" % (time.time() - start_time))
输出：
2
--- 0.240112066269 seconds ---
循环时
# This problem an be done in O(n*n)
import time
start_time = time.time()
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return []
elif len(nums) == 1:
return nums
size = len(nums)
subsequence_array = [1] * size
i, j, max_value = 0, 1, 1
while j < size:
if nums[j] > nums[i]:
subsequence_array[j] = max(subsequence_array[j], subsequence_array[i] + 1)
if max_value < subsequence_array[j]:
max_value = subsequence_array[j]
i += 1
if j == i:
i = 0
j += 1
else:
i += 1
if i == j:
j += 1
i = 0
return max_value
print Solution().lengthOfLIS([1] * 1249 + [101] + [1] * 1250)
print("--- %s seconds ---" % (time.time() - start_time))
输出值
2
--- 0.331799030304 seconds ---
谁能解释为什么即使循环几乎相同，仍然while loop比花费更多的时间？将感谢您的回答。for loopi and j
该while回路必须做更多的方式操作。Python正在执行字节码。因此，字节码指令的数量和种类可以提示您实际发生的情况。
dis模块中的功能dis：
import dis
可以形象地显示bytcode。
首先是range解决方案：
dis.dis(SolutionRange)
Disassembly of lengthOfLIS1:
8 0 LOAD_FAST 1 (nums)
3 POP_JUMP_IF_TRUE 10
9 6 LOAD_CONST 1 (0)
9 RETURN_VALUE
10 >> 10 LOAD_CONST 2 (1)
13 BUILD_LIST 1
16 LOAD_GLOBAL 0 (len)
19 LOAD_FAST 1 (nums)
22 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
25 BINARY_MULTIPLY
26 STORE_FAST 2 (dp)
11 29 SETUP_LOOP 103 (to 135)
32 LOAD_GLOBAL 1 (range)
35 LOAD_CONST 2 (1)
38 LOAD_GLOBAL 0 (len)
41 LOAD_FAST 1 (nums)
44 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
47 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
50 GET_ITER
>> 51 FOR_ITER 80 (to 134)
54 STORE_FAST 3 (i)
12 57 SETUP_LOOP 71 (to 131)
60 LOAD_GLOBAL 1 (range)
63 LOAD_FAST 3 (i)
66 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
69 GET_ITER
>> 70 FOR_ITER 57 (to 130)
73 STORE_FAST 4 (j)
13 76 LOAD_FAST 1 (nums)
79 LOAD_FAST 3 (i)
82 BINARY_SUBSCR
83 LOAD_FAST 1 (nums)
86 LOAD_FAST 4 (j)
89 BINARY_SUBSCR
90 COMPARE_OP 4 (>)
93 POP_JUMP_IF_FALSE 70
14 96 LOAD_GLOBAL 2 (max)
99 LOAD_FAST 2 (dp)
102 LOAD_FAST 3 (i)
105 BINARY_SUBSCR
106 LOAD_FAST 2 (dp)
109 LOAD_FAST 4 (j)
112 BINARY_SUBSCR
113 LOAD_CONST 2 (1)
116 BINARY_ADD
117 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
120 LOAD_FAST 2 (dp)
123 LOAD_FAST 3 (i)
126 STORE_SUBSCR
127 JUMP_ABSOLUTE 70
>> 130 POP_BLOCK
>> 131 JUMP_ABSOLUTE 51
>> 134 POP_BLOCK
15 >> 135 LOAD_GLOBAL 2 (max)
138 LOAD_FAST 2 (dp)
141 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
144 RETURN_VALUE
现在是while解决方案：
dis.dis(SolutionWhile)
Disassembly of lengthOfLIS:
7 0 LOAD_FAST 1 (nums)
3 POP_JUMP_IF_TRUE 10
8 6 BUILD_LIST 0
9 RETURN_VALUE
9 >> 10 LOAD_GLOBAL 0 (len)
13 LOAD_FAST 1 (nums)
16 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
19 LOAD_CONST 1 (1)
22 COMPARE_OP 2 (==)
25 POP_JUMP_IF_FALSE 32
10 28 LOAD_FAST 1 (nums)
31 RETURN_VALUE
12 >> 32 LOAD_GLOBAL 0 (len)
35 LOAD_FAST 1 (nums)
38 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
41 STORE_FAST 2 (size)
13 44 LOAD_CONST 1 (1)
47 BUILD_LIST 1
50 LOAD_FAST 2 (size)
53 BINARY_MULTIPLY
54 STORE_FAST 3 (subsequence_array)
14 57 LOAD_CONST 3 ((0, 1, 1))
60 UNPACK_SEQUENCE 3
63 STORE_FAST 4 (i)
66 STORE_FAST 5 (j)
69 STORE_FAST 6 (max_value)
15 72 SETUP_LOOP 172 (to 247)
>> 75 LOAD_FAST 5 (j)
78 LOAD_FAST 2 (size)
81 COMPARE_OP 0 (<)
84 POP_JUMP_IF_FALSE 246
16 87 LOAD_FAST 1 (nums)
90 LOAD_FAST 5 (j)
93 BINARY_SUBSCR
94 LOAD_FAST 1 (nums)
97 LOAD_FAST 4 (i)
100 BINARY_SUBSCR
101 COMPARE_OP 4 (>)
104 POP_JUMP_IF_FALSE 205
17 107 LOAD_GLOBAL 1 (max)
110 LOAD_FAST 3 (subsequence_array)
113 LOAD_FAST 5 (j)
116 BINARY_SUBSCR
117 LOAD_FAST 3 (subsequence_array)
120 LOAD_FAST 4 (i)
123 BINARY_SUBSCR
124 LOAD_CONST 1 (1)
127 BINARY_ADD
128 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
131 LOAD_FAST 3 (subsequence_array)
134 LOAD_FAST 5 (j)
137 STORE_SUBSCR
18 138 LOAD_FAST 6 (max_value)
141 LOAD_FAST 3 (subsequence_array)
144 LOAD_FAST 5 (j)
147 BINARY_SUBSCR
148 COMPARE_OP 0 (<)
151 POP_JUMP_IF_FALSE 164
19 154 LOAD_FAST 3 (subsequence_array)
157 LOAD_FAST 5 (j)
160 BINARY_SUBSCR
161 STORE_FAST 6 (max_value)
20 >> 164 LOAD_FAST 4 (i)
167 LOAD_CONST 1 (1)
170 INPLACE_ADD
171 STORE_FAST 4 (i)
21 174 LOAD_FAST 5 (j)
177 LOAD_FAST 4 (i)
180 COMPARE_OP 2 (==)
183 POP_JUMP_IF_FALSE 243
22 186 LOAD_CONST 2 (0)
189 STORE_FAST 4 (i)
23 192 LOAD_FAST 5 (j)
195 LOAD_CONST 1 (1)
198 INPLACE_ADD
199 STORE_FAST 5 (j)
202 JUMP_ABSOLUTE 75
25 >> 205 LOAD_FAST 4 (i)
208 LOAD_CONST 1 (1)
211 INPLACE_ADD
212 STORE_FAST 4 (i)
26 215 LOAD_FAST 4 (i)
218 LOAD_FAST 5 (j)
221 COMPARE_OP 2 (==)
224 POP_JUMP_IF_FALSE 75
27 227 LOAD_FAST 5 (j)
230 LOAD_CONST 1 (1)
233 INPLACE_ADD
234 STORE_FAST 5 (j)
28 237 LOAD_CONST 2 (0)
240 STORE_FAST 4 (i)
>> 243 JUMP_ABSOLUTE 75
>> 246 POP_BLOCK
30 >> 247 LOAD_FAST 6 (max_value)
250 RETURN_VALUE
while解决方案中还有更多行的字节码。这表明速度较慢。当然，并非所有字节码指令都花费相同的时间，因此需要更深入地分析以获得更定量的答案。
在Python中，一切都是对象。因此，这：
>>> 1 + 1
2
实际上是这样做的：
>>> 1 .__add__(1)
2
因此，两个整数的简单加法涉及对该方法的调用__add__()。这样的通话相对较慢。
例如，我们有以下列表：
L = list(range(int(1e6)))
内置函数的和sum()：
%%timeit
sum(L)
100 loops, best of 3: 15.9 ms per loop
比编写循环快得多：
%%timeit
sum_ = 0
for x in L:
sum_ += x
10 loops, best of 3: 95.7 ms per loop
内建的sum使用优化避免了“一切都是对象”概念所造成的一些开销。
该while解决方案具有许多操作，例如j += 1。仅这些一项就增加了可测量的执行时间。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句