소스코드 레벨에서 비교하는 Python List와 Set의 차이

Python에서 Set과 List

 

List는 순서가 있고 mutable한 객체 집합이며, Set은 순서가 없고 mutable한 고유한 객체 집합이다.
두 자료구조 사이의 가장 큰 차이는 1) 객체의 중복 허용 여부와 2) 순서를 가지고 있는가 이다.

순서가 중요할 때에는 List를 사용하며, 객체의 중복을 배제하고 싶을 때에는 Set을 사용하는 것이 좋다.
그런데, 만약 중복이 없는 배열이 필요한 상황에서는 list와 set 중 어느 것을 사용하는 것이 좋을까? 둘 중 하나를 고르는 것이 실질적으로 어플리케이션의 성능에 큰 차이를 가져올 수 있을까?

 

CPython 소스코드 레벨로 이해하는 List

CPython 소스코드를 보게되면 List는 PyObject의 array의 포인터를 가지는 형태의 구조체로 구현되어있다.

typedef struct {
    PyObject_VAR_HEAD
    /* 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
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

구조체 내에 allocated라는 값을 통해 전체 reference의 수를 counting하는 방식으로 배열의 크기를 관리하기 때문에 list.length 연산을 사용할때 매번 list의 크기를 계산할 필요 없이 간단하게 배열의 크기를 반환할 수 있게 되는 것이다.

단순히 list 객체를 만드는 경우에는 다음과 같이 length가 0인 상태로 초기화가 이루어지게 된다.

static PyObject *
list_repr(PyListObject *v)
{
    Py_ssize_t i;
    PyObject *s, *temp;
    PyObject *pieces = NULL, *result = NULL;

    i = Py_ReprEnter((PyObject*)v);
    if (i != 0) {
        return i > 0 ? PyString_FromString("[...]") : NULL;
    }

    if (Py_SIZE(v) == 0) {
        result = PyString_FromString("[]");
        goto Done;
    }

    pieces = PyList_New(0);
    if (pieces == NULL)
        goto Done;

...
}

또한, slice를 만들 때에는 인덱스 값들로 부터 길이를 계산해서 동적으로 새로 PyListObject 구조체를 만든 뒤, for loop를 통해 값을 일일히 복제하는 방식으로 작업이 이루어지게 된다.

static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    len = ihigh - ilow;
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;

    src = a->ob_item + ilow;
    dest = np->ob_item;
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
}

이쯤에서 한가지 의문이 들 수 있을 것이다. 파이썬의 List가 C의 Array를 활용해서 구현되었다고 했는데, C의 Array는 "정해진 크기만큼만" 할당이 가능하다. 파이썬에서는 동적으로 크기가 증가하는 List의 구현을 위해서 매번 insertion이 일어날 때마다 남은 배열의 크기를 확인하고, 남은 empty space가 더 없다면 더 큰 배열을 재할당하고, 기존 값들을 이전 배열에서 새로운 배열로 복사하는 방법으로 문제를 해결하였다.

/* Ensure ob_item has room for at least newsize elements, and set
 * ob_size to newsize.  If newsize > ob_size on entry, the content
 * of the new slots at exit is undefined heap trash; it's the caller's
 * responsiblity to overwrite them with sane values.
 * The number of allocated elements may grow, shrink, or stay the same.
 * Failure is impossible if newsize <= self.allocated on entry, although
 * that partly relies on an assumption that the system realloc() never
 * fails when passed a number of bytes <= the number of bytes last
 * allocated (the C standard doesn't guarantee this, but it's hard to
 * imagine a realloc implementation where it wouldn't be true).
 * Note that self->ob_item may change, and even if newsize is less
 * than ob_size on entry.
 */
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;
    items = self->ob_item;
    if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

...

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) == -1)
        return -1;

    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

