Почему оператор или быстрее, чем оператор в?

Question

В моем проекте мне нужно было проверить, было ли значение одним из двух значений. Так как я мог подойти к этому с помощью оператора if or или оператора if in, и так как я не знал, какой из них будет работать быстрее, я запустил следующий код для проверки их соответствующих характеристик:

import time
import datetime
from scipy.stats import ttest_ind


def if_in(t):
    bln = False
    for z in range(400):
        if z % 100 == 0: print("test1", z)
        starttime = time.time()
        for x in range(1000000):
            for i in range(5):
                if i in [2, 4]:
                    bln = True
        t.append(time.time() - starttime)
    return t


def if_or(t):
    bln = False
    for z in range(400):
        if z % 100 == 0: print("test2", z)
        starttime = time.time()
        for x in range(1000000):
            for i in range(5):
                if i == 2 or i == 4:
                    bln = True
        t.append(time.time() - starttime)
    return t


st = time.time()

times1 = if_in([])
times2 = if_or([])

t, p = ttest_ind(times1, times2)

print("\nTotal execution time:", str(datetime.timedelta(seconds=time.time() - st)))
t1mean = sum(times1) / len(times1)
t2mean = sum(times2) / len(times2)
print("Test1 mean:", t1mean, "\nTest2 mean:", t2mean)
print("\nT-test p-score:", p)

Который напечатал:

Test1 mean: 0.47915725767612455 
Test2 mean: 0.46851890563964843

T-test p-score: 0.001033983121482868

Значение p указывает, что разница между временем выполнения оператора in и or l oop является значительной.

Почему эта разница? Для метода 'или' я бы предположил, что дальнейшая проверка будет остановлена, когда первое условие будет считаться истинным. То же самое, я снова предполагаю, верно и для метода in. Тем не менее, один из них работает быстрее, чем другой.

Кроме того, это выдержит больше условий? Например, когда i должен быть проверен, чтобы быть одним из 100 значений?

Answer 1

Есть несколько проблем с вашими наблюдениями.

Давайте на мгновение забудем, кто является "победителем".

Первая, самая важная проблема заключается в том, что вы наблюдаете некоторые статистически значимые отклонение от среднего значения, и вы обобщаете это как отражение скорости выполнения некоторой части кода. Хотя это может быть правильным для конкретного прогона кода, ничего нельзя сказать о подходе в целом, потому что на этом уровне в ваших измерениях преобладают флуктуации, управляемые ОС. Я довольно уверен (я сам наблюдал это), что несколько прогонов этого кода дадут вам нового победителя для каждого прогона.

Вторая проблема заключается в том, что вы используете time.time(), который не очень подходит для тестов. Вероятно, вам следует использовать time.perf_counter(), и даже в этом случае он может не подходить для измерения таких коротких временных интервалов.

Третья проблема заключается в том, что ваши данные не подтверждают ваши выводы, поскольку tmean2, связанный с if_or(), на самом деле меньше, чем tmean1, связанный с if_in.

Обратите внимание, что очень сложно (и, вероятно, не имеет значения) фактически измерить, что быстрее между двумя предложенными вами вариантами.

---

Вместо этого интересно исследовать второй вопрос, то есть для больших повторений шаблона x == y0 or x == y1 et c. быстрее ли использовать in на контейнере?

Давайте исследуем это (используя I Python %timeit magi c для таймингов) для различного количества коротких замыканий:

def if_or(n, ks, timer=time.perf_counter):
    for _ in range(n):
        for k in ks:
            if k == 0 or k == 1 or k == 2 or k == 3 or k == 4 \
                    or k == 5 or k == 6 or k == 7 or k == 8 or k == 9:
                pass


def if_in_set(n, ks, timer=time.perf_counter):
    for _ in range(n):
        for k in ks:
            if k in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}:
                pass


def if_in_tuple(n, ks, timer=time.perf_counter):
    for _ in range(n):
        for k in ks:
            if k in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
                pass


def if_in_list(n, ks, timer=time.perf_counter):
    for _ in range(n):
        for k in ks:
            if k in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
                pass


n = 100000
m = 20
ks = [0] * m
%timeit if_or(n, ks)
# 10 loop, best of 3: 59 ms per loop
%timeit if_in_set(n, ks)
# 10 loop, best of 3: 57.6 ms per loop
%timeit if_in_tuple(n, ks)
# 10 loop, best of 3: 52.4 ms per loop
%timeit if_in_list(n, ks)
# 10 loop, best of 3: 54.7 ms per loop


ks = list(range(m))
%timeit if_or(n, ks)
# 1 loop, best of 3: 351 ms per loop
%timeit if_in_set(n, ks)
# 10 loop, best of 3: 57.6 ms per loop
%timeit if_in_tuple(n, ks)
# 1 loop, best of 3: 209 ms per loop
%timeit if_in_list(n, ks)
# 1 loop, best of 3: 214 ms per loop


