Какова стоимость len()
функции для встроенных Python? (список / Кортеж / строка / словарь)
290
Какова стоимость len()
функции для встроенных Python? (список / Кортеж / строка / словарь)
Это O (1) (постоянное время, не зависящее от фактической длины элемента - очень быстро) для каждого типа, который вы упомянули, плюс set
и другие, такие как array.array
.
Вызов len () для этих типов данных - это O (1) в CPython , самой распространенной реализации языка Python. Вот ссылка на таблицу, которая обеспечивает алгоритмическую сложность множества различных функций в CPython:
TimeComplexity Python Wiki Page
источник
Все эти объекты отслеживают свою собственную длину. Время для извлечения длины невелико (O (1) в нотации big-O) и в основном состоит из [грубого описания, написанного в терминах Python, а не в терминах C]: найдите «len» в словаре и отправьте его в Встроенная функция len, которая ищет метод объекта
__len__
и вызывает его ... все, что ему нужно сделать, этоreturn self.length
источник
length
появляется в словареdir(list)
?list.lenght
переменная реализована на C, а не на Python.Приведенные ниже измерения свидетельствуют о том, что
len()
O (1) используется для часто используемых структур данных.Примечание относительно
timeit
: когда используется-s
флаг и передаются две строкиtimeit
первой строке, выполняется только один раз и не рассчитывается по времени.Список:
Кортеж:
Строка:
Словарь (словарь-понимание доступно в 2.7+):
Массив:
Набор (набор-понимание доступно в 2.7+):
Deque:
источник
len()
, а также исправил измерения, чтобы правильно использовать-s
флаг.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 нсек на циклlen - это O (1), потому что в вашей оперативной памяти списки хранятся в виде таблиц (серии смежных адресов). Чтобы знать, когда стол останавливается, компьютеру нужны две вещи: длина и начальная точка. Вот почему len () - это O (1), компьютер хранит значение, поэтому ему просто нужно его найти.
источник
Я думал, что len () в Python зависит от размера списка, поэтому я всегда сохраняю длину в переменной, если использую несколько раз. Но сегодня во время отладки я заметил атрибут __len__ в объекте списка, поэтому len () должен просто извлекать его, что делает сложность O (1). Так что я просто погуглил, если кто-то уже спросил это и наткнулся на этот пост.
источник
__len__
это функция, а не переменная, которая представляет длину списка.list.__len__
функция работает в постоянном времени? Да, но не только потому, что это функция. Потому что это реализовано так.