Почему не установлены литералы O (1) для операций "in"?

Question

Довольно часто можно протестировать множество констант по отношению к переменной, выполнив

if x in ('foo', 'bar', 'baz'):

вместо

if x == 'foo' or x == 'bar' or x == 'baz':

Я часто видел "use {'foo', 'bar', 'baz'} вместо этого"('foo', 'bar', 'baz') для производительности O (1) ", что имеет смысл, но тестирование показывает довольно странные результаты.

%timeit 1 in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
27.6 ns ± 2.35 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

%timeit 10 in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
136 ns ± 4.04 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

%timeit 0 in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
186 ns ± 26.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Почему поиск для заданных литералов не является постоянным временем?

Answer 1

Заданный поиск в среднем является операцией O (1).Он не должен последовательно изменять производительность в зависимости от того, какой элемент набора вы проверяете, за исключением случайной степени в некоторой степени, поскольку некоторые значения могут иметь хеш-коллизии с другими значениями, и поэтому поиск может занять больше времени.Различия во времени, которые вы наблюдаете при поиске различных значений в своих небольших наборах, почти наверняка являются совпадениями или шумом, который вы принимаете за данные.

Обратите внимание, что вы не просто являетесь участником набора времени в своих тестах,Вы также каждый раз создаете новый набор, и это обычно операция O (N) (где N - количество значений в наборе).В некоторых особых ситуациях заданный литерал может быть создан за время O (1), так как компилятор Python выполняет оптимизацию, чтобы заменить изменяемый объект set неизменным объектом frozenset, который он заранее вычислял как константу.Это происходит только в ситуации, когда компилятор ожидает воссоздание объекта целую кучу раз, и когда он может сказать, что никакая ссылка на заданный объект не может просочиться из области кода, в которой он выполняется.Например, набор, используемый в предложении if выражения понимания или генератора, может получить постоянную обработку:

[foo(x) for x in some_iterable if x in {0, 1, 2, 3, 4, 5, 6, 7, 9}]

В последних версиях CPython здесь литерал набора всегда будет ссылаться на константу frozenset, которое не нужно создавать заново для каждого значения x, полученного из some_iterable.Но вы, вероятно, не должны полагаться на это поведение, так как другие интерпретаторы Python и даже другие версии CPython могут не выполнять такую ​​же оптимизацию.

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

Попробуйте более конкретный тест (с учетом создания множества), например:

import timeit, random

big_set = set(range(1000000))

for x in random.sample(range(1000000), 10):
    print('looking up', x, 'took', timeit.timeit(lambda: x in big_set), 'seconds')

Answer 2

Я не получаю ваши результаты:

python -m timeit "(-1) in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"
10000000 loops, best of 3: 0.0238 usec per loop

python -m timeit "0 in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"
10000000 loops, best of 3: 0.0235 usec per loop

python -m timeit "9 in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"
10000000 loops, best of 3: 0.0208 usec per loop

Что касается вашего вопроса о разнице в создании set() и {}, вы можете увидеть разницу в байт-коде:

Установить литерал:

from dis import dis
print(dis("9 in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"))

Вывод:

          0 LOAD_CONST               0 (9)
          2 LOAD_CONST              10 (frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}))
          4 COMPARE_OP               6 (in)
          6 RETURN_VALUE

Использование функции:

print(dis("9 in set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])"))

Вывод:

          0 LOAD_CONST               0 (9)
          2 LOAD_NAME                0 (set)
          4 LOAD_CONST               1 (0)
          6 LOAD_CONST               2 (1)
          8 LOAD_CONST               3 (2)
         10 LOAD_CONST               4 (3)
         12 LOAD_CONST               5 (4)
         14 LOAD_CONST               6 (5)
         16 LOAD_CONST               7 (6)
         18 LOAD_CONST               8 (7)
         20 LOAD_CONST               9 (8)
         22 LOAD_CONST               0 (9)
         24 BUILD_LIST              10
         26 CALL_FUNCTION            1
         28 COMPARE_OP               6 (in)
         30 RETURN_VALUE