ks = [-1] * m
%timeit if_or(n, ks)
# 1 loop, best of 3: 421 ms per loop
%timeit if_in_set(n, ks)
# 10 loop, best of 3: 54.4 ms per loop
%timeit if_in_tuple(n, ks)
# 1 loop, best of 3: 238 ms per loop
%timeit if_in_list(n, ks)
# 1 loop, best of 3: 237 ms per loop

Как видите, при достаточном коротком замыкании решение or работает так же быстро, как in в любом конкретном контейнере, но в целом использование set() является гораздо лучшей альтернативой, поскольку оно само себя зарекомендовало ( потому что он имеет O(1) время поиска, по сравнению с tuple или list, которые имеют O(N) время поиска) и не зависит от короткой ставки.

---

Наконец, Чтобы получить представление о том, почему or медленнее, давайте разберем if_or() и if_in_set(), используя dis:

• if_or()

import dis


dis.dis(if_or)

  2           0 SETUP_LOOP             110 (to 112)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                98 (to 110)
             12 STORE_FAST               3 (_)

  3          14 SETUP_LOOP              92 (to 108)
             16 LOAD_FAST                1 (ks)
             18 GET_ITER
        >>   20 FOR_ITER                84 (to 106)
             22 STORE_FAST               4 (k)

  4          24 LOAD_FAST                4 (k)
             26 LOAD_CONST               1 (0)
             28 COMPARE_OP               2 (==)
             30 POP_JUMP_IF_TRUE        20
             32 LOAD_FAST                4 (k)
             34 LOAD_CONST               2 (1)
             36 COMPARE_OP               2 (==)
             38 POP_JUMP_IF_TRUE        20
             40 LOAD_FAST                4 (k)
             42 LOAD_CONST               3 (2)
             44 COMPARE_OP               2 (==)
             46 POP_JUMP_IF_TRUE        20
             48 LOAD_FAST                4 (k)
             50 LOAD_CONST               4 (3)
             52 COMPARE_OP               2 (==)
             54 POP_JUMP_IF_TRUE        20
             56 LOAD_FAST                4 (k)
             58 LOAD_CONST               5 (4)
             60 COMPARE_OP               2 (==)
             62 POP_JUMP_IF_TRUE        20
             64 LOAD_FAST                4 (k)
             66 LOAD_CONST               6 (5)
             68 COMPARE_OP               2 (==)
             70 POP_JUMP_IF_TRUE        20
             72 LOAD_FAST                4 (k)
             74 LOAD_CONST               7 (6)
             76 COMPARE_OP               2 (==)
             78 POP_JUMP_IF_TRUE        20
             80 LOAD_FAST                4 (k)
             82 LOAD_CONST               8 (7)
             84 COMPARE_OP               2 (==)
             86 POP_JUMP_IF_TRUE        20
             88 LOAD_FAST                4 (k)
             90 LOAD_CONST               9 (8)
             92 COMPARE_OP               2 (==)
             94 POP_JUMP_IF_TRUE        20
             96 LOAD_FAST                4 (k)
             98 LOAD_CONST              10 (9)
            100 COMPARE_OP               2 (==)
            102 POP_JUMP_IF_FALSE       20

  5         104 JUMP_ABSOLUTE           20
        >>  106 POP_BLOCK
        >>  108 JUMP_ABSOLUTE           10
        >>  110 POP_BLOCK
        >>  112 LOAD_CONST               0 (None)
            114 RETURN_VALUE

• if_in_set()

import dis


dis.dis(if_in_set)

  9           0 SETUP_LOOP              38 (to 40)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                26 (to 38)
             12 STORE_FAST               3 (_)

 10          14 SETUP_LOOP              20 (to 36)
             16 LOAD_FAST                1 (ks)
             18 GET_ITER
        >>   20 FOR_ITER                12 (to 34)
             22 STORE_FAST               4 (k)

 11          24 LOAD_FAST                4 (k)
             26 LOAD_CONST              11 (frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}))
             28 COMPARE_OP               6 (in)
             30 POP_JUMP_IF_FALSE       20

 12          32 JUMP_ABSOLUTE           20
        >>   34 POP_BLOCK
        >>   36 JUMP_ABSOLUTE           10
        >>   38 POP_BLOCK
        >>   40 LOAD_CONST               0 (None)
             42 RETURN_VALUE

там вы можете видеть, что длинный третий блок if_or() с несколькими относительно дорогими COMPARE_OP вызовами заменяется одним COMPARE_OP звонок. Контейнер замораживается с помощью механизмов оптимизации Python.