튜플이 Python의 목록보다 빠른 이유는 무엇입니까?

튜플이 Python의 목록보다 빠른 이유는 무엇입니까?

---

방금 "Dive into Python" 에서 "튜플이 목록보다 빠르다 " 라는 글을 읽었습니다 .

튜플은 불변하고 목록은 변경 가능하지만 튜플이 더 빠른 이유를 이해하지 못합니다.

누구든지 이것에 대한 성능 테스트를 했습니까?

---

보고 된 "생성 속도"비율은 상수 튜플 (항목이 리터럴로 표현 된 것) 에만 적용됩니다 . 주의 깊게 관찰하십시오 (그리고 컴퓨터에서 반복하십시오-쉘 / 명령 창에 명령을 입력하기 만하면됩니다!) ... :

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.379 usec per loop
$ python3.1 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.413 usec per loop

$ python3.1 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.174 usec per loop
$ python3.1 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0602 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '[x,y,z]'
1000000 loops, best of 3: 0.352 usec per loop
$ python2.6 -mtimeit '[1,2,3]'
1000000 loops, best of 3: 0.358 usec per loop

$ python2.6 -mtimeit -s'x,y,z=1,2,3' '(x,y,z)'
10000000 loops, best of 3: 0.157 usec per loop
$ python2.6 -mtimeit '(1,2,3)'
10000000 loops, best of 3: 0.0527 usec per loop

나는 3.0에서 측정을하지 않았습니다. 당연히 그것을 가지고 있지 않기 때문입니다. 완전히 쓸모없고 그것을 유지할 이유가 전혀 없습니다. 3.1이 모든면에서 우월하기 때문입니다 (Python 2.7, 만약 당신이 업그레이드 할 수 있습니다. 각 작업에서 2.6보다 거의 20 % 더 빠른 것으로 측정됩니다. 보시다시피 2.6은 3.1보다 빠릅니다. 따라서 성능에 대해 진지하게 생각한다면 Python 2.7이 실제로 필요한 유일한 릴리스입니다. 갈 것입니다!).

어쨌든 여기서 핵심은 각 Python 릴리스에서 상수 리터럴로 목록을 작성하는 것이 변수가 참조하는 값으로 작성하는 것보다 속도가 거의 같거나 약간 느리다는 것입니다. 그러나 튜플은 매우 다르게 동작합니다. 상수 리터럴로 튜플을 만드는 것은 일반적으로 변수가 참조하는 값으로 만드는 것보다 3 배 빠릅니다! 이것이 어떻게 될 수 있는지 궁금 할 것입니다, 그렇죠?-)

답변 : 상수 리터럴로 만들어진 튜플은 파이썬 컴파일러가 불변의 상수 리터럴 자체로 쉽게 식별 할 수 있습니다. 따라서 컴파일러가 소스를 바이트 코드로 변환 할 때 본질적으로 한 번만 빌드되고 "constants 테이블에 숨겨집니다. "관련 기능 또는 모듈. 이러한 바이트 코드가 실행되면 미리 빌드 된 상수 튜플을 복구하기 만하면됩니다-hey presto!-)

이 쉬운 최적화는 목록에 적용 할 수 없습니다. 목록은 변경 가능한 객체이기 때문에 동일한 표현식이 [1, 2, 3]두 번 실행되는 경우 (루프에서- timeit모듈이 사용자를 대신하여 루프를 생성합니다 .-) 새 목록 객체는 매번 새로 생성되며 컴파일러가 컴파일 시간 상수 및 불변 객체로 사소하게 식별 할 수없는 튜플 생성과 같은 구성에는 시간이 조금 걸립니다.

즉, 튜플 생성 (두 구조가 실제로 발생해야 할 때)은 여전히 ​​목록 생성보다 약 두 배 빠릅니다. 이 불일치는 다른 답변에서 반복적으로 언급 한 튜플의 단순한 단순성으로 설명 될 수 있습니다. 그러나 목록과 튜플의 구성과 단순한 상수 리터럴을 항목으로 비교하는 경우에만 관찰 할 수 있듯이 이러한 단순성은 6 배 이상의 속도 향상을 설명하지 않습니다! _)

---

Alex는 훌륭한 대답을했지만 언급 할 가치가 있다고 생각되는 몇 가지 사항을 확장하려고합니다. 모든 성능 차이는 일반적으로 작으며 구현에 따라 다릅니다. 따라서 이러한 차이에 대해 기대하지 마십시오.

CPython에서 튜플은 단일 메모리 블록에 저장되므로 새 튜플을 생성하려면 최악의 경우 메모리 할당을위한 단일 호출이 필요합니다. 목록은 두 개의 블록으로 할당됩니다. 하나는 모든 Python 객체 정보를 포함하는 고정 블록이고 다른 하나는 데이터를위한 가변 크기 블록입니다. 이것이 튜플을 만드는 것이 더 빠른 이유의 일부이지만 따라야 할 포인터가 하나 적기 때문에 인덱싱 속도의 약간의 차이를 설명 할 수도 있습니다.

CPython에는 메모리 할당을 줄이기위한 최적화도 있습니다. 할당 해제 된 목록 개체는 재사용 할 수 있도록 사용 가능한 목록에 저장되지만 비어 있지 않은 목록을 할당하려면 데이터에 대한 메모리 할당이 여전히 필요합니다. 튜플은 크기가 다른 튜플에 대해 20 개의 무료 목록에 저장되므로 작은 튜플을 할당하면 메모리 할당 호출이 전혀 필요하지 않은 경우가 많습니다.

