Bodigrim/chimera

🚀 Chimera: Memoization O(1) trên luồng vô hạn bằng Haskell

Kết hợp sức mạnh của mảng phẳng và cây nhị phân lười biếm để tối ưu memoization với truy cập ngẫu nhiên nhanh.

Chimera là một thư viện Haskell thiết kế để giải quyết bài toán memoization hiệu quả cho các hàm f :: Word -> a tốn chi phí tính toán. Thay vì chọn giữa mảng phẳng (nhanh nhưng cần cấp phát trước kích thước) hay cây nhị phân lười biếm (linh hoạt nhưng chậm do truy cập logarithmic và không thân thiện bộ nhớ cache), Chimera giới thiệu kiểu dữ liệu Chimera — luồng vô hạn lười biếm nhưng hỗ trợ chỉ số O(1) thân thiện bộ nhớ cache.

✨ Điểm nổi bật

• Luồng vô hạn lười biếm: Hỗ trợ toàn bộ miền giá trị đầu vào mà không cần cấp phát trước kích thước.
• Chỉ số O(1) thân thiện cache: Truy cập phần tử bằng chỉ số nguyên trong thời gian hằng số nhờ cấu trúc mảng lồng nhau theo mẫu nhân đôi.
• Memoization hàm đệ quy: Hỗ trợ memoize cả hàm đệ quy thông qua memoizeFix, truyền bộ nhớ cache vào các lời gọi đệ quy nội tại.
• Hỗ trợ đa đối số: Memoize hàm có nhiều đối số, bao gồm cả số nguyên có dấu.
• Tối ưu cho predicated logic: Hiệu suất cao khi memoize các hàm trả về Bool.
• Tích hợp với các gói khác: Chuyển đổi kiểu dữ liệu tùy chỉnh bằng cantor-pairing hoặc Data.Chimera.ContinuousMapping.

💡 Vì sao đáng chú ý

Chimera khác biệt nhờ kết hợp hai cách tiếp cận truyền thống: mảng phẳng cho tốc độ và cây nhị phân lười biếm cho linh hoạt. Cụ nghĩa, nó sử dụng một vector bao ngoài (boxed) chứa nhiều vector trong (có thể unboxed) có kích thước tăng dần theo cấp số nhân (1, 1, 2, 4, ..., 2⁶³). Nhờ mẫu tăng kích thước này, việc xác định vector chứa phần tử cần tìm chỉ mất O(1) thông qua hướng dẫn ffs (Find First Set). Kết quả là Chimera nhanh hơn 20 lần so với thư viện memoize truyền thống trong benchmark Collatz sequence, đặc biệt hiệu quả cho các bài toán đệ quy dày đặc như kiểm tra số nguyên tố hay dãy Fibonacci.

---

#Haskell #Memoization #LazyStreams #DynamicProgramming #TiniX