15. Danh sách, bộ dữ liệu và mảng

Danh sách, bộ dữ liệu và các đối tượng giống như mảng biểu thị các bộ sưu tập có thứ tự. Tất cả chúng đều hỗ trợ quyền truy cập được lập chỉ mục, nhưng chúng có các mô hình lưu trữ, quy tắc có thể thay đổi và sự đánh đổi hiệu suất khác nhau.

Danh sách là một chuỗi các tham chiếu đối tượng có thể thay đổi.

Tuple là một chuỗi bất biến của các tham chiếu đối tượng.

Một đối tượng giống như mảng lưu trữ dữ liệu được gõ nhỏ gọn hoặc hiển thị bộ đệm liền kề.

Những khác biệt này rất quan trọng vì bộ chứa CPython lưu trữ các tham chiếu trừ khi loại đó được thiết kế riêng cho việc lưu trữ thô.

15.1 Bộ sưu tập đã đặt hàng

Python có một số loại bộ sưu tập được sắp xếp.

Một danh sách và một bộ dữ liệu có thể lưu trữ các đối tượng thuộc bất kỳ loại nào:python xs = [1, "two", object()] t = (1, "two", object()) Một mảng lưu trữ các giá trị của một loại cấp độ máy:```python from array import array

nums = array("i", [1, 2, 3])

Danh sách CPython lưu trữ các con trỏ tới các đối tượng Python.

Về mặt khái niệm:```text
PyListObject
    PyVarObject header
        ob_size = logical length
    ob_item ----> array of PyObject *
    allocated = capacity
```Vì:```python
xs = [10, 20, 30]
```cách bố trí là:```text
list object
    ob_size = 3
    allocated >= 3
    ob_item ----+
                |
                v
              [ptr][ptr][ptr]
                |    |    |
                v    v    v
               10   20   30
```Danh sách không chứa tải trọng số nguyên. Nó lưu trữ các tham chiếu đến các đối tượng số nguyên.

Đây là lý do tại sao một danh sách có thể chứa các loại hỗn hợp:```python
xs = [1, "hello", None, []]
```Mọi vị trí phần tử đều có cùng cách biểu diễn: a`PyObject *`.

## 15.3 Độ dài và dung lượng danh sách

Một danh sách có độ dài logic và dung lượng được phân bổ.```text
length
    number of active elements

capacity
    number of slots currently allocated in the internal array
```Ví dụ:```python
xs = []
xs.append("a")
xs.append("b")
xs.append("c")
```Độ dài logic là 3. Dung lượng được phân bổ có thể lớn hơn 3.

Dung lượng dự phòng này cho phép nối thêm hiệu quả. CPython thường không thay đổi kích thước mảng bên trong trên mỗi phần bổ sung. Nó phát triển mảng theo các bước lớn hơn.

Về mặt khái niệm:```text
append item
    if length < allocated:
        store item in spare slot
        length += 1
    else:
        allocate larger array
        copy references
        store item
        length += 1
```Danh tính đối tượng của danh sách vẫn ổn định. Mảng phần tử bên trong có thể di chuyển.```python
xs = []
before = id(xs)

for i in range(1000):
    xs.append(i)

after = id(xs)
print(before == after)   # True
```## 15.4 Nối thêm danh sách`list.append`thêm một tham chiếu đối tượng vào cuối.```python
xs = []
xs.append(1)
xs.append(2)
```Ở cấp độ C, nối thêm phải:```text
ensure there is enough capacity
increment the appended object's reference count
store the object pointer
increase the logical size
```Việc thêm một đối tượng không sao chép nó.```python
item = []
xs = []
xs.append(item)

item.append(1)
print(xs)        # [[1]]
```Danh sách lưu trữ một tham chiếu đến`item`.

## 15.5 Phân bổ quá mức danh sách

Việc phân bổ quá mức danh sách là lý do khiến việc bổ sung lặp lại có hiệu quả.

Nếu không phân bổ quá mức, vòng lặp này sẽ sao chép toàn bộ mảng trên nhiều lần lặp:```python
xs = []
for i in range(1_000_000):
    xs.append(i)
