[Python]리스트 (List): 파이썬에서의 동작 원리

JUNYOUNG·2024년 11월 27일
python

실무 Spring, Python, DB, 인프라

목록 보기
5/15
post-thumbnail

이전 글에서 나는 파이썬에서의 복사를 다루며 리스트와 딕셔너리에 대해 언급했다.
이후 곰곰이 생각해보니, 리스트라는 자료구조가 내부적으로 어떻게 동작하는지 궁금해졌다.
조사한 결과, 파이썬의 리스트는 listobject.c 에 C 언어로 구현되어 있었다.
이 코드를 모두 읽어보진 않았지만, 주요 동작 방식과 성능 최적화의 원리를 다음과 같이 정리할 수 있었다.

리스트란?

리스트는 동적 배열(Dynamic Array) 기반의 자료구조다. 데이터를 순서대로 저장하며, 필요에 따라 메모리를 동적으로 확장한다. 리스트는 파이썬에서 가장 기본적이고 많이 사용되는 자료구조로, 데이터의 추가, 삭제, 조회 작업을 효율적으로 처리하도록 설계되었다.

리스트의 구조

리스트는 연속된 메모리 공간에 데이터를 저장한다. 파이썬의 리스트는 C 언어로 구현되어 있으며, 내부적으로 다음과 같은 구조를 가진다.

// hhttps://github.com/python/cpython/blob/main/Include/cpython/listobject.h 
typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;  // 데이터를 가리키는 포인터 배열
    Py_ssize_t allocated;  // 할당된 메모리 크기
} PyListObject;
  1. ob_item: 데이터(파이썬 객체)를 가리키는 포인터 배열이다.
  2. allocated: 리스트에 할당된 메모리 크기다. 추가 작업이 많을 경우, 여유 공간이 부족하면 재할당이 필요하다.

리스트의 주요 연산

1. 데이터 추가 (Append)

1.1 동작 방식

리스트의 끝에 데이터를 추가하는 작업이다.

평균적으로 O(1)의 시간 복잡도를 가지며, 여유 공간 부족 시 O(n)의 시간이 소요될 수 있다.

  1. 여유 공간 확인:
    • 리스트에 추가할 공간이 있는지 확인한다.
    • 여유 공간이 충분하면 데이터를 바로 추가한다.
  2. 여유 공간 부족 시:
    • 리스트의 크기를 확장한다. (기존 크기의 약 1.125배)
    • 기존 데이터를 새 메모리로 복사하고, 새 데이터를 추가한다.
  3. 참조 관리:
    • 추가된 객체의 참조 카운트를 증가시켜, 메모리 안전성을 확보한다.

1.2 구현 코드: list_append_impl

static PyObject *
list_append_impl(PyListObject *self, PyObject *object)
{
    // 리스트 끝에 데이터를 추가합니다.
    // _PyList_AppendTakeRef는 리스트 크기를 확인하고 메모리를 확장한 뒤 데이터를 추가합니다.
    if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {
        return NULL;  // 추가 실패 시 NULL 반환
    }

    Py_RETURN_NONE;  // 성공적으로 추가되면 None 반환
}

1.3 핵심 함수 설명

  1. Py_NewRef:
    • 추가할 객체의 참조 카운트를 증가시킵니다.
    • 이를 통해 객체가 리스트 내부에서 안전하게 관리되며, 외부에서 삭제되지 않도록 보호됩니다.
  2. _PyList_AppendTakeRef:
    • 리스트 끝에 데이터를 추가하거나, 필요 시 메모리를 확장합니다.
    • 공간이 부족하면 기존 데이터를 새 메모리로 복사한 후 데이터를 추가합니다.

1.3 정리

  • 평균 시간 복잡도: O(1)
  • 최악 시간 복잡도: O(n) (메모리 확장이 필요한 경우)
  • 메모리 확장은 리스트 크기를 약 1.125배로 늘려 성능 저하를 최소화한다.
  • 리스트는 데이터 추가가 빈번한 작업에 적합한 자료구조다.

2. 데이터 삭제 (Pop, Remove)

2.1 동작 방식

