Triển khai Dynamic Array (Mảng động) trong Python

Dynamic Array

Trong Python, list, set, dictionary là mutable objects. Số, string, tuple là immutable. Mutable nghĩa là có thể thêm/xóa item từ list, set, dict, không đúng với immutable như tuple, string.

Trong Python, list chính là dynamic array. Thử tạo dynamic list:

>>> list1 = []
>>> type(list1)

Thêm item vào list rỗng:

>>> list1 = [2, 4, 6]
>>> list1
[2, 4, 6]
>>> list1.append('Tutorialspoint')
>>> list1
[2, 4, 6, 'Tutorialspoint']

Xóa item từ list:

>>> list1.pop()
'Tutorialspoint'
>>> list1
[2, 4, 6]

List thực sự là mở rộng của array, có thể sửa đổi kích thước (tăng/giảm). Bắt đầu list size "zero", thêm "bốn" item.

Cơ bản triển khai Dynamic Array

Xét ví dụ list list1 append khi array đầy, cần thực hiện:

• Cấp phát array mới list2 với capacity lớn hơn
• Gán list2[i] = list1[i], với i = 0,1...n-1, n là số item hiện tại
• Gán list1 = list2, bây giờ list2 tham chiếu list mới
• Chèn (append) item mới vào list (list1)

Đây là cơ sở triển khai dynamic array.

Tạo code triển khai khái niệm dynamic array. Tự tạo class dynamic array dùng thư viện built-in ctypes như raw array từ module ctypes.

dynamicArray.py

import ctypes

class DynamicArray(object):
    def __init__(self):
        self.n = 0           # số phần tử hiện tại
        self.capacity = 1    # dung lượng mặc định
        self.A = self.make_array(self.capacity)

    def __len__(self):
        return self.n

    def __getitem__(self, k):
        if not 0 <= k < self.n:
            return IndexError('k is out of bounds')
        return self.A[k]

    def append(self, element):
        if self.n == self.capacity:
            self.resize(2 * self.capacity)
        self.A[self.n] = element
        self.n += 1

    def _resize(self, new_cap):
        B = self.make_array(new_cap)
        for k in range(self.n):
            B[k] = self.A[k]
        self.A = B
        self.capacity = new_cap

    def make_array(self, new_cap):
        return (new_cap * ctypes.py_object)()

arr = DynamicArray()

Thử dùng dynamic array:

>>> len(arr)
0
>>> arr.append(1)
>>> len(arr)
1
>>> arr.append('Tutorialspoint')
>>> len(arr)
2
>>> arr[1]
'Tutorialspoint'

Đã tạo thành công dynamic array riêng, có thể resize array (list trong Python).