```Với việc phân bổ quá mức, CPython sẽ tăng công suất lên nhiều vị trí cùng một lúc. Công thức chính xác là chi tiết triển khai, nhưng hành vi cung cấp phần bổ sung theo thời gian không đổi được khấu hao.

Kết quả quan trọng:

| Hoạt động |     Chi phí trung bình |
| ------------------ | ---------------: |
|`append`           | `O(1)`khấu hao |
|`pop()`từ cuối |`O(1)`|
| lập chỉ mục ngẫu nhiên |`O(1)`|
| chèn ở phía trước |`O(n)`|
| xóa từ giữa |`O(n)`|

Việc bổ sung là rẻ vì nó chạm đến điểm cuối. Việc chèn ở phía trước rất tốn kém vì nhiều tài liệu tham khảo phải di chuyển.

## 15.6 Lập chỉ mục danh sách

Lập chỉ mục danh sách là truy cập mảng trực tiếp.```python
x = xs[i]
```Về mặt khái niệm:```text
check bounds
read ob_item[i]
return referenced object
```Điều này mang lại`O(1)`truy cập.

Các chỉ số phủ định được dịch:```python
xs[-1]
```có nghĩa:```text
xs[len(xs) - 1]
```sau khi xử lý giới hạn.

Lập chỉ mục trả về một tham chiếu đến đối tượng được chứa. Nó không sao chép đối tượng đó.```python
xs = [[1], [2]]
a = xs[0]
a.append(99)

print(xs)        # [[1, 99], [2]]
```## 15.7 Phân công danh sách

Việc gán mục danh sách sẽ thay thế một tham chiếu được lưu trữ.```python
xs = [1, 2, 3]
xs[1] = "two"
```Ở cấp độ C, việc thay thế phải xử lý số lượng tham chiếu một cách an toàn:```text
increment new item
store new item pointer
decrement old item
```Trật tự an toàn quan trọng khi đối tượng mới và đối tượng cũ có thể là cùng một đối tượng.

Về mặt khái niệm:```c
Py_INCREF(new_item);
old_item = items[index];
items[index] = new_item;
Py_DECREF(old_item);
```Điều này duy trì sự bất biến về quyền sở hữu ngay cả khi các công cụ hoàn thiện chạy trong`Py_DECREF`.

## 15.8 Cắt danh sách

Cắt lát sẽ tạo ra một danh sách mới.```python
xs = [[1], [2], [3]]
ys = xs[0:2]
```Danh sách mới chứa các tham chiếu đến các đối tượng phần tử giống nhau.```python
ys[0].append(99)

print(xs)    # [[1, 99], [2], [3]]
print(ys)    # [[1, 99], [2]]
```Đây là một bản sao nông.

Danh sách bên ngoài là mới. Các đối tượng chứa được chia sẻ.```text
xs ----> [ptr A][ptr B][ptr C]
ys ----> [ptr A][ptr B]
```Một bản sao sâu yêu cầu sao chép đệ quy:```python
import copy

ys = copy.deepcopy(xs)
```## 15.9 Chèn và xóa danh sách

Chèn vào giữa sẽ di chuyển các tham chiếu sau.```python
xs = [1, 2, 3, 4]
xs.insert(1, "x")
```Về mặt khái niệm:```text
[1][2][3][4]
insert at index 1
[1]["x"][2][3][4]
```Các phần tử từ chỉ số 1 trở đi dịch chuyển sang phải.

Xóa từ ca giữa bên trái:```python
del xs[1]
```Những hoạt động này được`O(n)`vì chúng có thể di chuyển nhiều con trỏ.

Bản thân các đối tượng không được sao chép. CPython di chuyển các tham chiếu bên trong mảng bên trong.

## 15.10 Sắp xếp danh sách`list.sort`sắp xếp danh sách tại chỗ.```python
xs = [3, 1, 2]
xs.sort()

