Tại sao là một danh sách được sắp xếp lớn hơn một danh sách không được phân loại

Question

tôi có một danh sách my_list (danh sách có chứa chuỗi utf8):

>>> len(my_list) 
8777 
>>> getsizeof(my_list)      # <-- note the size 
77848 

Đối với một số lý do, một danh sách sắp xếp (my_sorted_list = sorted(my_list)) sử dụng nhiều bộ nhớ hơn:

>>> len(my_sorted_list) 
8777 
>>> getsizeof(my_sorted_list)    # <-- note the size 
79104 

Tại sao sorted trả về danh sách chiếm nhiều không gian hơn bộ nhớ so với danh sách chưa được phân loại ban đầu?

Answer 1

Là Ignacio points out, điều này là do Python phân bổ bộ nhớ nhiều hơn một chút so với yêu cầu. Việc này được thực hiện để thực hiện O(1).appends trên danh sách.

sortedcreates a new list ngoài chuỗi được cung cấp, sorts it in place và trả lại. Để tạo danh sách mới, Python extends an empty sized list with the one passed; dẫn đến việc phân bổ quá mức được quan sát (xảy ra sau khi gọi list_resize). Bạn có thể chứng thực một thực tế rằng phân loại không phải là thủ phạm bằng cách sử dụng list.sort; thuật toán tương tự được sử dụng mà không có danh sách mới được tạo (hoặc, được biết, đó là được thực hiện tại chỗ). Các kích thước ở đó, tất nhiên, không khác nhau.

Điều đáng chú ý là sự khác biệt này chủ yếu là mặt khi:

• Danh sách ban đầu được tạo ra với một danh sách-comp (ở đâu, nếu không gian có sẵn và the final append doesn't trigger a resize, kích thước nhỏ hơn).

• Khi sử dụng danh sách các chữ cái. Có a PyList_New is created based on the number of values on the stack và không có phụ thêm được thực hiện. Direct assigning to the underlying array is performed) mà không gây ra bất kỳ thay đổi kích thước và giữ kích thước tối thiểu của nó:

Như vậy, với một danh sách-comp:

l = [i for i in range(10)] 

getsizeof(l)   # 192 
getsizeof(sorted(l)) # 200 

Hoặc một danh sách đen:

l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

getsizeof(l)   # 144 
getsizeof(sorted(l)) # 200 

kích thước nhỏ hơn (nhiều hơn thế với việc sử dụng các chữ).

Khi tạo thông qua list, bộ nhớ luôn được phân phối quá mức; Python knows the sizes và có cản thay đổi tương lai bằng quá phân bổ một chút dựa trên kích thước:

l = list(range(10)) 

getsizeof(l)   # 200 
getsizeof(sorted(l)) # 200 

Vì vậy, bạn không nhận được sự khác biệt quan sát được trong các kích thước của danh sách (s).

---

Là một lưu ý cuối cùng, tôi phải chỉ ra rằng đây là một hành vi cụ thể thi C của Python tức là CPython.Đó là một chi tiết về cách ngôn ngữ được thực hiện và như vậy, bạn không nên phụ thuộc vào nó trong bất kỳ cách thức lập dị.

Jython, IronPython, PyPy và bất kỳ triển khai nào khác có thể/có thể không có hành vi tương tự.

Answer 2

list resize operation tổng quát để phân bổ phụ thêm vào danh sách so với bắt đầu với danh sách được trình biên dịch giải thích.