List và Tuple trong bộ nhớ: mảng động, over-allocation và deque

Bạn dùng list hằng ngày, nhưng có biết vì sao append nhanh mà insert(0, x) lại chậm? Vì sao [1, 2, 3] tốn 88 byte còn (1, 2, 3) chỉ 64 byte? Bài này mổ xẻ cách CPython tổ chức list và tuple trong bộ nhớ.

Trong bài này, bạn sẽ học:

• Cấu trúc bên trong của list: mảng động chứa con trỏ
• Cơ chế over-allocation và vì sao append là O(1) khấu hao
• Độ phức tạp thật của từng thao tác list và các bẫy hiệu năng phổ biến
• Vì sao Timsort đặc biệt nhanh với dữ liệu thực tế
• deque được tổ chức ra sao và khi nào nên dùng
• Vì sao tuple nhẹ và nhanh hơn list, và những “bất biến” không hoàn toàn bất biến

1. List là một mảng động các con trỏ

Cấu trúc C của list (rút gọn):

typedef struct {
    PyObject_VAR_HEAD        // refcount, type, ob_size (= len(list))
    PyObject **ob_item;      // con trỏ tới mảng các con trỏ PyObject*
    Py_ssize_t allocated;    // số ô ĐÃ cấp phát (>= ob_size)
} PyListObject;

PyListObject (56 byte)                  mảng ob_item (cấp phát riêng)
┌───────────────────┐                 ┌─────┬─────┬─────┬─────┐
│ refcnt, type      │                 │ ptr │ ptr │ ptr │ --- │  allocated = 4
│ ob_size   = 3     │                 └──┬──┴──┬──┴──┬──┴─────┘  ob_size   = 3
│ ob_item   ────────┼───────────────►     │     │     │
│ allocated = 4     │                    "a"    42   [..]   (object thật nằm rải rác)
└───────────────────┘

Ba điều quan trọng rút ra:

1. List không chứa object, nó chứa con trỏ (8 byte mỗi phần tử). Vì vậy một list có thể chứa mọi kiểu dữ liệu lẫn lộn.
2. Mảng con trỏ nằm liền nhau trong bộ nhớ nên l[i] là O(1): chỉ cần tính ob_item + i*8.
3. List thường cấp phát dư (allocated > ob_size) để append không phải xin bộ nhớ mỗi lần.

2. Over-allocation: quan sát list “lớn dần”

import sys

l = []
prev = -1
for i in range(70):
    size = sys.getsizeof(l)
    if size != prev:
        capacity = (size - 56) // 8
        print(f"len={len(l):3}  capacity={capacity}")
        prev = size
    l.append(i)

Kết quả (CPython 3.13):

len=  0  capacity=0
len=  1  capacity=4
len=  5  capacity=8
len=  9  capacity=16
len= 17  capacity=24
len= 25  capacity=32
len= 33  capacity=40
len= 41  capacity=52
len= 53  capacity=64
len= 65  capacity=76

Công thức trong listobject.c là khoảng new_allocated = n + n/8 + 6 (làm tròn xuống bội của 4). Tức là mỗi lần đầy, list lớn thêm khoảng 12.5%.

Vì sao append là O(1) “khấu hao”?

Khi mảng đầy, CPython phải realloc sang vùng nhớ lớn hơn và sao chép toàn bộ con trỏ - thao tác O(n). Nhưng vì mỗi lần tăng theo tỉ lệ, số lần phải sao chép là rất ít. Tính trung bình trên nhiều lần append, chi phí mỗi lần là hằng số - gọi là amortized O(1).

Cùng nội dung nhưng khác kích thước

import sys
print(sys.getsizeof([1, 2, 3]))            # 88  (literal: dư chỗ)
print(sys.getsizeof(list(range(5))))       # 104
print(sys.getsizeof([x for x in range(5)]))# 120 (comprehension: append dần -> dư nhiều hơn)
print(sys.getsizeof([None] * 5))           # 96  (biết trước kích thước -> vừa khít)

Cách tạo list ảnh hưởng đến lượng bộ nhớ dư. Với hàng triệu list nhỏ, sự khác biệt này đáng kể.

List co lại khi xoá bớt

import sys
l = list(range(1000))
print(sys.getsizeof(l))   # 8056
del l[100:]
print(sys.getsizeof(l))   # 984 - CPython trả bớt bộ nhớ khi len < allocated/2
l.clear()
print(sys.getsizeof(l))   # 56

3. Độ phức tạp thật của các thao tác list

