Стоимость функции len()

вызов len () для этих типов данных равен O (1) in CPython, наиболее распространенная реализация языка Python. Вот ссылка на таблицу, которая обеспечивает алгоритмическую сложность многих различных функций в CPython:

TimeComplexity Python Wiki Page

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

в отношении timeit: если -s флаг используется и две строки передаются в timeit первая строка выполняется только один раз и не приурочен.

список:

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

Кортеж:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

строку:

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

словарь (словарь-понимание существующих в 2.7+):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

время:

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

Set (set-понимание доступно в 2.7+):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

Deque:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

все эти объекты отслеживают свою собственную длину. Время для извлечения длины невелико (O (1) в нотации big-O) и в основном состоит из [грубого описания, написанного в терминах Python, а не в терминах C]: найдите "len" в словаре и отправьте его в функцию built_in len, которая будет искать объект __len__ метод и вызвать, что ... все, что он должен сделать, это return self.length

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