위의 `ins1` 함수는 리스트에 새로운 값이 추가될 때마다 호출이 되는데, 해당 함수 내부에서 남은 공간이 없는지 여부를 확인 후 더 큰 Array를 재할당하는 방식으로 작동하게 된다. 또한, Array 재할당이 너무 자주 발생하게 되면 성능 저하 포인트가 될 수 있기 때문에, 파이썬에서는 매번 새로 Array를 생성할 때마다 필요한 양보다 더 메모리를 할당함으로써 list resizing이 너무 자주 일어나지 않도록 한다.

 

CPython 소스코드 레벨로 이해하는 Set

 

Set은 List와는 다르게 "HashTable"을 활용해서 구현되게 된다.

#define PySet_MINSIZE 8

typedef struct {
    long hash;      /* cached hash code for the entry key */
    PyObject *key;
} setentry;


/*
This data structure is shared by set and frozenset objects.
*/

typedef struct _setobject PySetObject;
struct _setobject {
    PyObject_HEAD

    Py_ssize_t fill;  /* # Active + # Dummy */
    Py_ssize_t used;  /* # Active */

    /* The table contains mask + 1 slots, and that's a power of 2.
     * We store the mask instead of the size because the mask is more
     * frequently needed.
     */
    Py_ssize_t mask;

    /* table points to smalltable for small tables, else to
     * additional malloc'ed memory.  table is never NULL!  This rule
     * saves repeated runtime null-tests.
     */
    setentry *table;
    setentry *(*lookup)(PySetObject *so, PyObject *key, long hash);
    setentry smalltable[PySet_MINSIZE];

    long hash;                  /* only used by frozenset objects */
    PyObject *weakreflist;      /* List of weak references */
};

Set은 Dict와 마찬가지로 Open Addressing 기반의 해시 테이블로 구현되도록 구현되었으며, 처음 객체가 생성될 때에는 8개의 객체를 저장할 수 있을만큼의 공간이 할당되게 된다. 그리고, 객체가 추가되는 등의 과정에서 더 많은 메모리 공간이 필요할 때마다 더 큰 테이블을 만들게 된다.

static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
    register PySetObject *so = NULL;

    if (dummy == NULL) { /* Auto-initialize dummy */
        dummy = PyString_FromString("<dummy key>");
        if (dummy == NULL)
            return NULL;
    }

    /* create PySetObject structure */
    if (numfree &&
        (type == &PySet_Type  ||  type == &PyFrozenSet_Type)) {
        so = free_list[--numfree];
        assert (so != NULL && PyAnySet_CheckExact(so));
        Py_TYPE(so) = type;
        _Py_NewReference((PyObject *)so);
        EMPTY_TO_MINSIZE(so);
        PyObject_GC_Track(so);
    } else {
        so = (PySetObject *)type->tp_alloc(type, 0);
        if (so == NULL)
            return NULL;
        /* tp_alloc has already zeroed the structure */
        assert(so->table == NULL && so->fill == 0 && so->used == 0);
        INIT_NONZERO_SET_SLOTS(so);
    }

    so->lookup = set_lookkey_string;
    so->weakreflist = NULL;

    if (iterable != NULL) {
        if (set_update_internal(so, iterable) == -1) {
            Py_DECREF(so);
            return NULL;
        }
    }

    return (PyObject *)so;
}

해시 테이블에서의 해시 충돌을 피하기 위해서 Dict와 마찬가지로 `Perturbation Shift Probing` 기반의 Open Addressing 알고리즘을 사용하게 된다.

 

알다시피, 해시테이블은 key-value 기반의 자료구조이기 때문에, Set을 해시테이블을 사용해서 구현하기 위해서는 적절한 "key"를 갖도록 만들어야 한다. 이를 위해 Open Addressing 알고리즘을 사용해서 만든 hash 값을 string으로 변환 시킨 값을 key로 사용하도록 한다.

굳이 key를 string으로 만든 이유는 아래 코드의 주석에서 볼 수 있듯이, `_PyString_Eq` 함수를 재사용함으로써 코드를 효율적으로 관리하도록 하면서, key의 타입을 일관성 있게 관리하고 key의 비교를 간단하게 수행할 수 있도록 만든 것이다.