sorted(xs)tạo một danh sách mới:python ys = sorted(xs) CPython sử dụng Timsort để sắp xếp danh sách. Nó ổn định, có nghĩa là các khóa bằng nhau vẫn giữ nguyên thứ tự tương đối của chúng.```python items = [ ("a", 2), ("b", 1), ("c", 2), ]

items.sort(key=lambda x: x[1]) print(items) # [('b', 1), ('a', 2), ('c', 2)]

## 15.11 Tuples Lưu trữ tài liệu tham khảo nội tuyến

Một tuple là một chuỗi bất biến.

Về mặt khái niệm:```text
PyTupleObject
    PyVarObject header
        ob_size = length
    ob_item[0]
    ob_item[1]
    ...
```Vì:```python
t = (10, 20, 30)
```cách bố trí là:```text
tuple object
    ob_size = 3
    ob_item[0] ---> 10
    ob_item[1] ---> 20
    ob_item[2] ---> 30
```Không giống như danh sách, các mục trong bộ dữ liệu được lưu trữ nội tuyến như một phần của việc phân bổ bộ dữ liệu. Không có mảng có thể thay đổi kích thước riêng biệt.

Điều này có thể thực hiện được vì độ dài của bộ dữ liệu không thể thay đổi sau khi tạo.

## 15.12 Tính bất biến của bộ dữ liệu

Tính bất biến của bộ dữ liệu có nghĩa là các tham chiếu mục của bộ dữ liệu không thể thay đổi.```python
t = (1, 2, 3)
t[0] = 99        # TypeError
```Đối tượng tuple vẫn lưu trữ các tham chiếu. Nếu một đối tượng được tham chiếu có thể thay đổi thì đối tượng đó có thể thay đổi.```python
t = ([],)
t[0].append("x")

print(t)         # (['x'],)
```Tuple vẫn trỏ đến cùng một danh sách. Danh sách đã thay đổi.

Sự khác biệt này rất quan trọng đối với việc băm.```python
hash((1, 2, 3))      # works
hash(([],))          # TypeError
```Một bộ dữ liệu chỉ có thể băm được nếu tất cả các phần tử đều có thể băm được.

## 15.13 Tạo bộ dữ liệu

Tuple nghĩa đen là phổ biến:```python
t = (1, 2, 3)
```Chỉ riêng dấu ngoặc đơn không tạo ra một bộ dữ liệu. Dấu phẩy có.```python
a = (1)
b = (1,)

print(type(a))   # int
print(type(b))   # tuple
```Bộ dữ liệu được sử dụng nhiều trong nội bộ để:```text
function arguments
multiple return values
constant groups
dictionary keys
bytecode constants
C API argument packing
```Bởi vì các bộ dữ liệu là bất biến và nhỏ gọn nên chúng là nơi chứa tự nhiên cho các nhóm cố định.

## 15.14 Đóng gói và giải nén Tuple

Python sử dụng bộ dữ liệu để đóng gói nhiều giá trị.```python
point = 10, 20
```Điều này tạo ra một tuple.

Giải nén các phần tử trích xuất:```python
x, y = point
```Ở cấp độ bytecode, việc đóng gói và giải nén có các hướng dẫn riêng vì chúng phổ biến.

Giải nén mở rộng:```python
first, *middle, last = [1, 2, 3, 4, 5]
```tạo một danh sách cho mục tiêu được gắn dấu sao.```python
print(middle)    # [2, 3, 4]
```## 15.15 Danh sách so với bộ dữ liệu

Danh sách và bộ dữ liệu có hành vi lập chỉ mục tương tự nhưng mục tiêu thiết kế khác nhau.

| Tính năng | Danh sách | Bộ dữ liệu |
| ---------- | ------------------------ | ------------------------ |
| Khả năng thay đổi | Có thể thay đổi | Bất biến |
| Chiều dài | Có thể thay đổi | Đã sửa |
| Lưu trữ | Mảng có thể thay đổi kích thước riêng biệt | Tài liệu tham khảo mục nội tuyến |
| Nối thêm | Có | Không |
| Có thể băm | Không | Nếu các phần tử có thể băm được |
| Công dụng chính | Trình tự có thể thay đổi | Nhóm hoặc bản ghi cố định |
| Cú pháp |`[1, 2]`                 | `(1, 2)`|

Sử dụng danh sách khi bộ sưu tập thay đổi.

Sử dụng bộ dữ liệu khi bộ sưu tập đại diện cho một nhóm cố định.

## 15.16 Mảng lưu trữ giá trị thô`array.array`lưu trữ các giá trị được gõ nhỏ gọn, không phải tham chiếu đối tượng Python.```python
from array import array

