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

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

Ответы на вопрос(5)

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

TimeComplexity Python Wiki Page

 03 авг. 2017 г., 21:49
Это правда для (юникод) жало тоже? Ключевое слово кодовых точек.

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

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

List:
$ 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
Tuple:
$ 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
String:
$ 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
Dictionary (dictionary-comprehension available in 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
Array:
$ 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-comprehension available in 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
 21 янв. 2013 г., 14:14
Это, безусловно, лучший ответ. Вы должны просто добавить заключение на тот случай, если кто-то не осознает постоянное время.
 12 июл. 2009 г., 07:45
Это не очень хороший тест, хотя он показывает то, что мы уже знаем. Это потому, что диапазон (10) и диапазон (1000000) не должны быть O (1).
 21 янв. 2013 г., 18:21
Спасибо за комментарий. Я добавил примечание о сложности O (1)len(), а также исправил измерения, чтобы правильно использовать-s флаг.

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

len is an O(1) because in your RAM, lists are stored as tables (серия смежных адресов). Чтобы знать, когда стол останавливается, компьютеру нужны две вещи: длина и начальная точка. Вот почему len () является O (1), компьютер хранит значение, поэтому ему просто нужно его найти.

Решение Вопроса

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

 16 мар. 2012 г., 04:41
Спасибо за полезный ответ! Есть ли нативные типы, для которых это не так?

Ваш ответ на вопрос