Почему вложенные `if` в Python намного медленнее параллельных` и `?

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 

Обратите внимание на POP_JUMP_IF_FALSE опкод по индексу 45. Один подскакивает до конца (99), а другой переходит к elif Branc ч (по индексу 51)!

Это, безусловно, ошибка в коде, что приводит к гораздо большему времени, проведенному, и судья не выполняет ваш код.