xs = array("i", [1, 2, 3])
```Mã loại kiểm soát biểu diễn cấp độ C.

Ví dụ:

| Nhập mã | Ý nghĩa |
| --------- | -------------- |
|`"b"`| char đã ký |
|`"B"`| ký tự không dấu |
|`"h"`| ký ngắn |
|`"H"`| ngắn không dấu |
|`"i"`| đã ký int |
|`"I"`| int không dấu |
|`"l"`| ký dài |
|`"L"`| không dấu dài |
|`"f"`| phao |
|`"d"`| đôi |

Một mảng số nguyên nhỏ gọn hơn nhiều so với danh sách các đối tượng số nguyên trong Python.

Về mặt khái niệm:```text
list of ints
    [ptr][ptr][ptr]
      |    |    |
      v    v    v
     int  int  int

array("i")
    [raw int][raw int][raw int]
```## 15.17 Sự đánh đổi mảng

Mảng nhỏ gọn nhưng ít tổng quát hơn danh sách.

| Tính năng | Danh sách |`array.array`|
| --------------------- | --------------------------------------------- | ---------------------------- |
| Các loại phần tử | Bất kỳ đối tượng Python nào | Một kiểu nguyên thủy |
| Sử dụng bộ nhớ | Cao hơn | Hạ |
| Tính cô đọng về số | Nghèo | Tốt |
| Phương thức đối tượng Python | Tài liệu tham khảo đối tượng đầy đủ | Giá trị được chuyển đổi tại ranh giới |
| Dữ liệu không đồng nhất | Có | Không |
| Giao thức đệm | Không sử dụng bộ đệm số thô trực tiếp như mảng | Có |

Mảng rất hữu ích cho I/O nhị phân, lưu trữ số nhỏ gọn và dữ liệu tương thích với bộ đệm.

Đối với tính toán số nặng, các mảng của bên thứ ba như mảng NumPy thường mạnh hơn.

## 15,18 byte dưới dạng mảng byte`bytes`là một chuỗi byte bất biến.```python
b = b"abc"

print(b[0])     # 97
```Nó hoạt động giống như chuỗi nhưng lưu trữ byte thô.`bytearray`là phiên bản có thể thay đổi:```python
buf = bytearray(b"abc")
buf[0] = 65

print(buf)      # bytearray(b'Abc')
```Đối với dữ liệu nhị phân,`bytes`Và`bytearray`nhỏ gọn hơn`list[int]`.

```python
data = [97, 98, 99]     # list of Python int objects
raw = b"abc"            # compact bytes
```## 15.19 Chế độ xem bộ nhớ và Cắt không sao chép

A`memoryview`có thể hiển thị chế độ xem vào bộ đệm hiện có.```python
buf = bytearray(b"abcdef")
view = memoryview(buf)[2:5]

print(view.tobytes())   # b'cde'
```Chế độ xem không sao chép các byte cơ bản.

Việc thay đổi thông qua chế độ xem có thể ghi sẽ ảnh hưởng đến nhà xuất khẩu:```python
buf = bytearray(b"abcdef")
view = memoryview(buf)

