python - 为什么 Python 中的嵌套 `if` 比并行 `and` 慢得多？

Question

我正在回答在线法官的问题。解决方案的一部分如下所示:

if j > 0 and i < m and B[j-1] > A[i]:
    imin = i + 1
elif i > 0 and j < n and A[i-1] > B[j]:
    imax = i - 1

它毫无问题地通过了法官。

但是，如果我把它改成

if j > 0 and i < m:
    if B[j-1] > A[i]:
        imin = i + 1
elif i > 0 and j < n:
    if A[i-1] > B[j]:
        imax = i - 1

法官立即告诉我我已经超过了时间限制，即使是在一个非常简单的测试用例上也是如此。

我相信这两段代码在逻辑上是等价的(当然我在这里可能是错的。如果是这样的话请纠正我。)。令我惊讶的是，将并行 and 更改为嵌套 if 会产生如此大的差异。我的假设对吗？如果是这样，为什么会发生这种情况，这有多大不同？

(很抱歉，我无法提供程序运行的确切时间，因为在线判断没有说明运行测试用例需要多少时间。整个功能可在here找到，问题是 here 。它是关于找到放在一起的两个排序数组的中位数。失败的测试用例包括 [1], [1] 和 [1,1], [1, 1])

整个函数:

def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if j > 0 and i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and j < n and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect
            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

Answer 1

嵌套你的 if内部既不快也不慢，对于 Python 第一个 if test 编译成完全相同的字节码，如果是孤立的:

>>> import dis
>>> dis.dis(compile('''\
... if j > 0 and i < m and B[j-1] > A[i]:
...     pass
... ''', '', 'exec'))
  1           0 LOAD_NAME                0 (j)
              3 LOAD_CONST               0 (0)
              6 COMPARE_OP               4 (>)
              9 POP_JUMP_IF_FALSE       48
             12 LOAD_NAME                1 (i)
             15 LOAD_NAME                2 (m)
             18 COMPARE_OP               0 (<)
             21 POP_JUMP_IF_FALSE       48
             24 LOAD_NAME                3 (B)
             27 LOAD_NAME                0 (j)
             30 LOAD_CONST               1 (1)
             33 BINARY_SUBTRACT
             34 BINARY_SUBSCR
             35 LOAD_NAME                4 (A)
             38 LOAD_NAME                1 (i)
             41 BINARY_SUBSCR
             42 COMPARE_OP               4 (>)
             45 POP_JUMP_IF_FALSE       48

  2     >>   48 LOAD_CONST               2 (None)
             51 RETURN_VALUE
>>> dis.dis(compile('''\
... if j > 0 and i < m:
...     if B[j-1] > A[i]:
...         pass
... ''', '', 'exec'))
  1           0 LOAD_NAME                0 (j)
              3 LOAD_CONST               0 (0)
              6 COMPARE_OP               4 (>)
              9 POP_JUMP_IF_FALSE       48
             12 LOAD_NAME                1 (i)
             15 LOAD_NAME                2 (m)
             18 COMPARE_OP               0 (<)
             21 POP_JUMP_IF_FALSE       48

  2          24 LOAD_NAME                3 (B)
             27 LOAD_NAME                0 (j)
             30 LOAD_CONST               1 (1)
             33 BINARY_SUBTRACT
             34 BINARY_SUBSCR
             35 LOAD_NAME                4 (A)
             38 LOAD_NAME                1 (i)
             41 BINARY_SUBSCR
             42 COMPARE_OP               4 (>)
             45 POP_JUMP_IF_FALSE       48

  3     >>   48 LOAD_CONST               2 (None)
             51 RETURN_VALUE

上述反汇编中只有行号不同。

但是，您假设 elif分支仍然是等价的。它不是;因为你从第一个 if 中移出了一个测试 , 第二个 elif将被更频繁地测试，独立于B[j-1] > A[i] ;例如如果j > 0 and i < m是真的，但是 B[j-1] > A[i]为 False，您的第一个版本将跳过 elif完全测试，但您的第二个版本仍会测试 i > 0 and j < n !

以dis.dis()完整输出 if..elif测试，并删除除比较和跳跃之外的所有内容，您将得到:

          6 COMPARE_OP               4 (>)
          9 POP_JUMP_IF_FALSE       51
         18 COMPARE_OP               0 (<)
         21 POP_JUMP_IF_FALSE       51

         42 COMPARE_OP               4 (>)
         45 POP_JUMP_IF_FALSE       51
         48 JUMP_FORWARD            48 (to 99)

         57 COMPARE_OP               4 (>)
         60 POP_JUMP_IF_FALSE       99
         69 COMPARE_OP               0 (<)
         72 POP_JUMP_IF_FALSE       99

         93 COMPARE_OP               4 (>)
         96 POP_JUMP_IF_FALSE       99
    >>   99 LOAD_CONST               2 (None)
        102 RETURN_VALUE

对于您的初始版本，但移动了 and部分分开，嵌套 if你得到的测试:

          6 COMPARE_OP               4 (>)
          9 POP_JUMP_IF_FALSE       51
         18 COMPARE_OP               0 (<)
         21 POP_JUMP_IF_FALSE       51

         42 COMPARE_OP               4 (>)
         45 POP_JUMP_IF_FALSE       99
         48 JUMP_FORWARD            48 (to 99)

         57 COMPARE_OP               4 (>)
         60 POP_JUMP_IF_FALSE       99
         69 COMPARE_OP               0 (<)
         72 POP_JUMP_IF_FALSE       99

         93 COMPARE_OP               4 (>)
         96 POP_JUMP_IF_FALSE       99
    >>   99 LOAD_CONST               2 (None)
        102 RETURN_VALUE

注意 POP_JUMP_IF_FALSE索引 45 处的操作码。一个跳转到末尾 (99)，另一个跳转到 elif。分支(索引 51)!

这肯定是您代码中的一个错误，导致花费更多的时间并且法官无法通过您的代码。