Thao tác	Độ phức tạp	Lý do
l[i], l[i] = x	O(1)	tính địa chỉ trực tiếp
l.append(x)	O(1) khấu hao	có chỗ dư
l.pop()	O(1)	bỏ phần tử cuối
l.insert(0, x), l.pop(0)	O(n)	phải dịch toàn bộ con trỏ sang phải/trái
x in l, l.index(x), l.remove(x)	O(n)	duyệt tuần tự, gọi __eq__ từng phần tử
l[a:b]	O(b-a)	tạo list mới, copy con trỏ
l.sort()	O(n log n)	Timsort (Powersort từ 3.11), rất nhanh với dữ liệu gần có thứ tự
len(l)	O(1)	đọc ob_size

Bẫy phổ biến: dùng list làm hàng đợi

import timeit

# 10.000 lần thêm/xoá ở đầu một list 100.000 phần tử
t_list = timeit.timeit(
    "l.insert(0, 1); l.pop(0)",
    "l = list(range(100_000))", number=10_000)

t_deque = timeit.timeit(
    "d.appendleft(1); d.popleft()",
    "from collections import deque; d = deque(range(100_000))", number=10_000)

print(f"list : {t_list:.4f}s")   # ~0.66s
print(f"deque: {t_deque:.4f}s")  # ~0.0004s  -> nhanh hơn ~1000 lần

Bẫy phổ biến: in trên list lớn

import timeit
print(timeit.timeit("x in s", "s = list(range(10_000)); x = 9999", number=10_000))  # ~0.57s
print(timeit.timeit("x in s", "s = set(range(10_000)); x = 9999", number=10_000))   # ~0.0002s

Nếu bạn kiểm tra in nhiều lần, hãy chuyển sang set hoặc dict (xem bài Dict và Set: bảng băm).

Timsort: sắp xếp “thông minh” với dữ liệu thực tế

list.sort() và sorted() dùng Timsort (từ 3.11 dùng chiến lược gộp Powersort), một thuật toán lai giữa merge sort và insertion sort do Tim Peters thiết kế riêng cho Python. Ý tưởng then chốt: dữ liệu thực tế hiếm khi hoàn toàn ngẫu nhiên - nó thường chứa sẵn những đoạn đã có thứ tự (gọi là run). Timsort tìm các run đó rồi gộp chúng lại.

import random
import timeit

n = 1_000_000
random_data = [random.random() for _ in range(n)]
sorted_data = sorted(random_data)
nearly_sorted = sorted_data[:]
for _ in range(10):                          # xáo trộn 10 vị trí
    nearly_sorted[random.randrange(n)] = random.random()
reversed_data = sorted_data[::-1]

for name, data in [("ngẫu nhiên", random_data), ("đã sắp xếp", sorted_data),
                   ("gần sắp xếp", nearly_sorted), ("đảo ngược", reversed_data)]:
    t = timeit.timeit(lambda: sorted(data), number=3) / 3
    print(f"{name:12} {t:.4f}s")

ngẫu nhiên   0.1507s
đã sắp xếp   0.0191s
gần sắp xếp  0.0197s
đảo ngược    0.0212s

Dữ liệu gần có thứ tự được sắp xếp nhanh gấp ~8 lần dữ liệu ngẫu nhiên (O(n) thay vì O(n log n)). Hệ quả thực tế:

• Thêm vài phần tử vào một list đã sắp xếp rồi gọi sort() lại là rẻ - thường không cần tự cài chèn nhị phân.
• Timsort là stable (ổn định): các phần tử bằng nhau giữ nguyên thứ tự ban đầu. Nhờ vậy có thể sắp xếp nhiều khoá bằng nhiều lần sort, từ khoá phụ tới khoá chính:

students = [("An", "B"), ("Bình", "A"), ("Chi", "B"), ("Dũng", "A")]
students.sort(key=lambda s: s[0])     # khoá phụ: tên
students.sort(key=lambda s: s[1])     # khoá chính: lớp - thứ tự tên trong mỗi lớp được giữ
print(students)   # [('Bình', 'A'), ('Dũng', 'A'), ('An', 'B'), ('Chi', 'B')]

• Dùng key= thay vì so sánh tự viết: hàm key chỉ được gọi một lần mỗi phần tử, còn so sánh được gọi O(n log n) lần.

4. collections.deque - danh sách liên kết các khối

deque không phải mảng liền mạch mà là danh sách liên kết đôi các khối, mỗi khối chứa 64 con trỏ:

        ┌──────────────┐     ┌──────────────┐     ┌──────────────┐
None ◄──┤ block (64)   │◄───►│ block (64)   │◄───►│ block (64)   ├──► None
        └──────────────┘     └──────────────┘     └──────────────┘
          ▲ leftindex                                    ▲ rightindex

• Thêm/xoá ở hai đầu: O(1) thật sự (không phải khấu hao).
• Truy cập d[i] ở giữa: O(n) - phải nhảy qua các khối. Đừng dùng deque khi cần truy cập ngẫu nhiên.
• deque(maxlen=N) tự động bỏ phần tử cũ - rất hợp để giữ “N dòng log gần nhất”:

from collections import deque

