[python] [* a]의 전반적인 원인은 무엇입니까?

Program / 글쓴이

분명히 전체적으로 분류list(a) 하지 않고 [x for x in a]어떤 시점에서 전체적으로[*a] 할당하고 항상 전체적으로 할당 합니까?

최대 n = 100 크기

다음은 크기가 n에서 0부터 12까지이며 세 가지 방법에 대한 결과 크기는 바이트입니다.

0 56 56 56
1 64 88 88
2 72 88 96
3 80 88 104
4 88 88 112
5 96 120 120
6 104 120 128
7 112 120 136
8 120 120 152
9 128 184 184
10 136 184 192
11 144 184 200
12 152 184 208

다음과 같이 계산 된, repl.it에서 재현 할 파이썬 3. 사용, 8 :

from sys import getsizeof

for n in range(13):
    a = [None] * n
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]))

그래서 : 이것은 어떻게 작동합니까? [*a]전체적으로 어떻게 구성 합니까? 실제로, 주어진 입력에서 결과 목록을 작성하기 위해 어떤 메커니즘을 사용합니까? 반복자를 a사용하고 다음과 같은 것을 사용 list.append합니까? 소스 코드는 어디에 있습니까?

( 이미지를 생성 한 데이터 및 코드와 Colab )

더 작은 n으로 확대 :

최대 n = 40 크기

더 큰 n으로 축소 :

최대 n = 1000 크기

답변

[*a] 내부적으로 다음 과 같은 C를 수행하고 있습니다 .

  1. 새로운 빈 만들기 list
  2. 요구 newlist.extend(a)
  3. 를 반환 list합니다.

따라서 테스트를 확장하면 :

from sys import getsizeof

for n in range(13):
    a = [None] * n
    l = []
    l.extend(a)
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]),
             getsizeof(l))

온라인으로 사용해보십시오!

당신에 대한 결과를 볼 수 getsizeof([*a])와 l = []; l.extend(a); getsizeof(l)동일합니다.

이것은 일반적으로 올바른 일입니다. extending을 할 때 일반적으로 나중에 더 많이 추가 할 것으로 예상하고 일반 포장 풀기의 경우와 마찬가지로 여러 항목이 차례로 추가 될 것으로 가정합니다. [*a]정상적인 경우가 아닙니다. 파이썬은 여러 항목이나 반복 가능 객체받는 추가되고있다 가정 list( [*a, b, c, *d]초과 할당은 일반적인 경우에 작업을 저장), 그래서는.

대조적으로, list단일 크기의 iterable iterable (로 포함 된 list())은 사용 중에 커지거나 줄어들지 않을 수 있으며, 그렇지 않으면 입증 될 때까지 전체 할당이 너무 빠릅니다. 파이썬은 최근에 알려진 크기의 입력에 대해서도 생성자를 전체적으로 만드는 버그를 수정했습니다 .

list이해력에 관해서는 그것들은 효과적으로 반복되는 것과 동일 append하므로 한 번에 요소를 추가 할 때 정상적인 초과 할당 증가 패턴의 최종 결과를 볼 수 있습니다.

분명히, 이것은 언어 보증이 아닙니다. CPython이 구현하는 방식입니다. 파이썬 언어 사양은 일반적으로 list(상각 된 것을 보장하는 것 외에도) 특정 성장 패턴으로 인식되지 않습니다.O(1) appendpop 끝에서 및 ). 의견에서 언급했듯이, 특정 구현은 3.9에서 다시 변경된다. 영향을 미치지 않지만 이전에 [*a]” tuple개별 항목을 임시 로 구축 한 다음 ” 을 extend사용하여 tuple여러 애플리케이션이 되는 다른 경우에 영향을 줄 LIST_APPEND수 있습니다.이 경우 초과 할당이 발생하는 시점과 계산에 포함되는 숫자가 변경 될 수 있습니다.

답변

다른 답변과 의견 (특히 ShadowRanger의 답변 , 왜 그렇게했는지 설명)을 기반으로 발생 하는 상황에 대한 전체 그림 .

BUILD_LIST_UNPACK사용되는 분해 쇼 :

>>> import dis
>>> dis.dis('[*a]')
  1           0 LOAD_NAME                0 (a)
              2 BUILD_LIST_UNPACK        1
              4 RETURN_VALUE

에서 처리 되어ceval.c 빈 목록을 작성하고 확장합니다 ( a).

        case TARGET(BUILD_LIST_UNPACK): {
            ...
            PyObject *sum = PyList_New(0);
              ...
                none_val = _PyList_Extend((PyListObject *)sum, PEEK(i));

_PyList_Extend 사용합니다 list_extend :

_PyList_Extend(PyListObject *self, PyObject *iterable)
{
    return list_extend(self, iterable);
}

크기의 합으로 어떤 호출list_resize :

list_extend(PyListObject *self, PyObject *iterable)
    ...
        n = PySequence_Fast_GET_SIZE(iterable);
        ...
        m = Py_SIZE(self);
        ...
        if (list_resize(self, m + n) < 0) {

그리고 전체적으로 다음과 같이 할당 됩니다.

list_resize(PyListObject *self, Py_ssize_t newsize)
{
  ...
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

확인해 봅시다. 위의 공식으로 예상 스팟 수를 계산하고 여기에 64 비트 파이썬을 사용하는 것처럼 8을 곱하고 빈 목록의 바이트 크기 (예 : 목록 객체의 상수 오버 헤드)를 추가하여 예상 바이트 크기를 계산하십시오 :

from sys import getsizeof
for n in range(13):
    a = [None] * n
    expected_spots = n + (n >> 3) + (3 if n < 9 else 6)
    expected_bytesize = getsizeof([]) + expected_spots * 8
    real_bytesize = getsizeof([*a])
    print(n,
          expected_bytesize,
          real_bytesize,
          real_bytesize == expected_bytesize)

산출:

0 80 56 False
1 88 88 True
2 96 96 True
3 104 104 True
4 112 112 True
5 120 120 True
6 128 128 True
7 136 136 True
8 152 152 True
9 184 184 True
10 192 192 True
11 200 200 True
12 208 208 True

을 제외하고 일치 n = 0하는 list_extend사실은 바로 그 경기가 너무, 그래서 사실 :

        if (n == 0) {
            ...
            Py_RETURN_NONE;
        }
        ...
        if (list_resize(self, m + n) < 0) {

답변

이것들은 CPython 인터프리터의 구현 세부 사항이 될 것이므로 다른 인터프리터간에 일관성이 없을 수 있습니다.

즉, 당신은 이해력과 list(a) 행동이 있습니다.

https://github.com/python/cpython/blob/master/Objects/listobject.c#L36

이해력을 위해 특별히 : 

 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
...

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

해당 줄 바로 아래에를 list_preallocate_exact호출 할 때 사용됩니다 list(a).

답변