Сложность len() в отношении наборов и списков

Ответ 1

Во-первых, вы не измеряли скорость len(), вы измерили скорость создания списка/набора вместе со скоростью len().

Используйте аргумент --setup timeit:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop

Заявления, которые вы передаете --setup, выполняются перед измерением скорости len().

Во-вторых, следует отметить, что len(a) - довольно быстрый оператор. Процесс измерения его скорости может подвергаться "шуму". Учтите, что код, выполняемый (и измеренный) по времени, эквивалентен следующему:

for i in itertools.repeat(None, number):
    len(a)

Поскольку и len(a), и itertools.repeat(...).__next__() являются быстрыми операциями, и их скорости могут быть схожими, скорость itertools.repeat(...).__next__() может влиять на тайминги.

По этой причине вам лучше измерить len(a); len(a); ...; len(a) (повторяется 100 раз или около того), чтобы тело цикла for занимало значительно большее количество времени, чем итератор:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop

(Результаты по-прежнему говорят, что len() имеет одинаковые характеристики в списках и наборах, но теперь вы уверены, что результат верен.)

В-третьих, верно, что "сложность" и "скорость" связаны, но я считаю, что вы путаете. Тот факт, что len() имеет сложность O (1) для списков и наборов, не означает, что он должен работать с одинаковой скоростью в списках и наборах.

Это означает, что в среднем, независимо от того, насколько длинным является список a, len(a) выполняет одно и то же асимптотическое число шагов. И независимо от того, сколько времени установлено b, len(b) выполняет одно и то же асимптотическое число шагов. Но алгоритм вычисления размера списков и наборов может быть другим, что приводит к различным характеристикам (timeit показывает, что это не так, однако это может быть возможностью).

Наконец,

Если создание заданного объекта занимает больше времени по сравнению с созданием списка, какова будет основная причина?

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

В частности, при построении набора вам нужно вычислить хеши, построить хеш-таблицу, посмотреть ее, чтобы избежать вставки повторяющихся событий и т.д. Напротив, списки в CPython реализуются как простой массив указателей, который malloc() ed и realloc() ed при необходимости.

Ответ 2

Соответствующие строки http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640

640     static Py_ssize_t
641     set_len(PyObject *so)
642     {
643         return ((PySetObject *)so)->used;
644     }

и http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431

431     static Py_ssize_t
432     list_length(PyListObject *a)
433     {
434         return Py_SIZE(a);
435     }

Оба являются только статическим поиском.

Так в чем разница, которую вы можете спросить. Вы также измеряете создание объектов. И это немного больше времени, чтобы создать набор, чем список.

Ответ 3

Используйте это с флагом -s для timeit без учета первой строки:

~$ python -mtimeit -s "a=range(1000);" "len(a)"
10000000 loops, best of 3: 0.0424 usec per loop
                           ↑ 

~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)"
10000000 loops, best of 3: 0.0423 usec per loop
                           ↑ 

Теперь он учитывает только функцию len, и результаты практически совпадают, поскольку мы не учитывали время создания набора/list.

Ответ 4

Да, вы правы, это больше из-за различного времени, необходимого для создания объектов set и list с помощью python. В качестве более справедливого эталона вы можете использовать модуль timeit и передать объекты с помощью аргумента setup:

from timeit import timeit

print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)")
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000")

результат:

1st:  0.04927110672
2nd :  0.0530669689178

И если вы хотите знать, почему это так, давайте рассмотрим мир python. Фактически заданный объект использует таблицу хешей а хэш-таблица использует хеш-функцию для создания хеш-значений элементов и отображения их в значениях и в эта сделка, вызывающая функцию и вычисляющая хэш-значения, и некоторые другие дополнительные задачи потребуют много времени. Хотя для создания списка python просто создайте последовательность объектов, к которым вы можете получить доступ к ним с индексацией.

Подробнее о функции set_lookkey вы можете узнать из исходного кода Cpython.

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

<суб > потому что обозначение big O описывает ограничение поведения функции и не показывает точное уравнение сложности. Например, сложность следующих уравнений f(x)=100000x+1 и f(x)=4x+20 равна O (1) и это означает, что оба являются линейными уравнениями bur, поскольку вы можете видеть, что первая функция имеет значительно больший наклон, и для одного входа они будут давать разные результаты.

суб >

Ответ 5

Позвольте мне привести здесь отличные ответы: O(1) сообщает вам о порядке роста в отношении размера ввода.

O(1), в частности, означает только постоянное время относительно размера ввода. Метод может всегда принимать 0,1 с для любого ввода, а другой может занять 1000 лет для любого ввода, и оба они будут O(1)

В этом случае, хотя документация имеет некоторую степень двусмысленности, это означает, что метод принимает примерно одно и то же время для обработки списка размера 1, как требуется для обработки списка размеров 1000; аналогично, для обработки словаря размера 1 требуется одно и то же время, как требуется для обработки словаря размера 1000.

Никакой гарантии не предоставляется в отношении разных типов данных.

Это неудивительно, так как реализация len() в какой-то момент вниз стек вызовов может различаться в зависимости от типа данных.

Кстати, эта двусмысленность устранена в статически типизированных языках, где ClassA.size() и ClassB.size() для всех целей и других методов используются два разных метода.

Ответ 6

Удалите оператор len(a). Результат почти такой же. Набор должен быть хэширован для сохранения только отдельных элементов, поэтому он медленнее.

Ответ 7

Многие отметили, что O (1) не относится к производительности на разных типах данных, а о производительности как функции разных размеров ввода.

Если вы пытаетесь проверить O (1) -ness, вы будете искать что-то большее, как

~$python -m timeit --setup "a=list(range(1000000))" "len(a)"
10000000 loops, best of 3: 0.198 usec per loop

~$python -m timeit --setup "a=list(range(1))" "len(a)"
10000000 loops, best of 3: 0.156 usec per loop

Большие данные или небольшие данные, время, проведенное, очень похоже. В других сообщениях это отделяет время установки от времени тестирования, но не позволяет уменьшить шум времени len-time vs loop-time.