view[0] = ord("X")

print(buf)              # bytearray(b'Xbcdef')
```Điều này hữu ích cho các trình phân tích cú pháp nhị phân, giao thức mạng, định dạng tệp và mô-đun mở rộng.

## 15.20 Giao thức tuần tự

Danh sách, bộ dữ liệu, byte, mảng byte, phạm vi và mảng tham gia vào hành vi trình tự.

Các thao tác chung:```python
len(xs)
xs[i]
xs[i:j]
x in xs
for x in xs:
    ...
```Loại quyết định cách thực hiện các hoạt động đó.

Ở cấp độ C, hành vi trình tự được thể hiện thông qua các khe trình tự như:```text
sq_length
sq_item
sq_ass_item
sq_contains
sq_concat
sq_repeat
```Trình tự bất biến bỏ qua các vị trí phân công.

Trình tự có thể thay đổi cung cấp hành vi chuyển nhượng.

## 15.21 Lặp lại

Trình lặp danh sách lưu trữ tham chiếu đến danh sách và chỉ mục hiện tại.```python
xs = [1, 2, 3]
it = iter(xs)

print(next(it))    # 1
```Về mặt khái niệm:```text
list iterator
    sequence reference
    current index
```Việc lặp lại một bộ dữ liệu cũng tương tự.

Lặp lại danh sách sẽ thấy đối tượng danh sách chứ không phải bản sao ảnh chụp nhanh.```python
xs = [1, 2, 3]

for x in xs:
    if x == 2:
        xs.append(4)
```Việc thay đổi danh sách trong quá trình lặp có thể tạo ra hành vi khó hiểu. Tránh nó trừ khi hành vi được kiểm soát có chủ ý.

## 15.22 Kiểm tra tư cách thành viên

Đối với một danh sách hoặc bộ dữ liệu:```python
x in xs
```thực hiện quét tuyến tính.

Về mặt khái niệm:```text
for each item:
    compare item == x
```Đây là`O(n)`.

Đối với khối lượng công việc nặng về thành viên, hãy sử dụng một bộ hoặc lệnh:```python
seen = set(xs)

if x in seen:
    ...
```Một tập hợp sử dụng hàm băm và thường cho kết quả trung bình`O(1)`thành viên.

## 15.23 Sao chép

Danh sách các phương pháp sao chép còn nông cạn:```python
a = [[1], [2]]

b = a.copy()
c = list(a)
d = a[:]
```Cả ba đều tạo ra một danh sách bên ngoài mới. Các đối tượng bên trong được chia sẻ.```python
b[0].append(99)

print(a)    # [[1, 99], [2]]
```Sao chép bộ dữ liệu thường trả về cùng một đối tượng khi không cần bản sao thực:```python
t = (1, 2, 3)
u = tuple(t)

print(t is u)    # True
```Bởi vì các bộ dữ liệu là bất biến nên việc sử dụng lại này là an toàn.

## 15.24 Lặp lại

Trình tự lặp lại lặp lại các tài liệu tham khảo.```python
xs = [[]] * 3
xs[0].append(1)

print(xs)        # [[1], [1], [1]]
```Cả ba vị trí đều trỏ đến cùng một danh sách bên trong.

Đúng mẫu:```python
xs = [[] for _ in range(3)]
```Bây giờ mỗi phần tử là một danh sách khác nhau.

Đây là sự cố về mô hình tham chiếu chứ không phải lỗi nhân danh sách.

## 15.25 Sắp xếp danh sách đối tượng

Sắp xếp sử dụng so sánh hoặc một chức năng chính.```python
items = ["aaa", "b", "cc"]
items.sort(key=len)
```Với`key`, CPython tính toán các khóa và sắp xếp bằng cách sử dụng các khóa đó.

Điều này tránh việc tính toán lại nhiều lần logic so sánh đắt tiền.

Sắp xếp ổn định cho phép sắp xếp nhiều lượt:```python
items.sort(key=lambda x: x.name)
items.sort(key=lambda x: x.group)
```Sau lần sắp xếp thứ hai, các mục có nhóm bằng nhau sẽ giữ nguyên thứ tự tên từ lần sắp xếp đầu tiên.

## 15.26 Hiểu danh sách

Việc hiểu danh sách sẽ xây dựng một danh sách trực tiếp.```python
squares = [x * x for x in range(10)]
```Nó thường nhanh hơn và rõ ràng hơn các vòng lặp nối thêm thủ công đối với các phép biến đổi đơn giản.

Hình dạng tương đương:```python
squares = []
for x in range(10):
    squares.append(x * x)
