Cấu trúc và Hoạt động của Danh sách trong Python

Giới thiệu

Danh sách (list) là một trong những kiểu dữ liệu cơ bản và quan trọng nhất trong Python. Chúng ta có thể dễ dàng tạo ra các danh sách để lưu trữ nhiều loại dữ liệu khác nhau. Nhưng có bao giờ bạn tự hỏi danh sách trong Python thực sự hoạt động như thế nào không? Bài viết này sẽ giúp bạn khám phá những điều thú vị về danh sách, từ cách thức hoạt động bên trong cho đến những tối ưu hóa mà Python đang áp dụng để làm cho chúng trở nên linh hoạt và mạnh mẽ.

1. Cách thức danh sách hoạt động

Danh sách trong Python được định nghĩa bằng cú pháp đơn giản như sau:

myList = [1, 2, 3, 4]
for i in myList:
    print(i)

Tuy có vẻ đơn giản và trực quan, nhưng danh sách trong Python hoạt động rất khác biệt so với các mảng tĩnh trong C. Trong bài viết này, chúng ta sẽ đi sâu vào mã nguồn của CPython - phiên bản phổ biến nhất của Python - để hiểu rõ hơn về cách mà danh sách hoạt động.

1.1 Danh sách và C

Khi bạn chạy python3 trong terminal, bạn đang thực thi một chương trình được viết chủ yếu bằng ngôn ngữ C. Điều này có nghĩa là mọi khi bạn tạo một danh sách hay gọi phương thức .append(), bạn thực chất đang gọi một hàm C bên dưới. Để hiểu rõ hơn về danh sách, chúng ta cần xem xét mã nguồn C định nghĩa kiểu dữ liệu danh sách trong Python.

2. Đối tượng trong Python

Python là một ngôn ngữ lập trình hướng đối tượng, nhưng nó được xây dựng trên C - một ngôn ngữ không có các lớp hoặc đối tượng như chúng ta thường nghĩ. Vậy làm thế nào mà điều này lại có thể xảy ra?

Python sử dụng các cấu trúc (structs), con trỏ (pointers) và các hàm con trỏ để mô phỏng các tính năng của lập trình hướng đối tượng như đóng gói (Encapsulation), kế thừa (Inheritance) và đa hình (Polymorphism).

2.1 Đối tượng cơ bản - PyObject

PyObject là gốc của tất cả các đối tượng trong Python. Nó chứa các thông tin cần thiết để quản lý bộ nhớ và loại đối tượng. Dưới đây là định nghĩa của PyObject:

typedef struct _object {
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;

Phân tích thuộc tính

• ob_refcnt: Đếm số tham chiếu đến đối tượng. Khi giá trị này giảm xuống 0, Python sẽ tự động giải phóng bộ nhớ của đối tượng.
• ob_type: Là con trỏ tới PyTypeObject, kiểu dữ liệu chứa các thông tin về loại đối tượng.

2.2 Đối tượng có kích thước biến đổi - PyVarObject

Danh sách và chuỗi là những đối tượng có kích thước thay đổi. PyVarObject là nền tảng cho tất cả các đối tượng này:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;
} PyVarObject;

• ob_size: Lưu trữ số lượng mục hiện có trong danh sách hoặc chuỗi.

2.3 Đối tượng danh sách - PyListObject

Danh sách trong Python thực sự là một mảng tĩnh trong C. Dưới đây là cách PyListObject được định nghĩa:

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Phân tích thuộc tính

• ob_item: Là một mảng các con trỏ đến các đối tượng Python, cho phép danh sách lưu trữ các đối tượng khác nhau.
• allocated: Số lượng ô nhớ đã được cấp phát cho danh sách.

3. Danh sách trong hành động

Bây giờ chúng ta sẽ xem xét cách mà các phương thức của danh sách hoạt động thông qua các hàm C.

3.1 Tạo danh sách - PyList_New

Mọi danh sách đều bắt đầu từ việc gọi hàm PyList_New. Đây là hàm khởi tạo cho tất cả các đối tượng danh sách:

PyObject *
PyList_New(Py_ssize_t size)
{
    // Kiểm tra kích thước danh sách
    if (size < 0) {
        // ... xử lý lỗi ...
    }
    // Tạo danh sách mới
}

Hàm này sẽ kiểm tra xem có thể tái sử dụng đối tượng danh sách cũ hay không, và nếu không, nó sẽ cấp phát bộ nhớ mới cho danh sách.

3.2 Truy cập mục - PyList_GetItem

Khi bạn truy cập một mục trong danh sách thông qua chỉ số, hàm PyList_GetItem sẽ được gọi:

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    // Kiểm tra chỉ số hợp lệ
    return ((PyListObject *)op)->ob_item[i];
}

Hàm này sẽ thực hiện kiểm tra xem chỉ số có hợp lệ không và sau đó trả về mục tương ứng trong danh sách.

3.3 Tăng kích thước danh sách - list_resize

Hàm list_resize sẽ được gọi khi cần tăng kích thước của danh sách:

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    // Kiểm tra xem có đủ không gian không
    // Nếu không, cấp phát bộ nhớ mới
}

Hàm này giúp quản lý việc cấp phát bộ nhớ khi bạn thêm mục mới vào danh sách.

3.4 Thêm mục vào danh sách - list_append

Khi bạn gọi phương thức .append(), hàm list_append sẽ được gọi:

static PyObject *
list_append(PyListObject *self, PyObject *object)
{
    // Gọi hàm để thêm mục mới
}

Hàm này sẽ xử lý việc thêm mục mới vào danh sách và đảm bảo rằng không gian đủ để chứa mục mới.

3.5 Chèn mục - ins1

Hàm này sẽ xử lý việc chèn mục vào danh sách, có thể chậm hơn do cần dịch chuyển các mục khác:

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    // Kiểm tra và cấp phát bộ nhớ nếu cần thiết
    // Dịch chuyển các mục
}

3.6 Xóa mục - list_ass_slice

Việc xóa một mục cũng tương tự như chèn, nhưng cần phải lấp đầy khoảng trống:

static int
delete_one_item(PyListObject *self, Py_ssize_t i)
{
    // Dịch chuyển các mục để lấp khoảng trống
}

4. Kết luận

Sau khi tìm hiểu sâu về cách thức hoạt động của danh sách trong Python, chúng ta đã thấy rằng danh sách không phải là điều kỳ diệu mà là một cấu trúc rất thông minh dựa trên các mảng tĩnh trong C. Hiểu rõ cách hoạt động này sẽ giúp bạn tối ưu hóa mã của mình tốt hơn.

Nếu bạn có bất kỳ câu hỏi hoặc đề xuất nào, hãy liên hệ với tôi! Cảm ơn bạn đã đọc bài viết này!