Всем привет!
Никогда не задумывались, быстро ли работает функция len() в Python при работе со списками? Возможно, что не задумывались, потому что на этой функции Python никогда не зависал и не задерживал выполнение программы :) Как вы думаете, почему? Ведь списки, строки и прочие коллекции иногда бывают весьма значительных размеров.
Я решил провести небольшое исследование и написал скрипт, который генерирует несколько списков размером от 10 до 4096000000 элементов и попробовал посчитать время выполнения функции len() на каждый список. Как вы думаете, какие были результаты?
На графике по оси X приведен размер списка, а по оси Y время подсчета его длины, умноженное 1000 (чтобы не работать с совсем уж маленькими числами). Итак, сразу же видно, что скорость взятия длины не превышает 0,006 / 1000 секунд, даже на списке размером более 4 млрд элементов!
Как работает эта функция? На первый взгляд кажется, что самый простой алгоритм – при вызове функции len() пробежаться по списку и посчитать, сколько элементов в него входит. На деле же все чуть-чуть хитрее – дело в том, что объект списка всегда хранит свою длину. То есть, изначальный подсчет длины происходит в момент создания списка и выделения памяти под него, и длина объекта хранится в отдельной переменной внутри объекта. В дальнейшем, при модификации списка – при добавлении или удалении элементов, счетчик меняется в соответствии с изменениями.
Поэтому при вызове функции len(), Python просто вызывает внутренний метод объекта, чтобы получить значение длины, которое уже сохранено, а не производит подсчет.
Хочу отметить, что встроенная библиотека в Python написана на языке C, и структуры данных, тот же list, тоже описан в C. Поэтому внутреннее устройство метода len() и объекта list не совсем уместно описывать в терминах Python :)
Если вы хотите начать или продолжить изучать Python и не знаете, за что зацепиться – рекомендую зайти на сайт моего курса https://myfriendcourse.ru и записаться на первое бесплатное занятие – можно обучаться в группах, или индивидуально.
Мы не только учимся работать с конструкциями языка, но и разбираем, как они устроены изнутри :)
