Tôi cần một cấu trúc dữ liệu giống như mảng với bản cập nhật chức năng nhanh nhất có thể. Tôi đã thấy một vài triển khai khác nhau của mảng linh hoạt cung cấp cho tôi thuộc tính này (Braun, Danh sách truy cập ngẫu nhiên) nhưng tôi tự hỏi liệu có triển khai nào được tối ưu hóa cụ thể cho trường hợp chúng tôi không quan tâm đến việc thêm hoặc thêm vào - chỉ cập nhật.Triển khai hiệu quả nhất các mảng với các cập nhật chức năng là gì?
Điền vào Jean-Cristophe có a very nice implementation mảng liên tục, được mô tả trong the paper được liên kết tại cùng một trang (liên tục tìm liên tục, trong đó mảng liên tục là thành phần cốt lõi). Mã này có sẵn trực tiếp there.
Ý tưởng là "phiên bản cuối cùng" của mảng được biểu diễn dưới dạng một mảng thông thường, với O(1) truy cập và hoạt động cập nhật, và các phiên bản trước đó được biểu diễn dưới dạng phiên bản mới nhất này, cộng với một danh sách các sự khác biệt. Nếu bạn cố gắng truy cập vào phiên bản trước của cấu trúc, mảng được "khởi động lại" để áp dụng danh sách các khác biệt và trình bày cho bạn một lần nữa biểu diễn hiệu quả. Tất nhiên điều này sẽ không phải là O (1) trong tất cả các quy trình công việc (nếu bạn liên tục truy cập và sửa đổi các phiên bản không liên quan của cấu trúc, bạn sẽ trả chi phí thường xuyên), nhưng đối với luồng công việc chung chủ yếu là làm việc với một phiên bản, và đôi khi backtracking đến một phiên bản cũ mà trở thành "phiên bản cuối cùng" một lần nữa và nhận được các bản cập nhật, điều này là rất hiệu quả. Một cách sử dụng rất dễ bị ẩn giấu dưới một giao diện thuần túy quan sát.
Bạn đang sử dụng ngôn ngữ nào? Trong Haskell bạn có thể sử dụng mutable arrays với trạng thái đơn nguyên, và trong Mercury bạn có thể sử dụng các mảng có thể thay đổi bằng cách luồng trạng thái IO. Ocaml cũng có một mô-đun mảng, mà không may không duy trì tính minh bạch tham chiếu, nếu đó là những gì bạn đang sau.
Tôi đang sử dụng OCaml. Tôi đã gắn thẻ câu hỏi là Haskell để khai thác kiến thức của cộng đồng về những điều này. Btw, tôi không chắc chắn làm thế nào STArray sẽ giải quyết vấn đề của tôi bằng cách sử dụng cập nhật một mảng trong khi vẫn giữ bản sao cũ có hiệu quả. – rgrinberg
Các mảng OCaml có thể thay đổi được, chúng không có tính bền bỉ. Truy cập liên tục thời gian với các cập nhật và kiên trì có vẻ khá khó khăn nếu không phải là không thể. Vì vậy, một bản đồ có lẽ là những gì bạn muốn (như đề xuất ở trên). –
Có nhiều triển khai dựa trên bản đồ khác nhau, tôi đang tìm kiếm tốt nhất cho trường hợp sử dụng của tôi. Ví dụ như một BST cân bằng sẽ là khủng khiếp cho ứng dụng này. Mặc dù hiệu suất tiệm cận là như nhau. – rgrinberg
Tôi cũng cần các mảng chức năng và cảm nhận về câu hỏi SO này vài ngày trước. Tôi không hài lòng với giải pháp được Gasche đề xuất khi tạo mảng mới là một hoạt động tốn kém và tôi cần truy cập các phiên bản cũ của mảng khá thường xuyên (tôi dự định sử dụng điều này để triển khai AI alpha/beta trên một mảng).
(Khi tôi nói tốn kém, tôi đoán đó là O (n * h) trong đó h là kích thước lịch sử vì trong trường hợp xấu nhất chỉ có một ô được cập nhật nhiều lần và cần phải trải qua toàn bộ danh sách cập nhật cho mỗi Tôi cũng mong đợi hầu hết các tế bào không được cập nhật khi tôi cần phải định tuyến lại mảng).
Đây là lý do tại sao tôi đề xuất một cách tiếp cận khác, có lẽ tôi có thể nhận được một số phản hồi tại đây. Ý tưởng của tôi là để lưu trữ các mảng như trong một B-Tree, ngoại trừ rằng nó không phải là mutable, tôi có thể truy cập và cập nhật bất kỳ giá trị của chỉ số khá dễ dàng.
Tôi đã viết một phần giới thiệu nhỏ về kho lưu trữ của dự án: https://github.com/shepard8/ocaml-ptarray. Thứ tự được chọn để thậm chí độ sâu và trật tự của cây, vì vậy tôi có thể nhận được sự phức tạp tốt đẹp tùy thuộc vào thứ tự cho các hoạt động get/set, cụ thể là O (k^2).
Với k = 10 tôi có thể lưu trữ tối đa 10^10 giá trị. Trên thực tế mảng của tôi không nên chứa nhiều hơn 200 giá trị nhưng điều này là để hiển thị như thế nào mạnh mẽ giải pháp của tôi là dự định được.
Bất kỳ lời khuyên nào được chào đón!
Chắc chắn là một bản đồ thuộc loại nào đó? –
@ DominicBou-Samra là một bản đồ bất biến? nó sẽ không đắt hơn cả mảng? –
Dominic, bản đồ, Braun và RAL đều dựa trên cây. Tôi đang tìm xem liệu có thể kết hợp thông minh với một mảng bắt buộc (không bị đột biến) có thể đánh bại một cấu trúc dữ liệu dựa trên cây thuần túy hay không. – rgrinberg