특정 인덱스 삭제 (pop)

  1. 리스트 상태 확인:
    • 리스트가 비어 있으면 예외를 발생시킨다.
  2. 인덱스 유효성 검사:
    • 음수 인덱스를 양수로 변환한다.
    • 유효하지 않은 인덱스라면 예외를 발생시킨다.
  3. 데이터 이동:
    • 삭제된 인덱스 이후의 데이터를 모두 앞으로 이동시킨다.
  4. 리스트 크기 조정:
    • 리스트의 크기를 줄인다.
  5. 결과 반환:
    • 삭제된 데이터를 반환한다.

특정 값을 찾아 삭제 (remove)

  1. 값 검색:
    • 리스트를 순회하며 삭제할 값을 찾는다.
    • 값 비교는 리스트의 각 요소와 삭제 대상 값을 비교해 수행된다.
  2. 값 삭제:
    • 발견된 값을 삭제하고, 뒤에 있는 데이터를 앞으로 이동시킨다.
  3. 예외 처리:
    • 값이 리스트에 없으면 예외를 발생시킨다.

2.2 구현 코드: list_pop_impl, list_remove_impl

list_pop_impl

static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
/*[clinic end generated code: output=6bd69dcb3f17eca8 input=c269141068ae4b8f]*/
{
    PyObject *v;  // 삭제된 데이터를 저장할 변수
    int status;   // 삭제 성공 여부를 저장할 변수

    if (Py_SIZE(self) == 0) {  // 리스트가 비어 있는지 확인
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    if (index < 0) {  // 음수 인덱스를 양수로 변환
        index += Py_SIZE(self);
    }
    if (!valid_index(index, Py_SIZE(self))) {  // 유효한 인덱스인지 확인
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }

    PyObject **items = self->ob_item;  // 리스트 데이터 배열
    v = items[index];  // 삭제할 데이터 저장

    const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;

    if (size_after_pop == 0) {  // 삭제 후 리스트가 비어있게 되는 경우
        Py_INCREF(v);  // 삭제된 데이터의 참조 카운트를 증가
        list_clear(self);  // 리스트 메모리 정리
        status = 0;
    } else {  // 삭제 후 데이터를 이동해야 하는 경우
        if ((size_after_pop - index) > 0) {
            memmove(&items[index], &items[index + 1], (size_after_pop - index) * sizeof(PyObject *));
        }
        status = list_resize(self, size_after_pop);  // 리스트 크기를 줄임
    }

    if (status >= 0) {
        return v;  // 삭제된 데이터 반환
    } else {  // 실패 시 원상복구
        memmove(&items[index + 1], &items[index], (size_after_pop - index) * sizeof(PyObject *));
        items[index] = v;
        return NULL;
    }
}

list_remove_impl

static PyObject *
list_remove_impl(PyListObject *self, PyObject *value)
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {  // 리스트 순회
        PyObject *obj = self->ob_item[i];  // 현재 요소
        Py_INCREF(obj);  // 비교를 위해 참조 카운트를 증가
        int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);  // 값 비교
        Py_DECREF(obj);  // 참조 카운트 감소

        if (cmp > 0) {  // 값이 발견되면
            if (list_ass_slice(self, i, i + 1, NULL) == 0) {  // 값을 삭제
                Py_RETURN_NONE;  // 성공 시 None 반환
            }
            return NULL;  // 실패 시 NULL 반환
        }
    }

    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

2.3 핵심 함수 설명

  • PyErr_SetString
    • 예외를 설정하는 함수.
    • 비어 있는 리스트에서 삭제를 시도하거나 값이 존재하지 않을 경우 예외를 발생시킨다.
  • Py_INCREF / Py_DECREF
    • 파이썬 객체의 참조 카운트를 관리한다.
    • Py_INCREF는 참조 카운트를 증가시켜 객체가 삭제되지 않도록 보호한다.
    • Py_DECREF는 참조 카운트를 감소시켜 객체가 더 이상 사용되지 않을 경우 메모리를 해제할 수 있도록 한다.
  • memmove
    • 메모리 블록을 복사하는 저수준 함수이다.
    • 리스트에서 데이터를 삭제한 후, 뒤에 있는 데이터를 앞으로 이동시키는 데 사용된다.
    • 효율적이고 빠른 데이터 이동을 보장한다.
  • list_resize
    • 리스트의 크기를 조정한다.
    • 삭제 작업 후, 리스트 크기를 줄이기 위해 사용된다.
  • PyObject_RichCompareBool
    • 파이썬의 두 객체를 비교한다.
    • 값이 동일한지(==) 확인할 때 사용된다.
    • 리스트의 remove 메서드에서 삭제 대상 값을 찾는 데 활용된다.
  • list_ass_slice
    • 리스트의 특정 구간을 삭제하거나 교체한다.
    • remove 메서드에서 특정 값을 삭제하는 핵심 함수이다.

