[python] len()은 어떻게 O(1)으로 동작할까?

C언어에서는 직접 구현해야 하는 기능들을 파이썬에서는 내장함수을 통해 쉽게 접근이 가능하다. 그런데 파이썬의 편리한 함수들을 사용하다보면 시간복잡도에 대한 우려를 하게 된다. 파이썬이 워낙 사용자에게 친화적인 언어이다보니 나도 모르게 컴퓨터에게는 과중한 일을 시키고 있을지도 모르니 말이다. C언어에서 배운 구현 방식을 통해 파이썬에서 사용하는 함수들의 시간복잡도를 예상하곤 하는데, 그러던 중 파이썬에서 자주 사용되는 len() 함수의 시간복잡도에 대해 궁금증이 생겼다. 분명 C언어에서 리스트의 길이를 구할 때는 리스트를  traverse하면서 길이를 구하게 되는데, 이 경우 시간복잡도가 해당 함수를 불러올 때마다 O(N)이 될 것이고 이렇게 되면 함수를 매번 호출하기가 부담스러워질 수 밖에 없다. 여러 파이썬 코드들을 보면 for문 안에 버젓이 len()함수가 여러번 호출되는 것이 꽤 의문스러웠다. 혼자 머리를 이리저리 굴려보며 떠올린 아이디어는 파이썬의 클래스 중 속성 부분에 리스트의 길이가 저장되는 것이었다. 더 정확한 해답을 찾아보고자 구글에 서치해보았고, 아래와 같은 자료를 발견할 수 있었다.

 

Internal Working of the len() Function in Python - GeeksforGeeks

위 자료의 내용을 요약하면 iterable data structure(string, array, tuple, etc) 클래스의 속성 중 하나로 자료구조의 길이(length)가 저장되며, len()함수를 호출하는 것은 메서드 중 '__len()__()'를 호출하는 것과 같고 이 메서드는 counter로 작용하여 데이터가 저장될 때마다 길이를 업데이트하는 방식으로 작용하는 것이다.