"Danh sách" với hiệu quả chèn/xóa

Question

Tôi đang tìm kiếm một "Danh sách" với log (N) chèn/xóa tại chỉ số i. Tôi đặt từ "Danh sách" trong dấu ngoặc kép, bởi vì tôi không có nghĩa nó là một danh sách Haskell thực sự, nhưng chỉ bất kỳ thùng chứa có thứ tự với một loạt các đối tượng (trên thực tế, nó có thể cần một số loại cây trong nội bộ). Tôi ngạc nhiên rằng tôi chưa tìm được giải pháp tuyệt vời nào ....

Đây là giải pháp tốt nhất mà tôi có cho đến nay- Sử dụng Data.Sequence với hai hàm này.

doInsert position value seq = before >< (value <| after) 
    where 
    (before, after) = splitAt position seq 

doDelete position seq = before >< (drop 1 after) 
    where 
    (before, after) = splitAt position seq 

Trong khi đây là những kỹ thuật tất cả các log (N) chức năng, nó cảm thấy như tôi đang làm một loạt các công cụ bổ sung cho mỗi chèn/xóa .... Nói cách khác, điều này quy mô như K * log (N) cho một K lớn hơn mức cần thiết. Hơn nữa, vì tôi phải tự xác định thứ này, tôi cảm thấy mình đang dùng Sequence cho thứ gì đó mà nó không được thiết kế cho.

Có cách nào tốt hơn không?

Đây là một câu hỏi liên quan (mặc dù nó chỉ thoả thuận với Trình tự, tôi sẽ rất vui nếu sử dụng bất cứ điều gì khác): Why doesn't Data.Sequence have `insert' or `insertBy', and how do I efficiently implement them?

Và vâng, câu hỏi này có liên quan đến cái này khác tôi đăng tải cách đây vài ngày: Massive number of XML edits

Answer 1

Nếu bạn làm việc cẩn thận với Danh sách Haskell được xác định trước, sẽ không có vấn đề gì với chúng. (Ví dụ: khi ghép hai danh sách).

Nếu bạn muốn tìm cách triển khai danh sách, với việc chèn và xóa hiệu quả, một cây nhị phân AVLTree hoặc bất kỳ loại cây nhị phân cân bằng nào sẽ hoạt động. Ví dụ lưu trữ trong một AVLTree một tuple (Int, a) trong đó Int là chỉ mục của danh sách và một elem. Vì vậy, về độ phức tạp trung bình, các hoạt động sẽ là logarit để chèn và xóa.

Tôi hy vọng điều này sẽ trả lời câu hỏi của bạn.

Answer 2

Có các cấu trúc như seqs có thể thay đổi, hàng đợi có thể thay đổi, v.v. có thể cung cấp cho bạn O (1) tham gia. Tuy nhiên, tất cả các cấu trúc như vậy tôi biết để có được đi với điều này bằng cách cho bạn O (i) tách. Nếu bạn muốn chia nhỏ và tham gia cả hai để được tối ưu nhất có thể, tôi nghĩ rằng một ngón tay (aka Sequence) là đặt cược tốt nhất của bạn. Toàn bộ các điểm của con đường Sequence được cấu trúc là để đảm bảo rằng chia tách, tham gia, vv có một số lượng không khủng khiếp của juggling để làm khi chia tách và tham gia, trong số những thứ khác.

Nếu bạn thể nhận được ngay với một IntMap mà bắt đầu thưa thớt và có dày đặc hơn, và thỉnh thoảng "xây dựng lại" khi mọi việc trở nên quá dày đặc, sau đó thể cung cấp cho bạn hiệu suất tốt hơn - nhưng điều đó thực sự phụ thuộc vào bạn mô hình sử dụng.