last_lines = deque(maxlen=3)
for line in ["a", "b", "c", "d", "e"]:
    last_lines.append(line)
print(last_lines)   # deque(['c', 'd', 'e'], maxlen=3)

5. Tuple - mảng cố định, nhẹ hơn list

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];   // các con trỏ nằm NGAY trong object, không cấp phát riêng
} PyTupleObject;

Khác biệt so với list:

• Không có trường allocated, không cấp phát dư.
• Mảng con trỏ nằm ngay trong object → chỉ một lần cấp phát bộ nhớ thay vì hai.

import sys
print(sys.getsizeof((1, 2, 3)))  # 64
print(sys.getsizeof([1, 2, 3]))  # 88

Tuple hằng được tạo sẵn lúc biên dịch

import dis
dis.dis("x = (1, 2, 3)")
#   LOAD_CONST   ((1, 2, 3))     <- tuple có sẵn trong code object
#   STORE_NAME   x

dis.dis("x = [1, 2, 3]")
#   BUILD_LIST   0
#   LOAD_CONST   ((1, 2, 3))
#   LIST_EXTEND  1                <- phải tạo list mới mỗi lần chạy
#   STORE_NAME   x

Vì vậy tạo tuple hằng nhanh hơn tạo list khoảng 3-4 lần:

import timeit
print(timeit.timeit("(1, 2, 3, 4, 5)", number=10**6))  # ~0.009s
print(timeit.timeit("[1, 2, 3, 4, 5]", number=10**6))  # ~0.034s

Freelist: tái sử dụng tuple nhỏ

CPython giữ một “kho” (freelist) các tuple nhỏ (dưới 20 phần tử) đã bị giải phóng để tái sử dụng, tránh gọi bộ cấp phát. Tuple rỗng () là một singleton duy nhất. Đây là lý do các hàm trả về (a, b) rất rẻ.

Tuple bất biến, nhưng nội dung chưa chắc

Tuple chỉ đảm bảo các con trỏ không đổi. Nếu con trỏ trỏ tới object mutable, object đó vẫn thay đổi được:

t = (1, [2])
try:
    t[1] += [3]
except TypeError as e:
    print("TypeError:", e)
print(t)   # (1, [2, 3])  <- báo lỗi NHƯNG list vẫn bị thay đổi!

t[1] += [3] thực hiện hai bước: t[1].__iadd__([3]) (thành công, list đã đổi) rồi t[1] = ... (thất bại vì tuple bất biến). Hệ quả khác: tuple chứa list không hash được, nên không dùng làm key của dict.

6. Slicing và copy chỉ copy con trỏ

a = [[0] * 3] * 3      # 3 con trỏ tới CÙNG MỘT list con
a[0][0] = 1
print(a)               # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

b = [[0] * 3 for _ in range(3)]   # 3 list con khác nhau

Mọi thao tác l[:], list(l), l.copy(), l * n đều là shallow copy: tạo mảng con trỏ mới nhưng trỏ tới cùng các object cũ. Riêng với tuple, t[:] trả về chính t (vì bất biến nên không cần copy).

7. Một số lời khuyên thực tế

• Không cần “cấp phát trước” list bằng [None] * n để tăng tốc - trong CPython, append hoặc list comprehension đã đủ nhanh, comprehension thường là nhanh nhất.
• Dùng tuple cho dữ liệu cố định (toạ độ, bản ghi), đặc biệt khi có hàng triệu bản ghi - tiết kiệm bộ nhớ và nhanh hơn khi tạo.
• Dùng deque cho hàng đợi, BFS, cửa sổ trượt.
• Dùng array hoặc NumPy cho dãy số lớn cùng kiểu (xem bài Buffer protocol & memoryview).
• Dùng set/dict khi cần tra cứu in thường xuyên.

Bài tập

1. Viết chương trình in ra dãy capacity của list khi append từ 0 tới 1000 phần tử, rồi tính tỉ lệ tăng trung bình giữa các lần cấp phát.
2. Cài đặt BFS trên đồ thị 100.000 đỉnh hai lần: dùng list.pop(0) và dùng deque.popleft(). So sánh thời gian.
3. Giải thích vì sao t = ([],); t[0].append(1) chạy được nhưng hash(t) lại lỗi.

Kết luận

Bạn đã đi qua những kiến thức cốt lõi của bài này:

	list	tuple	deque
Cấu trúc	mảng động con trỏ	mảng cố định con trỏ	danh sách liên kết các khối 64 ô
Truy cập [i]	O(1)	O(1)	O(n)
Thêm/xoá cuối	O(1) khấu hao	không	O(1)
Thêm/xoá đầu	O(n)	không	O(1)
Bộ nhớ	có phần dư	vừa khít	theo khối
Hash được	không	có (nếu phần tử hash được)	không

Bài tiếp theo: Dict và Set: bảng băm bên trong.