Mảng Thưa Trong Lua

Trong Lua, kiểu dữ liệu bảng (table) có thể được sử dụng như một mảng, tuy nhiên điều kiện tiên quyết là mảng này không được chứa “lỗ hổng” (các giá trị nil). Nếu tồn tại giá trị nil trong mảng, hành vi của toán tử lấy độ dài (#) và vòng lặp sẽ trở nên không xác định.

Liệu có cách nào để triển khai một cấu trúc mảng hỗ trợ “lỗ hổng” trong Lua với chi phí tính toán tối thiểu?

Đặc tả hành vi của mảng thưa

Đầu tiên, chúng ta cần xác định rõ hành vi mong muốn của mảng thưa:

1. Chỉ cho phép dùng khóa số nguyên dương: Bất kỳ cố gắng thiết lập khóa không phải số nguyên dương nào sẽ ném ra lỗi (error).
2. Hỗ trợ vòng lặp pairs thông minh:
   • Vòng lặp pairs phải bỏ qua các phần tử có giá trị nil.
   • Đảm bảo thứ tự lặp từ khóa nhỏ nhất đến lớn nhất.
3. Toán tử lấy độ dài (#) chính xác: Trả về khóa số nguyên dương lớn nhất hiện có trong mảng.
4. Giữ nguyên hành vi của ipairs: Vòng lặp ipairs vẫn dừng lại khi gặp giá trị nil đầu tiên (giống mảng tiêu chuẩn).

Giải pháp kỹ thuật

Chúng ta có thể tận dụng bảng Lua thông thường làm nền tảng, đồng thời tùy chỉnh ba phương thức meta sau:

• __newindex: Kiểm soát việc gán giá trị.
• __pairs: Định nghĩa lại logic lặp.
• __len: Tính toán độ dài động.

Cơ chế hoạt động

• Phần tử trong phạm vi mảng (array part):
  Khi khóa nằm trong khoảng 1..lua_rawlen(t), giá trị sẽ được lưu trực tiếp vào phần array của bảng để tối ưu hiệu suất.

• Phần tử ngoài phạm vi mảng (hash part):
  Các khóa vượt quá kích thước hiện tại sẽ được lưu vào phần hash với khóa âm (ví dụ: -key) để phân biệt.

• Cân bằng và sắp xếp định kỳ:
  Trước mỗi lần gọi pairs hoặc #, hệ thống sẽ:

  1. Trích xuất các khóa âm từ hash part.
  2. Chuyển đổi thành khóa dương tương ứng.
  3. Sắp xếp và loại bỏ trùng lặp.
  4. Gộp vào array part nếu có thể.
     Quá trình này giúp đảm bảo độ phức tạp thuật toán ở mức O(log n) cho các thao tác sau đó.

Ưu điểm của giải pháp

• Tối ưu bộ nhớ: Chỉ lưu trữ các phần tử thực sự tồn tại.
• Tương thích ngược: Duy trì tính tương thích với các hàm tiêu chuẩn như ipairs, pairs.
• Mở rộng linh hoạt: Dễ dàng tích hợp thêm các phương thức như insert, remove, resize.

Bạn có thể tham khảo mã nguồn triển khai chi tiết tại github.com/example/sparse-array.

Lưu ý: Việc sắp xếp định kỳ có thể gây ra chi phí ẩn khi xử lý dữ liệu lớn. Trong các ứng dụng thời gian thực, hãy cân nhắc kết hợp với cơ chế “lười biếng” (lazy evaluation) để trì hoãn xử lý đến khi thực sự cần thiết.