```Sự hiểu biết có các mẫu mã byte chuyên dụng và giữ cho thân vòng lặp nhỏ gọn.

## 15.27 Biểu thức trình tạo so với Danh sách

Việc hiểu danh sách sẽ tạo ra tất cả các phần tử ngay lập tức.```python
xs = [x * x for x in range(1_000_000)]
```Một biểu thức trình tạo tạo ra các giá trị một cách lười biếng.```python
it = (x * x for x in range(1_000_000))
```Sử dụng danh sách khi bạn cần lập chỉ mục, truyền tải lặp lại hoặc dữ liệu cụ thể hóa.

Sử dụng trình tạo khi bạn cần một lượt và muốn tránh lưu trữ tất cả kết quả.

## 15.28 Các mẫu hiệu suất phổ biến

| Nhiệm vụ | Lựa chọn tốt hơn | Lý do |
| ------------------------ | ---------------------- | -------------------------- |
| Nối nhiều mục |`list.append`| Khấu hao`O(1)`|
| Xây dựng từ lặp lại |`list(iterable)`| Đường dẫn xây dựng hiệu quả |
| Bản ghi cố định |`tuple`| Bất biến và nhỏ gọn |
| Kiểm tra tư cách thành viên |`set`| Tra cứu dựa trên hàm băm |
| Xếp hàng từ trái |`collections.deque`| Pop trái hiệu quả |
| Lưu trữ số nhỏ gọn |`array.array`hoặc NumPy | Lưu trữ đánh máy thô |
| Dữ liệu nhị phân |`bytes`hoặc`bytearray`| Lưu trữ byte nhỏ gọn |
| Cắt nhị phân không sao chép |`memoryview`| Tránh phân bổ |
| Nhiều nối |`join`| Tránh sao chép nhiều lần |

Danh sách có mục đích chung. Chúng không tối ưu cho mọi khối lượng công việc được đặt hàng.

##15.29 Những lỗi thường gặp

Một số lỗi phổ biến xuất phát trực tiếp từ mô hình vùng chứa dựa trên tham chiếu của CPython.

Danh sách bên trong được chia sẻ:```python
matrix = [[0] * 3] * 3
```Tốt hơn:```python
matrix = [[0] * 3 for _ in range(3)]
```Sử dụng tư cách thành viên danh sách cho các bộ tra cứu lớn:```python
if user_id in user_ids_list:
    ...
```Tốt hơn:```python
user_ids = set(user_ids_list)
if user_id in user_ids:
    ...
```Xóa trước nhiều lần:```python
while xs:
    xs.pop(0)
```Tốt hơn:```python
from collections import deque

q = deque(xs)
while q:
    q.popleft()
```Nối chuỗi hoặc byte lặp lại:```python
s = ""
for part in parts:
    s += part
```Tốt hơn:```python
s = "".join(parts)
```## 15.30 Bản phác thảo API C

Tạo danh sách:```c
PyObject *list = PyList_New(0);
if (list == NULL) {
    return NULL;
}
```Nối thêm:```c
PyObject *item = PyLong_FromLong(42);
if (item == NULL) {
    Py_DECREF(list);
    return NULL;
}

if (PyList_Append(list, item) < 0) {
    Py_DECREF(item);
    Py_DECREF(list);
    return NULL;
}

Py_DECREF(item);