Câu hỏi list () sử dụng nhiều bộ nhớ hơn là hiểu danh sách


Vì vậy, tôi đã chơi với list đối tượng và tìm thấy những điều kỳ lạ mà nếu list được tạo bằng list() nó sử dụng nhiều bộ nhớ hơn là hiểu danh sách? Tôi đang sử dụng 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

Từ tài liệu:

Danh sách có thể được xây dựng theo nhiều cách:

  • Sử dụng một cặp dấu ngoặc vuông để biểu thị danh sách trống: []
  • Sử dụng dấu ngoặc vuông, phân tách các mục bằng dấu phẩy: [a], [a, b, c]
  • Sử dụng một danh sách hiểu: [x for x in iterable]
  • Sử dụng hàm tạo kiểu: list() hoặc là list(iterable)

Nhưng có vẻ như sử dụng list() nó sử dụng nhiều bộ nhớ hơn.

Và càng nhiều list lớn hơn, khoảng cách tăng lên.

Difference in memory

Tại sao điều này xảy ra?

CẬP NHẬT # 1

Thử nghiệm với 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

CẬP NHẬT # 2

Thử nghiệm với 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

76
2017-10-13 10:25


gốc


Đó là một câu hỏi rất thú vị. Tôi có thể tái tạo hiện tượng này trong Python 3.4.3. Thậm chí thú vị hơn: trên Python 2.7.5 sys.getsizeof(list(range(100))) là 1016, getsizeof(range(100)) là 872 và getsizeof([i for i in range(100)]) là 920. Tất cả đều có loại list. - Sven Festersen
Quan tâm là sự khác biệt này cũng có trong Python 2.7.10 (mặc dù các con số thực tế khác với Python 3). Cũng ở đó trong 3,5 và 3,6b. - cdarke
Tôi nhận được các con số tương tự cho Python 2.7.6 như @SvenFestersen, cũng khi sử dụng xrange. - RemcoGerlich
Có một lời giải thích có thể có ở đây: stackoverflow.com/questions/7247298/size-of-list-in-memory. Nếu một trong các phương thức tạo danh sách bằng append(), có thể có sự phân bổ quá mức bộ nhớ. Tôi đoán cách duy nhất để thực sự làm rõ điều này là để có một cái nhìn tại các nguồn Python. - Sven Festersen


Các câu trả lời:


Tôi nghĩ bạn đang thấy các mẫu phân bổ quá mức, đây là mẫu từ nguồn:

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

In các kích thước của danh sách comprehensions độ dài 0-88 bạn có thể thấy các mô hình phù hợp:

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

Kết quả (định dạng là (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))

Việc phân bổ quá mức được thực hiện vì lý do hiệu suất cho phép các danh sách phát triển mà không cần phân bổ nhiều bộ nhớ hơn với mọi tăng trưởng (tốt hơn khấu hao hiệu suất).

Một lý do có thể xảy ra cho sự khác biệt với việc sử dụng tính năng hiểu danh sách, đó là việc hiểu danh sách không thể tính toán được kích thước của danh sách được tạo ra, nhưng list() có thể. Điều này có nghĩa là sự hiểu biết sẽ liên tục phát triển danh sách khi nó lấp đầy nó bằng cách sử dụng phân bổ quá mức cho đến khi cuối cùng lấp đầy nó.

Có thể là sẽ không phát triển bộ đệm phân bổ quá mức với các nút được cấp phát chưa được sử dụng khi nó được thực hiện (trên thực tế, trong hầu hết các trường hợp, nó sẽ không đánh bại mục đích phân bổ quá mức).

list()Tuy nhiên, có thể thêm một số bộ đệm không có vấn đề kích thước danh sách vì nó biết kích thước danh sách cuối cùng trước.


Một bằng chứng ủng hộ khác, cũng từ nguồn, là chúng ta thấy cách gọi danh sách LIST_APPEND, cho biết cách sử dụng list.resize, mà lần lượt chỉ ra tiêu thụ bộ đệm phân bổ trước mà không biết nó sẽ được lấp đầy bao nhiêu. Điều này phù hợp với hành vi bạn đang thấy.


Để kết luận, list() sẽ phân bổ trước nhiều nút hơn dưới dạng hàm của kích thước danh sách

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

Danh sách hiểu không biết kích thước danh sách để nó sử dụng các hoạt động chắp thêm khi nó phát triển, làm cạn kiệt bộ đệm phân bổ trước:

# 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

56
2017-10-13 10:40



