최상의 답변
그 이름이 의미하는 것과는 달리, 파이썬 목록은 실제로 배열입니다. “오해의 소지가있는 이름과 같지 않음). 특히 지수 초과 할당이있는 동적 배열이므로 다음과 같은 코드가 선형 복잡성을 가질 수 있습니다.
lst = []
for i in xrange(0, 100000):
lst.append(i)
흥미롭게도 CPython은 1.125 * new\_size + 6 (또는 배열이 9 개 요소보다 작을 때 + 3)을 할당하기 때문에 매우 보수적입니다.이 1.125 상수는 다소 드물며 제가 말했듯이 매우 보수적이므로 일련의 추가 호출은 일반적이지 않습니다. 동적 배열의 구현은 일반적으로 2 또는 1.5와 같은 상수를 사용합니다 (방금 gcc / clang에서 std :: vector의 구현을 확인했고 2를 사용합니다. Microsoft 컴파일러의 구현이 1.5를 사용하는 것을 기억하는 것 같습니다. ). 나는 + 3과 + 6 상수가 어디에서 왔는지 모르겠지만,이 글을 쓴 사람은 + 3이 작은 배열에 대해 가장 좋은 정책이고 + 6이 다소 작은 배열에 가장 좋다는 것을 알아 냈다고 생각합니다 ( 즉, 100 개 미만) 큰 배열에서는 전혀 문제가되지 않았으므로 그대로 유지하면 안됩니다.
Jython 및 IronPython과 같은 대체 구현은 기본 동적 배열 클래스를 사용하는 것 같습니다. 언어 (각각 Java 및 C #)가 제공하므로 성능 특성이 동일합니다 (정확한 기본 클래스는 ArrayList for Jython 및 C # List for IronPython).
누군가 의견에서 어떻게 가능했는지 물었습니다. 이기종 유형의 요소 배열을 갖습니다 ([1, “hello”]는 Python에서 유효한 목록입니다). 이 질문에 대한 대답은 배열이 객체 자체가 아닌 포인터를 기술적으로 저장하므로 배열에 특정 크기의 요소 만 포함 할 수 있다는 것입니다. 기본 구현의 모든 위치에 포인터를 갖는 것은 동적 유형 언어의 일반적인 기능이며 실제로 포인터가없는 척하려는 모든 언어의 경우입니다.
답변
Adrien Lucas Ecoffet가 말했듯이, 파이썬 목록은 가변 길이 배열 일뿐입니다. cpython의 소스 코드를 파고 매크로를 확장하면 기본 구조는 다음과 같이 정의됩니다.
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
여기에서 주석을 정리했습니다. 원본 참조 여기에 코드를 입력하세요. 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEAD에는 참조 횟수와 유형 식별자가 포함됩니다. 따라서 “벡터 / 배열 초과 할당합니다. 이러한 배열이 꽉 찼을 때 크기를 조정하는 코드는 listobject.c 에 있습니다. list\_resize를 너무 많이 호출하지 않도록 메모리를 과도하게 할당합니다. 성장 패턴 목록 : 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…
arguments: list object, new size
returns: 0 if OK, -1 if not
list\_resize:
new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
new\_allocated += newsize
resize ob\_item (list of pointers) to size new\_allocated
return 0
추가, 삽입, 제거, 확장 등을 포함하여 나열된 Python 목록 구현의 모든 방법을 보려면이 훌륭한 블로그 게시물을 참조하세요.