Apa yang menyebabkan [* a] secara keseluruhan?

136

Tampaknya list(a)tidak secara keseluruhan, [x for x in a]keseluruhan di beberapa titik, dan [*a]keseluruhan sepanjang waktu ?

Ukuran hingga n = 100

Berikut adalah ukuran n dari 0 hingga 12 dan ukuran yang dihasilkan dalam byte untuk tiga metode:

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

Dihitung seperti ini, dapat direproduksi di repl.it , menggunakan Python 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]))

Jadi: Bagaimana cara kerjanya? Bagaimana secara [*a]keseluruhan? Sebenarnya, mekanisme apa yang digunakannya untuk membuat daftar hasil dari input yang diberikan? Apakah itu menggunakan iterator adan menggunakan sesuatu seperti list.append? Di mana kode sumbernya?

( Colab dengan data dan kode yang menghasilkan gambar.)

Memperbesar menjadi lebih kecil n:

Ukuran hingga n = 40

Perkecil hingga lebih besar n:

Ukuran hingga n = 1000

Stefan Pochmann
sumber
1
Pertama, memperpanjang kasus pengujian Anda akan tampak bahwa pemahaman daftar berperilaku seperti menulis lingkaran dan menambahkan setiap item ke daftar, sementara [*a]tampaknya berperilaku seperti menggunakan extenddaftar kosong.
jdehesa
4
Mungkin membantu untuk melihat kode byte yang dihasilkan untuk masing-masing kode. list(a)beroperasi sepenuhnya dalam C; itu dapat mengalokasikan node buffer internal demi node saat iterates over a. [x for x in a]hanya menggunakan LIST_APPENDbanyak, jadi ini mengikuti pola "secara keseluruhan sedikit, alokasikan kembali jika perlu" dari daftar normal. [*a]menggunakan BUILD_LIST_UNPACK, yang ... Saya tidak tahu apa yang dilakukannya, selain ternyata terlalu banyak mengalokasikan sepanjang waktu :)
chepner
2
Juga, dalam Python 3.7, tampaknya itu list(a)dan [*a]identik, dan keduanya secara keseluruhan dibandingkan dengan [x for x in a], jadi ... sys.getsizeofmungkin bukan alat yang tepat untuk digunakan di sini.
chepner
7
@ chepner saya pikir sys.getsizeofadalah alat yang tepat, itu hanya menunjukkan bahwa list(a)digunakan untuk mengatur keseluruhan. Sebenarnya Apa Yang Baru Di Python 3.8 menyebutkannya: "Daftar konstruktor tidak secara keseluruhan menempatkan [...]" .
Stefan Pochmann
5
@ chepner: Itu adalah bug yang diperbaiki di 3.8 ; Konstruktor tidak seharusnya secara keseluruhan.
ShadowRanger

Jawaban:

81

[*a] secara internal melakukan C yang setara dengan :

  1. Buat yang baru, kosongkan list
  2. Panggilan newlist.extend(a)
  3. Pengembalian list.

Jadi, jika Anda memperluas tes Anda ke:

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

Cobalah online!

Anda akan melihat hasilnya getsizeof([*a])dan l = []; l.extend(a); getsizeof(l)sama.

Ini biasanya hal yang benar untuk dilakukan; Ketika extendAnda biasanya berharap untuk menambahkan lebih banyak nanti, dan juga untuk pembongkaran umum, diasumsikan bahwa banyak hal akan ditambahkan satu demi satu. [*a]bukan kasus normal; Python mengasumsikan ada beberapa item atau iterables yang ditambahkan ke list( [*a, b, c, *d]), jadi keseluruhan lokasi menyimpan pekerjaan dalam kasus umum.

Sebaliknya, yang listdikonstruksi dari satu, yang dapat diubah (dengan list()) tidak boleh tumbuh atau menyusut selama penggunaan, dan keseluruhan penempatan prematur sampai terbukti sebaliknya; Python baru-baru ini memperbaiki bug yang membuat konstruktor secara keseluruhan bahkan untuk input dengan ukuran yang diketahui .

Adapun listpemahaman, mereka secara efektif setara dengan appends berulang , sehingga Anda melihat hasil akhir dari pola pertumbuhan keseluruhan penempatan normal saat menambahkan elemen pada suatu waktu.

