파이썬에는 리스트의 첫번째 요소를 추가하는 방법들이 되게 많다(😢), 흔히 사용되는 list.insert도 방법 중에 하나이지만 리스트의 시작과 끝에 요소를 추가하는 경우에는 많은 비용이 발생하여 권장되는 방법은 아니다.

list.insert(0, v)는 왜 권장되지 않는가(매우 느리다.)

• https://wiki.python.org/moin/TimeComplexity

  …inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.

because everything after that must move 충격과 공포의 한 문장..그렇다 파이썬은 list.insert를 이용하여 리스트의 시작에 새로운 요소를 넣을 경우 모든 요소를 이동시켜야 하기 때문이다. CPython 코드를 확인해보니(list_insert_impl > ins1) ins1 함수에 이렇게 뒤에서부터 순회하여 새로운 값을 집어넣게 되어있는데, 이게 0이면?!?! 모든 요소를 움직이게 되는 것이다..🙄

/* https://github.com/python/cpython/Objects/listobject.c#L286-L287 */
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
    ...
    /* n = 리스트 길이, where = 추가하려는 위치 */
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    ...

거기에 만약 새로운 요소로 인해서 list의 전체 크기를 넘기게 되면 realloc 함수에 의해서 리스트의 크기를 늘리는 작업이 추가로 발생하기 때문에 더 느려지게 되는 것이다.(이건 list.append도 똑같다.) 그러면 안 그래도 느린 파이썬의 리스트에 첫번째 요소를 넣기위해서 어떤 방법들로 속도를 최적화 할 수 있을까!

첫번째! collections.deque

쓸 수만 있다면 collections.deque를 사용하는 것이 가장 좋다. deque는 list처럼 새로운 요소를 추가하기 위해 모든 요소를 순회하지 않는다. 왜냐하면 요 녀석은 사실 dobule linked list이기 때문에 앞뒤에 요소를 추가하는 일에 대해서는 O(1)의 성능을 자랑한다.(대신 메모리를 더 먹겠죠?ㅎ)

from collections import deque


d = deque([1, 2, 3, 4, 5])
d.appendleft(0)  # list.insert(0, v), [0, 1, 2, 3, 4, 5]

그리고 deque는 list와 비슷한 연산들을 지원하기 때문에 사용하기에도 어렵지 않다.

두번째! slice assignment

slice assignment를 이용한 방법이다. 파이썬의 slice assignment 구현은 glibc의 memmove를 이용하여 구현되어 있는데, 추가하려는 리스트의 크기만큼 새로운 메모리를 할당하고 뒤의 리스트의 메모리 주소만 이동하는 방식인 것 같다.(글 작성하면서 찾아본 코드만 봤을 때는 이런 느낌인데, 나중에 더 자세히 봐야겠다.)

a = [1, 2, 3, 4, 5]
a[:0] = [0]  # a.insert(0, 0), [0, 1, 2, 3, 4, 5]

세번째! list concat

간단하게 list + list이다. 요 방식은 위의 두 방식과 다르게 두개의 배열을 concat하여 새로운 배열을 만들기 때문에 약간의 overload가 있다.

a = [1, 2, 3, 4, 5]
a = [0] + a   # a.insert(0, 0), [0, 1, 2, 3, 4, 5]

정리

이렇게 파이썬 리스트에 첫 번째 요소를 추가하는 방법들을 알아보았다. CPython의 구현들도 세부적으로 알게 되어 재밌는 시간이었고, 절대 대용량 list에서 insert를 이용하여 리스트의 시작 부분에 데이터를 넣으면 안 된다는 것을 다시 한번 마음에 되새겼다.

P.S. deque는 다른 데이터 타입이니 그렇다치지만 왜 list.insert는 내부적으로 slice assignment를 사용하지 않는 지는 잘모르겠다. 뭐 나보다 똑똑한 사람들이 만들었으니 다 이유가 있겠지 ㅎㅅㅎ..