이와 같은 최적화는 실제로 유용하지만 'timeit'의 결과에 너무 많이 의존하는 것을 위험하게 만들 수 있으며 물론 메모리 할당이 매우 다르게 작동하는 IronPython과 같은 것으로 이동하면 완전히 다릅니다.

---

timeit모듈 의 힘으로 성능 관련 질문을 직접 해결할 수 있습니다.

$ python2.6 -mtimeit -s 'a = tuple(range(10000))' 'for i in a: pass'
10000 loops, best of 3: 189 usec per loop
$ python2.6 -mtimeit -s 'a = list(range(10000))' 'for i in a: pass' 
10000 loops, best of 3: 191 usec per loop

이것은 튜플이 반복을위한 목록보다 무시할 정도로 빠르다는 것을 보여줍니다. 인덱싱에 대해 비슷한 결과를 얻었지만 구성을 위해 튜플이 목록을 파괴합니다.

$ python2.6 -mtimeit '(1, 2, 3, 4)'   
10000000 loops, best of 3: 0.0266 usec per loop
$ python2.6 -mtimeit '[1, 2, 3, 4]'
10000000 loops, best of 3: 0.163 usec per loop

따라서 반복 또는 인덱싱 속도가 유일한 요소라면 사실상 차이는 없지만 구성의 경우 튜플이 이깁니다.

---

요약

튜플은 거의 모든 범주의 목록보다 성능이 더 좋습니다 .

1) 튜플은 일정하게 접을 수 있습니다 .

2) 튜플을 복사하는 대신 재사용 할 수 있습니다.

3) 튜플은 작고 과도하게 할당되지 않습니다.

4) 튜플은 요소를 직접 참조합니다.

튜플은 일정하게 접을 수 있습니다.

튜플 상수는 Python의 틈새 최적화 프로그램 또는 AST 최적화 프로그램에 의해 미리 계산 될 수 있습니다. 반면에 목록은 처음부터 작성됩니다.

    >>> from dis import dis

    >>> dis(compile("(10, 'abc')", '', 'eval'))
      1           0 LOAD_CONST               2 ((10, 'abc'))
                  3 RETURN_VALUE   

    >>> dis(compile("[10, 'abc']", '', 'eval'))
      1           0 LOAD_CONST               0 (10)
                  3 LOAD_CONST               1 ('abc')
                  6 BUILD_LIST               2
                  9 RETURN_VALUE 

튜플을 복사 할 필요가 없습니다.

달리기 tuple(some_tuple)는 즉시 자체적으로 반환됩니다. 튜플은 불변이므로 복사 할 필요가 없습니다.

>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True

반대로 list(some_list)모든 데이터를 새 목록에 복사해야합니다.

>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False

튜플이 과도하게 할당되지 않음

튜플의 크기가 고정되어 있기 때문에 append () 작업을 효율적 으로 만들기 위해 과도하게 할당해야하는 목록보다 더 간결하게 저장할 수 있습니다 .

이것은 튜플에 좋은 공간 이점을 제공합니다.

>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200

Here is the comment from Objects/listobject.c that explains what lists are doing:

/* 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, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */

Tuples refer directly to their elements

References to objects are incorporated directly in a tuple object. In contrast, lists have an extra layer of indirection to an external array of pointers.

This gives tuples a small speed advantage for indexed lookups and unpacking:

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop

$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'x, y, z = a'
10000000 loops, best of 3: 0.0249 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'x, y, z = a'
10000000 loops, best of 3: 0.0251 usec per loop

Here is how the tuple (10, 20) is stored:

    typedef struct {
        Py_ssize_t ob_refcnt;
        struct _typeobject *ob_type;
        Py_ssize_t ob_size;
        PyObject *ob_item[2];     /* store a pointer to 10 and a pointer to 20 */
    } PyTupleObject;

Here is how the list [10, 20] is stored:

    PyObject arr[2];              /* store a pointer to 10 and a pointer to 20 */

    typedef struct {
        Py_ssize_t ob_refcnt;
        struct _typeobject *ob_type;
        Py_ssize_t ob_size;
        PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
        Py_ssize_t allocated;
    } PyListObject;

Note that the tuple object incorporates the two data pointers directly while the list object has an additional layer of indirection to an external array holding the two data pointers.

---

Essentially because tuple's immutability means that the interpreter can use a leaner, faster data structure for it, compared to list.

---

One area where a list is notably faster is construction from a generator, and in particular, list comprehensions are much faster than the closest tuple equivalent, tuple() with a generator argument:

$ python --version
Python 3.6.0rc2
$ python -m timeit 'tuple(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.34 usec per loop
$ python -m timeit 'list(x * 2 for x in range(10))'
1000000 loops, best of 3: 1.41 usec per loop
$ python -m timeit '[x * 2 for x in range(10)]'
1000000 loops, best of 3: 0.864 usec per loop

Note in particular that tuple(generator) seems to be a tiny bit faster than list(generator), but [elem for elem in generator] is much faster than both of them.

---

Tuples are identified by python compiler as one immutable constant so compiler created only one entry in hash table and never changed

Lists are mutable objects.So compiler update the entry when we update the list so it is little bit slower compare to tuple

참고URL : https://stackoverflow.com/questions/3340539/why-is-tuple-faster-than-list-in-python