/*
 * Hacked up version of set_lookkey which can assume keys are always strings;
 * This means we can always use _PyString_Eq directly and not have to check to
 * see if the comparison altered the table.
 */
static setentry *
set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
{
    register Py_ssize_t i;
    register size_t perturb;
    register setentry *freeslot;
    register size_t mask = so->mask;
    setentry *table = so->table;
    register setentry *entry;

    /* Make sure this function doesn't have to handle non-string keys,
       including subclasses of str; e.g., one reason to subclass
       strings is to override __eq__, and for speed we don't cater to
       that here. */
    if (!PyString_CheckExact(key)) {
        so->lookup = set_lookkey;
        return set_lookkey(so, key, hash);
    }
    i = hash & mask;
    entry = &table[i];
    if (entry->key == NULL || entry->key == key)
        return entry;
    if (entry->key == dummy)
        freeslot = entry;
    else {
        if (entry->hash == hash && _PyString_Eq(entry->key, key))
            return entry;
        freeslot = NULL;
    }

    /* In the loop, key == dummy is by far (factor of 100s) the
       least likely outcome, so test for that last. */
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = (i << 2) + i + perturb + 1;
        entry = &table[i & mask];
        if (entry->key == NULL)
            return freeslot == NULL ? entry : freeslot;
        if (entry->key == key
            || (entry->hash == hash
            && entry->key != dummy
            && _PyString_Eq(entry->key, key)))
            return entry;
        if (entry->key == dummy && freeslot == NULL)
            freeslot = entry;
    }
    assert(0);          /* NOT REACHED */
    return 0;
}

 

List 대신 Set을 사용해서 성능을 대폭 개선하기

앞서 보았듯이, List는 Array이고 Set은 HashTable이다. 단순히 전체 값을 iterrate해야 하는 등의 경우에는 둘 사이의 성능에 그리 큰 차이가 없을 것이나, 집합 내에 있는 특정 값을 찾아야 하는 경우에는 List보다 Set이 압도적으로 더 빠르게 작업을 수행할 수 있다. 집합의 크기가 커질 수록 더욱 확실하게 성능 차이가 나게 된다.

Array 내에서 특정 값을 찾는 작업의 시간 복잡도는 `O(n)`인데 반해, HashTable 내에서 특정 값을 찾는 작업의 시간 복잡도는 `O(1)`에 근접하게 된다. 즉, 전체 집합의 크기가 커지면 커질 수록 n의 크기가 커지게 되기 때문에 두 접근법 사이의 성능 차이는 더욱 커지게 될 것이다.

물론, Set은 중복이 허용 안 되고 순서가 없기 때문에 언제나 사용할 수 있지는 않겠지만, 중복이 없는 객체 집합 내에서 특정 값을 찾는 작업이 자주 일어나는 경우에는 List 대신 Set을 통해 확실하게 성능을 개선시킬 수 있을 것이다.

 

아래는 이와 관련된 예제 코드이다.

from timeit import timeit


my_list = list(range(1_000_000))
my_set = set(range(1_000_000))

list_time = timeit('999_999 in my_list', number=1000, globals=globals())
print(f'List: {list_time:.6f} seconds')

set_time = timeit('999_999 in my_set', number=1000, globals=globals())
print(f'Set: {set_time:.6f} seconds')

위의 코드를 실행시켜보게 되면 list의 경우 약 9.1초가 소요되는데 반해 set은 약 0.00003초 정도가 소요되게 된다.

그렇다고 Set이 List보다 늘 좋다는 것은 아니겠지만, 위와 같이 중복이 없는 집합 내에서 특정 값을 찾는 경우에서는 Set을 선택하는 것이 전체 시스템의 성능을 크게 향상 시켜줄 수 있다는 것을 알아두는 것이 좋을 것이다.

 

참고자료

https://svn.python.org/projects/python/trunk/Objects/setobject.c

https://svn.python.org/projects/python/trunk/Include/setobject.h

https://svn.python.org/projects/python/trunk/Objects/listobject.c

https://svn.python.org/projects/python/trunk/Include/listobject.h