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

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

---

연결된 목록입니까, 배열입니까? 나는 주변을 검색하고 추측하는 사람들 만 찾았습니다. 내 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) 임의 액세스 권한이 있습니다.

---

설명서 에 따르면 ,

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

---

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

객체 C 구조 나열

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

typedef 구조체 {

PyObject_VAR_HEAD

PyObject ** ob_item;

Py_ssize_t 할당;

} PyListObject;

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

...

추가

리스트에 정수를 추가합니다 : l.append (1). 무슨 일이야?

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

...

끼워 넣다

위치 1 : l.insert (1,5)에 새 정수 (5)를 삽입하고 내부적으로 어떤 일이 발생하는지 살펴 보겠습니다.

...

팝

마지막 요소 인 l.pop ()을 팝업하면 listpop ()이 호출됩니다. list_resize는 listpop () 내에서 호출되며 새 크기가 할당 된 크기의 절반보다 작 으면 목록이 축소됩니다.

You can observe that slot 4 still points to the integer but the important thing is the size of the list which is now 4. Let’s pop one more element. In list_resize(), size – 1 = 4 – 1 = 3 is less than half of the allocated slots so the list is shrunk to 6 slots and the new size of the list is now 3.

You can observe that slot 3 and 4 still point to some integers but the important thing is the size of the list which is now 3.

...

Remove Python list object has a method to remove a specific element: l.remove(5).

---

As others have stated above, the lists (when appreciably large) are implemented by allocating a fixed amount of space, and, if that space should fill, allocating a larger amount of space and copying over the elements.

To understand why the method is O(1) amortized, without loss of generality, assume we have inserted a = 2^n elements, and we now have to double our table to 2^(n+1) size. That means we're currently doing 2^(n+1) operations. Last copy, we did 2^n operations. Before that we did 2^(n-1)... all the way down to 8,4,2,1. Now, if we add these up, we get 1 + 2 + 4 + 8 + ... + 2^(n+1) = 2^(n+2) - 1 < 4*2^n = O(2^n) = O(a) total insertions (i.e. O(1) amortized time). Also, it should be noted that if the table allows deletions the table shrinking has to be done at a different factor (e.g 3x)

---

파이썬의 목록은 배열과 유사하며 여러 값을 저장할 수 있습니다. 목록은 변경할 수 있으므로 변경할 수 있습니다. 더 중요한 것은리스트를 만들 때 파이썬은 자동으로 해당리스트 변수에 대한 reference_id를 만듭니다. 다른 변수를 지정하여 변경하면 기본 목록이 변경됩니다. 예를 들어 봅시다 :

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

우리는 추가 my_list하지만 기본 목록이 변경되었습니다. 그 의미의 목록은 참조로 사본 목록으로 지정되지 않았습니다.

참고 URL : https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented