Haskell: Datastruture với O (1) nối thêm và O (1) lập chỉ mục?

Question

Tôi đang tìm cấu trúc dữ liệu trong Haskell hỗ trợ cả lập chỉ mục nhanh và nối nhanh. Đây là một vấn đề ghi nhớ phát sinh từ đệ quy.

Từ cách vectơ hoạt động trong C++ (có thể thay đổi, nhưng điều đó không quan trọng trong trường hợp này) có vẻ như vectơ bất biến với cả (được phân bổ) O (1) nối thêm và O (1) lập chỉ mục có thể thực hiện được (ok, không, hãy xem bình luận cho câu hỏi này). Đây có phải là poossible trong Haskell hay tôi nên đi với Data.Sequence trong đó có (AFAICT anyway) O (1) nối thêm và O (log (min (i, n-i))) lập chỉ mục?

Trên ghi chú có liên quan, với tư cách là một newbie Haskell, tôi thấy mình khao khát một hướng dẫn thực tế, ngắn gọn về cấu trúc dữ liệu Haskell. Lý tưởng nhất điều này sẽ cung cấp một cái nhìn tổng quan khá toàn diện về các cấu trúc dữ liệu thực tế nhất cùng với các đặc tính hiệu năng và các con trỏ tới các thư viện Haskell nơi chúng được thực hiện. Có vẻ như có rất nhiều thông tin trên mạng, nhưng tôi thấy nó có một chút phân tán. Tôi có hỏi quá nhiều không?

Answer 1

Nếu bộ nhớ phân phối, các vectơ C++ được triển khai dưới dạng một mảng có thông tin giới hạn và kích thước. Khi chèn sẽ làm tăng giới hạn vượt quá kích thước, kích thước được tăng gấp đôi. Điều này được khấu hao theo thời gian O (1) (không phải O (1) như bạn yêu cầu), và có thể được mô phỏng tốt trong Haskell bằng cách sử dụng loại Array, có lẽ với IO hoặc ST được thêm vào trước.

Answer 2

Hãy xem this để đưa ra lựa chọn sáng suốt hơn về những gì bạn nên sử dụng.

Nhưng điều đơn giản là, nếu bạn muốn tương đương với vectơ C++, hãy sử dụng Data.Vector.

Answer 3

Đối với các vấn đề ghi nhớ đơn giản, bạn thường muốn xây dựng bảng một lần và sau đó không sửa đổi nó sau này. Trong trường hợp đó, bạn có thể tránh phải lo lắng về việc phụ thêm, thay vào đó, hãy nghĩ đến việc xây dựng bảng ghi nhớ là một thao tác.

Một phương pháp là tận dụng lợi thế của việc đánh giá lười biếng và tham khảo bảng trong khi chúng tôi đang xây dựng nó.

import Data.Array 
fibs = listArray (0, n-1) $ 0 : 1 : [fibs!(i-1) + fibs!(i-2) | i <- [2..n-1]] 
    where n = 100 

Phương pháp này đặc biệt hữu ích khi phụ thuộc đơn giản để đánh giá chúng trước thời hạn. Tuy nhiên, nó đòi hỏi phải sử dụng các mảng hoặc vectơ đóng hộp, điều này có thể làm cho phương pháp này không phù hợp với các bảng lớn do phụ phí.

Đối với vectơ không có hộp, bạn có các thao tác như constructN cho phép bạn tạo bảng một cách thuần túy trong khi sử dụng đột biến bên dưới để làm cho nó hiệu quả. Nó thực hiện điều này bằng cách đưa ra hàm bạn truyền qua một cái nhìn bất biến của tiền tố của vectơ được xây dựng cho đến nay, mà sau đó bạn có thể sử dụng để tính toán phần tử tiếp theo.

import Data.Vector.Unboxed as V 
fibs = constructN 100 f 
    where f xs | i < 2 = i 
      | otherwise = xs!(i-1) + xs!(i-2) 
      where i = V.length xs