2.3 정리

  1. pop
    • 특정 인덱스의 데이터를 삭제한다.
    • 삭제된 데이터를 반환하며, 인덱스가 유효하지 않으면 예외를 발생시킨다.
  2. remove
    • 특정 값을 찾아 삭제한다.
    • 값이 없으면 예외를 발생시킨다.

삭제 작업의 성능 분석:

  • pop: 특정 인덱스 데이터 삭제 후, 나머지 데이터를 이동해야 하므로 O(n)의 시간 복잡도를 가진다.
  • remove: 리스트를 순회하며 값을 찾고, 삭제 후 데이터를 이동하므로 O(n)의 시간 복잡도를 가진다.

사용 시 주의사항:

  • 삭제 작업이 빈번히 발생하거나, 중간 삽입/삭제가 많은 경우 collections.deque와 같은 자료구조를 사용하는 것이 더 효율적이다.

3. 데이터 조회 (Indexing)

3.1 동작 방식

리스트는 연속된 메모리 구조를 가지므로, 인덱스를 통한 데이터 접근이 매우 빠르다.

조회 작업은 O(1)의 시간 복잡도를 가진다.

3.2 구현 코드: list_subscript

static PyObject *
list_subscript(PyObject* _self, PyObject* item)
{
    PyListObject* self = (PyListObject*)_self;

    if (_PyIndex_Check(item)) {  // 정수 인덱스인지 확인
        Py_ssize_t index = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (index < 0) index += PyList_GET_SIZE(self);  // 음수 인덱스 처리
        return list_item((PyObject *)self, index);  // 데이터 반환
    }

    PyErr_SetString(PyExc_TypeError, "list indices must be integers or slices");
    return NULL;  // 유효하지 않은 인덱스
}

3.3 핵심 함수 설명

  1. list_item:
    • 지정된 인덱스의 데이터를 반환한다.
  2. PyNumber_AsSsize_t:
    • 인덱스를 정수로 변환하며, 음수 인덱스를 처리한다.

3.3 정리

  • 시간 복잡도: O(1) (정수 인덱스를 통한 조회)
  • 정수 인덱스를 사용한 조회는 매우 효율적이다.
  • 슬라이스를 사용하면 범위 내 데이터를 반환할 수 있다.

최종 정리

  • 추가 작업은 평균적으로 O(1)이며, 메모리 확장을 통해 성능을 최적화한다.
  • 삭제 작업은 데이터 이동으로 인해 O(n)의 시간 복잡도를 가지며, 중간 삭제가 많은 경우 적합하지 않다.
  • 조회 작업은 정수 인덱스를 통해 O(1)의 성능을 보장한다.

실무에서 파이썬 리스트를 고민 없이 사용해왔지만, 이번 계기로 내부 동작을 이해하게 되었다.
이 지식이 리스트 활용에 직접적인 영향을 미칠지는 모르겠지만, 성능 최적화가 필요한 상황에서 더 나은 판단을 내릴 기반이 될 것이다.
특히, 대규모 데이터 처리나 빈번한 삽입/삭제가 필요한 경우 적합한 자료구조를 선택하는 데 도움이 될 것이라 생각한다.
다음엔 딕셔너리 구조에 대해 공부를 해봐야겠다.

Ref.
https://github.com/python/cpython/blob/main/Include/cpython/listobject.h
https://github.com/python/cpython/blob/main/Objects/listobject.c

profile
JUNYOUNG
Onward, Always Upward - 기록은 성장의 증거
다음 포스트

[Python]N+1 문제와 ORM 관계 설정: SQLAlchemy selectinload 사례+subqueryload로 업그레이드

0개의 댓글