[python] 파이썬의 목록은 어떻게 구현됩니까?

PYTHON / 글쓴이

연결된 목록입니까, 배열입니까? 나는 주변을 수색하고 사람들 만 추측하는 것을 발견했다. 내 C 지식은 소스 코드를 볼만큼 충분하지 않습니다.

답변

그것은의 동적 배열 . 실용적 증거 : 색인에 상관없이 색인 생성에는 시간이 많이 걸립니다 (물론 아주 작은 차이 (0.0013 µsec!)).

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

IronPython 또는 Jython에서 링크 된 목록을 사용하면 놀라 울 것입니다. 목록이 동적 배열이라는 가정하에 널리 사용되는 많은 라이브러리의 성능을 망칠 것입니다.

답변

실제로 C 코드는 매우 간단합니다. 하나의 매크로를 확장하고 관련이없는 주석을 정리하면 기본 구조는에 listobject.h있으며 목록을 다음과 같이 정의합니다.

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEAD참조 횟수와 유형 식별자를 포함합니다. 따라서 전체적으로 할당되는 벡터 / 배열입니다. 이러한 배열이 가득 찼을 때 크기를 조정하는 코드는입니다 listobject.c. 실제로 배열을 두 배로 늘리지는 않지만 할당하여 자랍니다.

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

newsize요청 된 크기는 매번 용량 에 따라 달라집니다 (필수 요소 수를 하나씩 지정하는 대신 임의의 수의 요소 allocated + 1를 사용할 수 있기 때문은 아닙니다 ).extendappend

Python FAQ 도 참조하십시오 .

답변

CPython에서 목록은 포인터의 배열입니다. 파이썬의 다른 구현은 다른 방법으로 저장하도록 선택할 수 있습니다.

답변

이것은 구현에 따라 다르지만 IIRC :

  • CPython은 포인터 배열을 사용합니다
  • 자이 썬은 ArrayList
  • IronPython은 분명히 배열을 사용합니다. 소스 코드 를 찾아서 찾을 수 있습니다 .

따라서 그들은 모두 O (1) 랜덤 액세스를 갖습니다.

답변

Laurent Luce의 기사 “Python list implementation”을 제안 합니다. 필자가 CPython에서 목록이 구현되는 방법을 설명 하고이 목적을 위해 훌륭한 다이어그램을 사용하기 때문에 정말 유용했습니다.

객체 C 구조 나열

CPython의 목록 오브젝트는 다음 C 구조로 표시됩니다. ob_item목록 요소에 대한 포인터 목록입니다. 할당은 메모리에 할당 된 슬롯 수입니다.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

할당 된 슬롯과 목록 크기의 차이를 확인하는 것이 중요합니다. 목록의 크기는 len(l)입니다. 할당 된 슬롯 수는 메모리에 할당 된 수입니다. 종종, 할당 된 크기가 크기보다 클 수 있음을 알 수 있습니다. realloc새 요소가 목록에 추가 될 때마다 호출 할 필요 가 없습니다.

…

추가

리스트에 정수를 추가합니다 : l.append(1). 무슨 일이야?
여기에 이미지 설명을 입력하십시오

계속해서 요소를 하나 더 추가합니다 : l.append(2). list_resizen + 1 = 2로 호출되지만 할당 된 크기가 4이므로 더 많은 메모리를 할당 할 필요가 없습니다. 정수 2 개를 더 추가 할 때도 마찬가지입니다 : l.append(3), l.append(4). 다음 다이어그램은 우리가 지금까지 가지고있는 것을 보여줍니다.

여기에 이미지 설명을 입력하십시오

…

끼워 넣다

1 번 위치에 새로운 정수 (5)를 삽입하고 l.insert(1,5)내부에서 어떤 일이 발생하는지 봅시다.여기에 이미지 설명을 입력하십시오

…

팝

당신이 마지막 요소를 팝업 할 때 : l.pop(), listpop()라고합니다. list_resize내부에서 호출 listpop()되고 새 크기가 할당 된 크기의 절반보다 작 으면 목록이 축소됩니다.여기에 이미지 설명을 입력하십시오

슬롯 4가 여전히 정수를 가리키는 것을 볼 수 있지만 중요한 것은 이제 4의 목록 크기입니다. 에list_resize() , 크기 – 1 = 4 – 1 = 3에서 6 개 슬롯 수축 및리스트의 새로운 크기가 현재 3 있도록 할당 된 슬롯의 절반 미만이다.

슬롯 3과 4가 여전히 일부 정수를 가리키는 것을 볼 수 있지만 중요한 것은 목록의 크기가 현재 3입니다.여기에 이미지 설명을 입력하십시오

…


Python 목록 제거 객체에는 특정 요소를 제거하는 방법이 l.remove(5)있습니다.여기에 이미지 설명을 입력하십시오

답변

에 따르면 문서 ,

파이썬의 목록은 실제로 가변 길이 배열이며 Lisp 스타일의 연결된 목록이 아닙니다.

답변

다른 사람들이 위에서 언급했듯이, 목록 (눈에 띄게 큰 경우)은 고정 된 양의 공간을 할당하고, 그 공간이 채워지면 더 많은 양의 공간을 할당하고 요소를 복사하여 구현됩니다.

일반성을 잃지 않고 메소드가 O (1)로 상각되는 이유를 이해하려면 = 2 ^ n 요소를 삽입했으며 이제 테이블을 2 ^ (n + 1) 크기로 두 배로 늘려야합니다. 이는 현재 2 ^ (n + 1) 작업을 수행하고 있음을 의미합니다. 마지막 사본에서는 2 ^ n 작업을 수행했습니다. 그 전에 우리는 2 ^ (n-1) … 8,4,2,1까지 줄였습니다. 이제 합산하면 1 + 2 + 4 + 8 + … + 2 ^ (n + 1) = 2 ^ (n + 2)-1 <4 * 2 ^ n = O (2 ^ n) = O (a) 총 삽입 (즉, O (1) 상각 시간). 또한 테이블이 삭제를 허용하는 경우 테이블 축소는 다른 요소 (예 : 3x)로 수행되어야합니다.