Tìm kiếm cấu trúc giống như mảng hỗ trợ "thay thế một thành viên" và "nối thêm"

Question

Là bài tập tôi đã viết an implementation của longest increasing subsequence algorithm, ban đầu bằng Python nhưng tôi muốn dịch thành Haskell. Tóm lại, thuật toán liên quan đến một danh sách các số nguyên, trong đó kết quả của mỗi lần lặp là một dãy số nguyên là kết quả của việc thay đổi một phần tử hoặc nối thêm một phần tử vào kết quả trước đó.

Tất nhiên trong Python bạn chỉ có thể thay đổi một phần tử của mảng. Trong Haskell, bạn có thể xây dựng lại mảng trong khi thay thế một phần tử tại mỗi lần lặp - nhưng điều đó có vẻ lãng phí (sao chép hầu hết các mảng tại mỗi lần lặp).

Nói tóm lại những gì tôi đang tìm kiếm là một hiệu quả Haskell cấu trúc dữ liệu đó là một bộ sưu tập lệnh của 'n' đối tượng và hỗ trợ các hoạt động: lookup i, replace i foo, và append foo (nơi i là trong [0..n- 1]). Gợi ý?

Answer 1

Có lẽ loại tiêu chuẩn Seq từ Data.Sequence. Nó không phải khá O (1), nhưng đó là khá tốt:

• index (bạn lookup) và adjust (bạn replace) là O (log (min (index,   dài  -  index)))

• (><) (bạn append) là O (log (min (length1, 0.123.length2)))

Nó dựa trên một cấu trúc cây (đặc biệt, một cây 2-3 ngón tay), vì vậy nó phải có tính chất chia sẻ tốt (nghĩa là nó sẽ không sao chép toàn bộ chuỗi cho sửa đổi gia tăng, và sẽ thực hiện chúng nhanh hơn quá). Lưu ý rằng Seq s rất nghiêm ngặt, không giống như danh sách.

Answer 2

Tôi sẽ cố gắng chỉ sử dụng các mảng có thể thay đổi trong trường hợp này, tốt nhất là trong đơn vị ST.

Ưu điểm chính sẽ làm cho bản dịch trở nên đơn giản hơn và làm cho mọi việc trở nên đơn giản và hiệu quả.

Những bất lợi, tất nhiên, đang mất đi độ tinh khiết và tính tương thích. Tuy nhiên tôi nghĩ rằng đây không phải là một vấn đề lớn vì tôi không nghĩ có nhiều trường hợp bạn muốn giữ các thuật toán trung gian xung quanh.