[파이썬] len함수 코스트(비용)

<질문>

비용은 얼마입니까len()Python 내장 함수? (목록/튜플/문자열/사전)

---

<답변1>

그것은오(1)(요소의 실제 길이에 의존하지 않는 일정한 시간 - 매우 빠름) 언급한 모든 유형에 대해set및 기타array.array.

---

<답변2>

부름len()해당 데이터 유형에 대한오(1)안에CPython, Python 언어의 공식적이고 가장 일반적인 구현입니다. 다음은 CPython에서 다양한 함수의 알고리즘 복잡성을 제공하는 표에 대한 링크입니다.

TimeComplexity Python Wiki Page

---

<답변3>

이러한 모든 개체는 자체 길이를 추적합니다. 길이를 추출하는 시간은 짧고(big-O 표기법의 O(1)) 대부분 [대략적인 설명, C 용어가 아닌 Python 용어로 작성됨]: 사전에서 "len"을 찾아 다음으로 디스패치합니다. 객체를 조회할 built_in len 함수__len__방법과 호출 ...해야 할 일은return self.length

---

<답변4>

아래 측정은 다음과 같은 증거를 제공합니다.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

$ 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

$ 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

$ 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

---

<답변5>

len은 RAM에 목록이 테이블로 저장되기 때문에 O(1)입니다.(일련의 연속 주소). 테이블이 언제 멈추는지 알기 위해 컴퓨터는 길이와 시작점이라는 두 가지가 필요합니다. 그렇기 때문에 len()은 O(1)이고 컴퓨터는 값을 저장하므로 찾아보기만 하면 됩니다.