python - Python 中最长的递增子序列(For vs While 循环)

Question

我正在解决这个 leetcode 问题 link我们应该在其中找到列表或数组中的最长递增子序列。我使用解决了问题两种方法。

• 首先使用while循环
• 使用嵌套的for 循环

Even though the value of (i, j) or looping is exactly same, but for the higher length inputs, the while loop program is taking more time than the for program. 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 的循环几乎相同？非常感谢您的回答。

Answer 1

看字节码

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。仅这些就增加了可衡量的执行时间。