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

Ответ 1

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

Ответ 2

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

Страница Wiki для TimeComplexity

Ответ 3

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

Ответ 4

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

Ответ 5

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

Ответ 6

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