[*a]이(가) 초과 할당되는 원인은 무엇입니까?

[*a]이(가) 초과 할당되는 원인은 무엇입니까?

보아하니list(a)오버레이팅은 되지 않습니다.[x for x in a]일부 포인트에서 오버플로케이트하고,[*a]항상 오버플로케이트를 하는 건가요?

다음으로 0 ~ 12의 크기n과 3가지 방식의 바이트 단위 크기를 나타냅니다.

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

Python 3.8을 사용하여 repl.it에서 재현할 수 있습니다.

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소스코드는 어디에 있나요?

(이미지를 생성한 데이터 및 코드와 함께 보관합니다.

더 작은 n으로 확대:

더 큰 n으로 축소:

[*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)똑같아요.

이것은 보통 옳은 일입니다.extend일반적으로 나중에 추가될 것으로 예상되며, 일반화된 포장의 경우 여러 가지가 차례로 추가될 것으로 예상됩니다. [*a]일반적인 경우가 아닙니다.Python은 여러 항목 또는 반복 가능한 항목이 추가되어 있다고 가정합니다.list([*a, b, c, *d]）를 사용하면 일반적인 경우 작업이 절약됩니다.

반면,list(와 함께) 하나의 미리 정해진 반복 가능한 것으로 구성되다list()Python은 사용 중 증가 또는 축소되지 않을 수 있으며, 오버로케이션은 그렇지 않다는 것이 입증될 때까지 시기상조입니다.최근 Python은 이미 알려진 크기의 입력에도 컨스트럭터가 오버로케이션을 발생시키는 버그를 수정했습니다.

에 대해서는list이해력 같은 건 반복하는 거나 마찬가지죠append따라서 요소를 한 번에 추가할 때 일반적인 오버로케이션 증가 패턴의 최종 결과를 볼 수 있습니다.

확실히 말하면, 이것들 중 어느 것도 언어의 보증은 아닙니다.그것은 단지 CPython이 그것을 구현하는 방법이다.Python 언어 사양은 일반적으로 특정 성장 패턴과 무관합니다.list(상각보증에서 제외)O(1) append및pops)를 클릭합니다.코멘트에 기재되어 있듯이, 구체적인 실장은 3.9로 다시 변경되지만, 영향은 없습니다.[*a]그 외의 케이스에 영향을 줄 수 있습니다.이 경우는, 「일시적인 구축」을 실시해 주세요.tuple개개의 아이템과extend와 함께tuple"는 이제 여러 개의 응용 프로그램이 되었습니다.LIST_APPEND이 값은 오버로케이션 발생 시 및 계산에 들어가는 숫자를 변경할 수 있습니다.

다른 답변과 코멘트를 바탕으로 무슨 일이 일어나는지 전체 그림(특히 Shadow Ranger의 답변이 왜 그렇게 되었는지도 설명함)

하면 「」가 됩니다.BUILD_LIST_UNPACK★★★★

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

이는 에서 처리되며, 빈 목록을 작성하고 확장합니다.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_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);

확인해 봅시다.위의 공식으로 예상 스팟 수를 계산하고 8을 곱하여 예상 바이트 크기를 계산합니다(여기서는 64비트 Python을 사용하므로). 그리고 빈 목록의 바이트 크기(예: 목록 개체의 지속적인 오버헤드)를 추가합니다.

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).

언급URL : https://stackoverflow.com/questions/60549865/what-causes-a-to-overallocate