Agar jelas, semua ini bukan jaminan bahasa. Hanya bagaimana CPython mengimplementasikannya. Spesifikasi bahasa Python pada umumnya tidak peduli dengan pola pertumbuhan spesifik list(selain menjamin amortisasi O(1) appenddan pops dari akhir). Seperti disebutkan dalam komentar, implementasi spesifik berubah lagi di 3,9; sementara itu tidak akan mempengaruhi [*a], itu bisa mempengaruhi kasus-kasus lain di mana apa yang dulunya "membangun sementara tupleitem individual dan kemudian extenddengan tuple" sekarang menjadi beberapa aplikasi LIST_APPEND, yang dapat berubah ketika keseluruhan lokasi terjadi dan angka apa yang masuk ke dalam perhitungan.

ShadowRanger
sumber
4
@StefanPochmann: Saya sudah membaca kode sebelumnya (itulah sebabnya saya sudah tahu ini). Ini adalah penangan kode byteBUILD_LIST_UNPACK , yang digunakan _PyList_Extendsebagai C yang setara dengan pemanggilan extend(hanya secara langsung, bukan dengan metode pencarian). Mereka menggabungkannya dengan jalan untuk membangun tupledengan membongkar; tupleTidak secara keseluruhan menempatkan dengan baik untuk pembuatan sedikit demi sedikit, sehingga mereka selalu membongkar list(untuk mendapatkan manfaat dari keseluruhan lokasi), dan beralih ke tuplepada akhirnya ketika itulah yang diminta.
ShadowRanger
4
Perhatikan bahwa ini tampaknya berubah pada 3,9 , di mana konstruksi dilakukan dengan bytecodes yang terpisah ( BUILD_LIST, LIST_EXTENDuntuk setiap hal untuk dibongkar, LIST_APPENDuntuk item tunggal), alih-alih memuat segala sesuatu di stack sebelum membangun keseluruhan listdengan instruksi kode byte tunggal (memungkinkan compiler untuk melakukan optimasi bahwa semua-dalam-satu instruksi tidak memungkinkan, seperti menerapkan [*a, b, *c]sebagai LIST_EXTEND, LIST_APPEND, LIST_EXTENDw / o perlu untuk membungkus bdalam satu- tupleuntuk memenuhi persyaratan BUILD_LIST_UNPACK).
ShadowRanger
18

Gambaran lengkap tentang apa yang terjadi, membangun jawaban dan komentar lain (terutama jawaban ShadowRanger , yang juga menjelaskan mengapa itu dilakukan seperti itu).

Membongkar acara yang BUILD_LIST_UNPACKdigunakan:

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

Itu ditangani diceval.c , yang membangun daftar kosong dan meluas (dengan a):

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

_PyList_Extend menggunakan list_extend :

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

Yang memanggil list_resizedengan jumlah ukuran :

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

Dan itu secara keseluruhan menempatkan sebagai berikut:

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

Mari kita periksa. Hitung jumlah tempat yang diharapkan dengan rumus di atas, dan hitung ukuran byte yang diharapkan dengan mengalikannya dengan 8 (karena saya menggunakan Python 64-bit di sini) dan menambahkan ukuran byte daftar kosong (yaitu, overhead konstan objek daftar) :

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)

Keluaran:

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

Cocok kecuali untuk n = 0, yang list_extendsebenarnya pintasan , jadi benar-benar cocok juga:

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

Ini akan menjadi detail implementasi dari juru bahasa CPython, dan karenanya mungkin tidak konsisten antar penerjemah lain.

Yang mengatakan, Anda bisa melihat di mana pemahaman dan list(a)perilaku muncul di sini:

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

Khusus untuk pemahaman:

 * 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);

Tepat di bawah garis itu, ada list_preallocate_exactyang digunakan saat menelepon list(a).

Randy
sumber
1
[*a]tidak menambahkan elemen individual satu per satu. Itu punya bytecode khusus sendiri, yang melakukan penyisipan massal extend.
ShadowRanger
Gotcha - Saya kira saya tidak menggali cukup jauh tentang itu. Menghapus bagian pada[*a]
Randy