Pertanyaan daftar () menggunakan lebih banyak memori daripada pemahaman daftar


Jadi saya bermain dengan list benda-benda dan menemukan sedikit hal aneh itu jika list dibuat dengan list() menggunakan lebih banyak memori, daripada pemahaman daftar? Saya menggunakan Python 3.5.2

In [1]: import sys
In [2]: a = list(range(100))
In [3]: sys.getsizeof(a)
Out[3]: 1008
In [4]: b = [i for i in range(100)]
In [5]: sys.getsizeof(b)
Out[5]: 912
In [6]: type(a) == type(b)
Out[6]: True
In [7]: a == b
Out[7]: True
In [8]: sys.getsizeof(list(b))
Out[8]: 1008

Dari dokumen:

Daftar dapat dibangun dengan beberapa cara:

  • Menggunakan sepasang tanda kurung siku untuk menunjukkan daftar kosong: []
  • Menggunakan tanda kurung siku, memisahkan item dengan koma: [a], [a, b, c]
  • Menggunakan pemahaman daftar: [x for x in iterable]
  • Menggunakan konstruktor tipe: list() atau list(iterable)

Tetapi tampaknya menggunakan list() ini menggunakan lebih banyak memori.

Dan sebanyak itu list lebih besar, kesenjangan meningkat.

Difference in memory

Mengapa ini terjadi?

UPDATE # 1

Uji dengan Python 3.6.0b2:

Python 3.6.0b2 (default, Oct 11 2016, 11:52:53) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(range(100)))
1008
>>> sys.getsizeof([i for i in range(100)])
912

UPDATE # 2

Uji dengan Python 2.7.12:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(xrange(100)))
1016
>>> sys.getsizeof([i for i in xrange(100)])
920

75
2017-10-13 10:25


asal


Jawaban:


Saya pikir Anda melihat pola alokasi berlebihan ini adalah sampel dari sumbernya:

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

Mencetak ukuran daftar pemahaman panjang 0-88 Anda dapat melihat pola yang cocok:

# create comprehensions for sizes 0-88
comprehensions = [sys.getsizeof([1 for _ in range(l)]) for l in range(90)]

# only take those that resulted in growth compared to previous length
steps = zip(comprehensions, comprehensions[1:])
growths = [x for x in list(enumerate(steps)) if x[1][0] != x[1][1]]

# print the results:
for growth in growths:
    print(growth)

Hasil (formatnya adalah (list length, (old total size, new total size))):

(0, (64, 96)) 
(4, (96, 128))
(8, (128, 192))
(16, (192, 264))
(25, (264, 344))
(35, (344, 432))
(46, (432, 528))
(58, (528, 640))
(72, (640, 768))
(88, (768, 912))

Over-alokasi dilakukan untuk alasan kinerja yang memungkinkan daftar tumbuh tanpa mengalokasikan lebih banyak memori dengan setiap pertumbuhan (lebih baik diamortisasi kinerja).

Alasan yang mungkin untuk perbedaan dengan menggunakan pemahaman daftar, adalah bahwa pemahaman daftar tidak dapat secara deterministik menghitung ukuran daftar yang dibuat, tetapi list() bisa. Ini berarti pemahaman akan terus menumbuhkan daftar karena mengisi dengan menggunakan alokasi berlebihan sampai akhirnya mengisinya.

Ada kemungkinan bahwa tidak akan menumbuhkan buffer over-alokasi dengan node dialokasikan yang tidak digunakan setelah dilakukan (pada kenyataannya, dalam banyak kasus tidak akan, yang akan mengalahkan tujuan over-alokasi).

list()Namun, dapat menambahkan beberapa buffer tidak peduli ukuran daftar karena tahu ukuran daftar terakhir di muka.


Bukti pendukung lainnya, juga dari sumbernya, adalah yang kita lihat daftar pemahaman yang memohon LIST_APPEND, yang menunjukkan penggunaan list.resize, yang pada gilirannya menunjukkan mengonsumsi buffer pra-alokasi tanpa mengetahui berapa banyak yang akan diisi. Ini konsisten dengan perilaku yang Anda lihat.


Untuk menyimpulkan, list() akan mengalokasikan lebih banyak node sebagai fungsi dari ukuran daftar

>>> sys.getsizeof(list([1,2,3]))
60
>>> sys.getsizeof(list([1,2,3,4]))
64

List comprehension tidak mengetahui ukuran daftar sehingga menggunakan operasi tambahan saat bertambah, menghabiskan buffer pra-alokasi:

# one item before filling pre-allocation buffer completely
>>> sys.getsizeof([i for i in [1,2,3]]) 
52
# fills pre-allocation buffer completely
# note that size did not change, we still have buffered unused nodes
>>> sys.getsizeof([i for i in [1,2,3,4]]) 
52
# grows pre-allocation buffer
>>> sys.getsizeof([i for i in [1,2,3,4,5]])
68

55
2017-10-13 10:40



Terima kasih semua untuk membantu saya memahami Python yang luar biasa itu.

Saya tidak ingin membuat pertanyaan yang masif (itulah sebabnya saya memposting jawaban), hanya ingin menunjukkan dan berbagi pemikiran saya.

Sebagai @ReutSharabani dicatat dengan benar: "daftar () menentukan ukuran daftar" secara deterministik. Anda dapat melihatnya dari grafik itu.

graph of sizes

Ketika kamu append atau menggunakan pemahaman daftar Anda selalu memiliki semacam batasan yang memanjang ketika Anda mencapai suatu titik. Dan dengan list() Anda memiliki batas yang hampir sama, tetapi mereka mengambang.

MEMPERBARUI

Terima kasih untuk @ReutSharabani, @tavo, @SvenFestersen

Untuk menyimpulkan: list() preallocates memori tergantung pada ukuran daftar, pemahaman daftar tidak bisa melakukan itu (itu meminta lebih banyak memori ketika dibutuhkan, suka .append()). S mengapa list() simpan lebih banyak memori.

Satu grafik lagi, pertunjukan itu list() pra-alokasi memori. Jadi garis hijau menunjukkan list(range(830)) menambahkan elemen demi elemen dan untuk sementara memori tidak berubah.

list() preallocates memory

PERBARUI 2

Seperti yang @Barmar catat dalam komentar di bawah ini, list() harus saya lebih cepat dari daftar pemahaman, jadi saya berlari timeit() dengan number=1000 untuk panjang list dari 4**0 untuk 4**10 dan hasilnya

time measurements


27
2017-10-13 11:37