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

Ответы:

341

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

Алекс Мартелли
источник
17
Спасибо за полезный ответ! Есть ли нативные типы, для которых это не так?
Мванвеен
141

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

TimeComplexity Python Wiki Page

Джеймс Томпсон
источник
84

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

Джон Мачин
источник
3
Я думаю, что это наиболее подходящий ответ, поскольку он дает представление о деталях реализации.
AK
почему не lengthпоявляется в словаре dir(list)?
ViFI
это то, что я искал
Висах Виджаян
@ViFI Потому что это только пример. Показанная list.lenghtпеременная реализована на C, а не на Python.
Ковальский
73

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

Набор (набор-понимание доступно в 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
mechanical_meat
источник
1
Это не очень хороший показатель, хотя он показывает то, что мы уже знаем. Это потому, что диапазон (10) и диапазон (1000000) не должны быть O (1).
Неизвестно
3
Это, безусловно, лучший ответ. Вы должны просто добавить заключение на тот случай, если кто-то не осознает постоянное время.
santiagobasulto
4
Спасибо за комментарий. Я добавил примечание о сложности O (1) len(), а также исправил измерения, чтобы правильно использовать -sфлаг.
mechanical_meat
Важно отметить, что сохранение длины в переменной может сэкономить значительное количество вычислительного времени: python -m timeit -s "l = range(10000);" "len(l); len(l); len(l)"223 нсек на цикл python -m timeit -s "l = range(100);" "len(l)"66,2 нсек на цикл
Радостин Стоянов
16

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

РАХУЛ КУМАР
источник
3

Я думал, что len () в Python зависит от размера списка, поэтому я всегда сохраняю длину в переменной, если использую несколько раз. Но сегодня во время отладки я заметил атрибут __len__ в объекте списка, поэтому len () должен просто извлекать его, что делает сложность O (1). Так что я просто погуглил, если кто-то уже спросил это и наткнулся на этот пост.

АЮШ СЕНАПАТИ
источник
Но __len__это функция, а не переменная, которая представляет длину списка.
Ковальский
@ Kowalski да, len - это функция, но все, что она делает, это возвращает self.length
AYUSH SENAPATI
Но ваш пост ничего об этом не говорит. Кроме того, как вы узнали, что list.__len__функция работает в постоянном времени? Да, но не только потому, что это функция. Потому что это реализовано так.
Ковальский