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测试编译成完全相同的字节码，如果单独使用：

>>> 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为True，但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

注意索引45处的POP_JUMP_IF_FALSE操作码。一个跳到末尾（99），另一个跳到elif分支（在索引51处）！你知道吗

这当然是你的代码中的一个bug，导致花费的时间远远超过了你的代码，而法官也没有通过你的代码。你知道吗