Tối Ưu Hóa Cấu Trúc Dữ Liệu Tag Set

Trong thư viện ECS vừa được triển khai, cấu trúc Tag đóng vai trò then chốt. Đây là loại Component đặc biệt không chứa dữ liệu nhưng vẫn được liên kết với Entity, chủ yếu dùng cho mục đích lọc chọn. Khi thiết kế cấu trúc dữ liệu Component, tôi chọn phương pháp sử dụng mảng liên tục trong bộ nhớ với Entity ID được sắp xếp theo thứ tự. Thuật toán truy vấn được cải tiến giúp thời gian tìm kiếm đa số trường hợp đạt gần mức hằng số O(1), thấp hơn Log(N).

Tuy nhiên, đổi lại là thao tác chèn/xóa đều có độ phức tạp O(n). Để tránh hiện tượng tích tụ thao tác làm độ phức tạp tăng đến O(n²), tôi áp dụng cơ chế đánh dấu thay vì xóa trực tiếp Component. Các Entity bị xóa sẽ được ghi chú và xử lý hàng loạt vào cuối frame, đảm bảo độ phức tạp duy trì ở mức O(n) cho các thao tác xóa hàng loạt.

Đặc biệt, quá trình đánh dấu liên quan đến việc thao tác Tag - loại Component cần hỗ trợ khả năng kích hoạt/vô hiệu hóa động. Dù không chứa dữ liệu, tôi đã phát triển phương pháp tối ưu giúp trung bình độ phức tạp thấp hơn O(n). Cấu trúc Tag bản chất lưu trữ mảng Entity ID có thứ tự. Ví dụ khi 5 Entity 1,3,5,7,9 được đánh dấu, sẽ có mảng {1,3,5,7,9} độ dài 5.

Với phương pháp truyền thống, khi vô hiệu hóa Entity 5 cần xóa phần tử này và dời dữ liệu phía sau, tạo ra mảng {1,3,7,9} với độ phức tạp O(n) - tìm kiếm Log(n) lần so sánh và trung bình di chuyển n/2 phần tử. Tôi đề xuất kỹ thuật tối ưu: thay vì dịch chuyển dữ liệu, ta sao chép giá trị kề gần nhất. Mảng sẽ trở thành {1,3,3,7,9} hoặc {1,3,7,7,9} tùy chọn.

Biến thể này rút ngắn độ phức tạp xuống O(logN) cho thao tác xóa, đồng thời không ảnh hưởng nhiều đến quá trình duyệt mảng. Trong quá trình duyệt, có thể tích hợp luôn thao tác thanh lọc các Entity ID trùng lặp. Hơn nữa, sau nhiều lần xóa khiến mảng xuất hiện giá trị trùng, khi cần kích hoạt Entity mới, số lượng dữ liệu cần dịch chuyển trong thao tác chèn cũng giảm đáng kể.

Điểm sáng của giải pháp nằm ở việc tận dụng đặc tính riêng của cấu trúc Tag - chỉ cần xác định sự tồn tại và liệt kê Entity ID. Điều này cho phép chấp nhận tạm thời các giá trị trùng lặp để đổi lấy hiệu suất tối ưu trong các thao tác sửa đổi thường xuyên.