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

Question

Какова стоимость функции len() для встроенных Python? (Список / Кортеж / строка / словарь)

Answer 1

Это O (1) (постоянное время, не зависит от фактической длины элемента - очень быстро) для каждого типа, который вы упомянули, плюс set и другие, такие как array.array.

Answer 2

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

TimeComplexity Python Wiki Page

Answer 3

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

Answer 4

Приведенные ниже измерения подтверждают, что 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 (набор-понимание доступно в 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

Answer 5

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