我正在解决这个 leetcode 问题 link我们应该在其中找到列表或数组中的最长递增子序列。我使用解决了问题
两种方法。
- 首先使用
while循环 - 使用嵌套的
for循环
Even though the value of (i, j) or looping is exactly same, but for the higher length inputs, the
while loopprogram is taking more time than theforprogram. I am not sure why?
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 ---
WHILE 循环
# 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 循环 比 for 循环 花费更多的时间，即使 i 和 j 的循环几乎相同？非常感谢您的回答。
最佳答案
看字节码
while 循环必须执行更多操作。
Python 正在执行字节码。因此，字节码指令的数量和种类可以提示实际发生了什么。
dis 模块中的函数dis:
import dis
可以可视化字节码。
首先针对 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。仅这些就增加了可衡量的执行时间。
关于python - Python 中最长的递增子序列(For vs While 循环)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34561569/