Python의 내부 목록, 액세스 및 크기 조정 런타임

Question

파이썬의 []은 목록입니까 배열입니까?
배열과 같은 인덱스 O (1)의 액세스 시간 또는 목록과 같은 O (n)입니까?
O (1)을리스트처럼 추가하거나 O (n)을 배열처럼 추가하거나, 액세스 및 크기 조정을 위해 O (1)을 관리 할 수있는 하이브리드입니까?

I read here 배열 액세스는 Python에서 실제로 느립니다. 그러나 필자가 사전 (파이썬의 사전은 정말 빠르다고 가정)과리스트를 모두 사용하여 재귀 적 피보나치 절차의 메모 버전을 작성했을 때, 그들은 같은 시간을 가졌다. 왜 이런거야?

파이썬 튜플이 파이썬 목록보다 빠른 액세스 시간을 갖고 있습니까?

Answer 1

파이썬의 []은 배열으로 구현되어 있으며 링크 된 목록이 아닙니다. 크기 조정은 O (n)이지만 크기 조정은 매우 드물기 때문에 은 0 (1)으로 조정됩니다. 어떻게 작동하는지 잘 모르겠 으면 Wikipedia entry on dynamic arrays을 읽어보십시오. 파이썬의 목록은 매번 2 씩 확장되지는 않지만 그보다 조금 더 복잡합니다. 그러나 확장은 여전히 ​​상각 된 O (1)을 추가하도록 설계되었습니다.

그러나 삽입은 n 항목을 이동해야하기 때문에 항상 비효율적 인 O (n)입니다.

튜플은 목록보다 빠르지 않습니다. 두꺼운 부분 (*)의 불변 목록 일뿐입니다.

사전 테스트 관련 : 정확한 구현에 따라 목록에있는 캐싱은 사전보다 빠릅니다. 그러나 Python의 dicts는 매우 최적화되어 있으며, 특히 소량의 키가 훌륭하게 수행됩니다.

PyObject * 
PyList_GetItem(PyObject *op, Py_ssize_t i) 
{ 
    if (!PyList_Check(op)) { 
     PyErr_BadInternalCall(); 
     return NULL; 
    } 
    if (i < 0 || i >= Py_SIZE(op)) { 
     if (indexerr == NULL) 
      indexerr = PyString_FromString(
       "list index out of range"); 
     PyErr_SetObject(PyExc_IndexError, indexerr); 
     return NULL; 
    } 
    return ((PyListObject *)op) -> ob_item[i]; 
} 

을 그리고 이것은 튜플의이다 :

PyObject * 
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i) 
{ 
    if (!PyTuple_Check(op)) { 
     PyErr_BadInternalCall(); 
     return NULL; 
    } 
    if (i < 0 || i >= Py_SIZE(op)) { 
     PyErr_SetString(PyExc_IndexError, "tuple index out of range"); 
     return NULL; 
    } 
    return ((PyTupleObject *)op) -> ob_item[i]; 
} 

당신이 볼 수 있듯이, 그들은 '

---

(*) 다음 목록의 파이썬 2.6에서 C 기능 "항목을 얻을"입니다 거의 동일합니다. 결국, 일부 유형 및 바운드 검사 후에는 인덱스가있는 간단한 포인터 액세스입니다.

[참조 : Python documentation on Time Complexity for data type operations]

Answer 2

파이썬 데이터 유형의 시간 복잡도를 개략적 큰 목록 here있다. 귀하의 경우 아이템 검색은 O (1) 시간이어야합니다.

Answer 3

튜플 은 목록보다 빠릅니다. 나는 기본적인 구현을 모른다. 나는 '다이빙으로 파이썬'을 읽었습니다. 관련 발췌문 :

"튜플은 목록보다 빠릅니다. 일정한 값 집합을 정의하고 있다면이 튜토리얼을 사용하여 작업 할 것입니다 그것을 통해 iterate, 목록 대신 튜플을 사용합니다. "

Answer 4

파이썬의 목록은 자바의 ArrayList과 비슷합니다. 목록 및 튜플에서 항목을 가져 오는 access time은 O(1)이어야합니다.Norvig의 기사에 따르면 Python의 목록은 Java의 Vector 또는 Lisp의 Adjustable Array와 비슷하지만 실제로는 더 많은 공간이 필요하지만 액세스 시간은 O(1)입니다.