Python len() 함수의 내부 동작 원리

Python에서 객체의 길이를 구할 수 있는 빌트인 함수 len()은 어떻게 작동하는 걸까?

객체의 길이라 하면 표현이 모호하므로

iterable 자료형의 원소 개수가 더 정확하겠다.

대표적인 iterable 자료형으로 List를 예로 들자.

만약 List 객체 a의 원소 개수가 2,500개이고,

[0]주소부터 시작해서 [2499]까지 순회하며 count 변수를 1씩 올린다면,

len 함수는 O(n)의 시간복잡도를 가진다.

Python에서는 len()을 호출할 때마다 객체 내 Item을 반복하면서 돌며
count를 변수를 올리는 형태로 계산하지 않는다.

대신 __len__() 이라는 이름의 매직메서드를 이용하는데,

이 매직 메서드는 length를 attribute로서 사용한다.

list는 iterable 데이터 구조의 클래스 안에 정의되어 있으며

__len__ 메서드는 카운터 역할을 한다.

list 자료형이 정의거나 저장될 때 자동으로 증가한다.

len을 호출할 때는 순회하며 길이를 찾는 명령어가 아니라

이미 저장되어 있는 len값을 묻는 것과 같다.

따라서, O(1)시간 안에 해결할 수 있다.

len함수를 호출했을 때 최악실행시간만 보면

꽤 경제적으로 생각될 수 있으나,

데이터가 정의 될 때 len 값 또한 정의되기 때문에

인터프리터에 부담이 갈 수 있다.

특히 큰 값이 정의될 때 그렇다.
( 단순히 값이 수학적으로 큰 것이 아니라 정보량이 많다는 의미에서 )

이는 Python 환경에서 Item 개수가 큰 값을 입력받을 때
다른 언어에 비해 느린 요인 중 하나다.

Computation suite