Оба компилируют set, но python сразу может распознать буквальный набор как литерал (и оптимизирует его для создания фрозенцет, поскольку он знает, что нет необходимости в добавлении и удалении), в то время как ему нужно создать список,загрузить функцию set, а затем вызвать функцию из списка.Однако эта разница только в создании набора.Это не повлияет на операцию in.

Answer 3

Ну, пара вещей здесь.

1. set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) очень медленный, потому что он может сначала создать список.Я думаю, в 3.7+ есть некоторые оптимизации, но все равно.Из-за этого литералы наборов быстрее.
2. «проверка первого члена еще немного медленнее» - вещь о наборах - это не волшебно O(1).Проверка набора элементов: хэш + по модулю + сравнение хеша + запасные варианты для столкновения / удаления.Не существует такого понятия, как «первый член».
3. Кортежи превосходят наборы на небольших данных - потому что наборы используют большое количество машин.Это O(1), но константа выше значения O(N) в некотором диапазоне.Профилируйте ваш код, например, длиной 10 ** 6, и вы увидите разницу

4. Синхронизация с литералами - странная идея, обычно быстрая проверка членства использует уже созданные контейнеры:

   t = tuple(range(10**6))
   s = set(range(10**6))
   %timeit 999999 in t
   11.9 ms ± 92 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
   
   %timeit 999999 in s
   52 ns ± 0.538 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
   

---

Дополнительное замечание по тестированию асимптотической сложности - вы всегда должны проверять величину роста, необработанные данные ничего не значат.Т.е.

x = 1; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
168 ns ± 22.9 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit (-1) in s
38.3 ns ± 0.46 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

x = 2; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
1.1 µs ± 17.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit (-1) in s
37.7 ns ± 0.101 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

x = 4; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
107 µs ± 860 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit (-1) in s
39 ns ± 1.66 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

x = 6; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
10.8 ms ± 114 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit (-1) in s
38 ns ± 0.333 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

, чтобы вы могли ясно видеть, что здесь является линейной и постоянной величиной.

Answer 4

Вы тестируете как конструкцию набора , так и поиска.Давайте попробуем эксперименты снова, но построим a только один раз.Во-первых, вот кортеж:

$ python -m timeit -s 'a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)' -- '0 in a'
10000000 loops, best of 5: 22.6 nsec per loop

Поиск последнего элемента выполняется медленнее:

$ python -m timeit -s 'a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)' -- '9 in a'
2000000 loops, best of 5: 136 nsec per loop

Как и поиск пропущенных значений:

$ python -m timeit -s 'a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)' -- '-1 in a'
2000000 loops, best of 5: 132 nsec per loop

set.__contains__ на намного лучше после того, как объект сконструирован:

$ python -m timeit -s 'a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}' -- '0 in a'
10000000 loops, best of 5: 26.3 nsec per loop

Как и ожидалось, порядок не имеет значения:

$ python -m timeit -s 'a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}' -- '9 in a'
10000000 loops, best of 5: 26.1 nsec per loop

Также не выполняется проверка на отсутствие значений:

$ python -m timeit -s 'a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}' -- '-1 in a'
10000000 loops, best of 5: 26.4 nsec per loop

Answer 5

Вы, похоже, не понимаете значения алгоритмической сложности - вы не проверяли эту характеристику. Сложность описывает асимптотическое требование времени, поскольку входной размер стремится к бесконечности.

Ваше тестирование только для одного входного размера: 10 элементов.Вы делаете тест на лучшие и худшие случаи.однако, чтобы работать в направлении алгоритмической сложности, вам необходимо извлечь шаг инициализации из синхронизации, а затем сравнить производительность при различных входных размерах: возможно, степени 10, в диапазоне от 10 до 10 ** 12.