Nhưng tại sao phân bổ quá mức xảy ra với một nhưng không phải là cái kia? - cdarke
Điều này đặc biệt là từ list.resize. Tôi không phải là một chuyên gia trong việc điều hướng thông qua nguồn của anh ta, nhưng nếu một cuộc gọi thay đổi kích thước và cái kia thì không - nó có thể giải thích sự khác biệt. - Reut Sharabani
Python 3.5.2 ở đây. Thử in kích cỡ danh sách từ 0 đến 35 trong vòng lặp. Đối với danh sách tôi thấy 64, 96, 104, 112, 120, 128, 136, 144, 160, 192, 200, 208, 216, 224, 232, 240, 256, 264, 272, 280, 288, 296, 304, 312, 328, 336, 344, 352, 360, 368, 376, 384, 400, 408, 416 và để hiểu 64, 96, 96, 96, 96, 128, 128, 128, 128, 192, 192, 192, 192, 192, 192, 192, 192, 264, 264, 264, 264, 264, 264, 264, 264, 264, 344, 344, 344, 344, 344, 344, 344, 344, 344. Tôi sẽ ngoại trừ hiểu rằng là một trong những người dường như preallocate bộ nhớ là thuật toán sử dụng nhiều RAM cho các kích cỡ nhất định. - tavo
Tôi mong đợi như vậy. Tôi có thể nhìn sâu hơn vào nó sớm thôi. Ý kiến ​​hay. - Reut Sharabani
thực ra list() xác định xác định kích thước danh sách, mà danh sách hiểu không thể làm. Điều này cho thấy việc hiểu danh sách không phải lúc nào cũng "kích hoạt" sự tăng trưởng "cuối cùng" của danh sách. Có thể có ý nghĩa. - Reut Sharabani


Cảm ơn tất cả mọi người đã giúp tôi hiểu rằng Python tuyệt vời.

Tôi không muốn đặt câu hỏi quá lớn (đó là lý do tại sao tôi đăng câu trả lời), chỉ muốn thể hiện và chia sẻ suy nghĩ của mình.

Như @ReutSharabani lưu ý chính xác: "list () xác định xác định kích thước danh sách". Bạn có thể thấy nó từ biểu đồ đó.

graph of sizes

Khi bạn append hoặc sử dụng danh sách hiểu bạn luôn có một số loại ranh giới kéo dài khi bạn đạt đến một số điểm. Và với list() bạn có gần như cùng ranh giới, nhưng chúng đang trôi nổi.

CẬP NHẬT

Vì vậy, nhờ @ReutSharabani, @tavo, @SvenFestersen

Tóm lại: list() preallocates bộ nhớ phụ thuộc vào kích thước danh sách, danh sách hiểu không thể làm điều đó (nó yêu cầu bộ nhớ nhiều hơn khi nó cần thiết, như .append()). Đó là lý do list() lưu trữ nhiều bộ nhớ hơn.

Một biểu đồ nữa, chương trình đó list() bộ nhớ preallocate. Vì vậy, dòng màu xanh lá cây cho thấy list(range(830)) phần tử chắp thêm theo phần tử và bộ nhớ trong khi không thay đổi.

list() preallocates memory

CẬP NHẬT 2

Như @Barmar đã lưu ý trong các bình luận bên dưới, list() phải tôi nhanh hơn danh sách hiểu, vì vậy tôi đã chạy timeit() với number=1000 cho chiều dài của list từ 4**0 đến 4**10 và kết quả là

time measurements


27
2017-10-13 11:37



Câu trả lời tại sao đường màu đỏ ở trên màu xanh là, khi list constructor có thể xác định kích thước của danh sách mới từ đối số của nó nó vẫn sẽ preallocate cùng một lượng không gian như nó sẽ nếu các yếu tố cuối cùng chỉ có và không có đủ không gian cho it.At ít nhất đó là những gì có ý nghĩa với tôi. - tavo
@tavo nó có vẻ giống với tôi, sau một thời điểm tôi muốn hiển thị nó trong biểu đồ. - vishes_shell
Vì vậy, trong khi việc hiểu danh sách sử dụng ít bộ nhớ hơn, chúng có thể chậm hơn đáng kể do tất cả các thay đổi kích thước xảy ra. Những điều này thường sẽ phải sao chép xương sống danh sách vào một vùng bộ nhớ mới. - Barmar
@Barmar thực sự tôi có thể chạy một số phép đo thời gian với range đối tượng (có thể thú vị). - vishes_shell
Và nó sẽ làm cho đồ thị của bạn thậm chí đẹp hơn. :) - Barmar