Hàng đợi không thể thay đổi trong Clojure

Question

Cách tốt nhất để có được loại dữ liệu hàng đợi đơn giản, hiệu quả trong Clojure là gì?

Chỉ cần hai thao tác, enqueue và dequeue với ngữ nghĩa thông thường.

Tôi coi danh sách và vectơ tất nhiên, nhưng tôi hiểu rằng chúng có hiệu suất tương đối kém (tức là O (n) hoặc tệ hơn) để sửa đổi ở cuối và đầu tương ứng - vì vậy không lý tưởng cho hàng đợi!

Lý tưởng nhất là tôi muốn có cấu trúc dữ liệu liên tục thích hợp với O (log n) cho cả hoạt động enqueue và dequeue.

Answer 1

Sự cố được giải quyết - giải pháp cho những người khác có thể thấy hữu ích.

Tôi đã tìm thấy Clojure có lớp clojure.lang.PersistentQueue thực hiện những gì cần thiết.

Bạn có thể tạo một thể hiện như thế này:

(def x (atom clojure.lang.PersistentQueue/EMPTY)) 

Theo như tôi thấy, bạn đang cần phải sử dụng Java interop để tạo ra các ví dụ nhưng như Michal helpfully chỉ ra bạn có thể sử dụng cái nhìn, pop và sau đó.

Answer 2

Tôi sử dụng chức năng sau queue để tạo PersistentQueue. Tùy chọn, bạn có thể muốn có phương thức in và trình đọc dữ liệu nếu bạn đang in và đọc hàng đợi.

Các chức năng Clojure thông thường đã được triển khai cho PersistentQueue.

• cái nhìn - nhận người đứng đầu
• pop - trả về một PersistentQueue mới mà không có sự đầu
• conj - thêm mục vào đuôi
• trống rỗng? - đúng nếu rỗng
• seq - nội dung như là một chuỗi (danh sách)

    (defn queue 
     ([] clojure.lang.PersistentQueue/EMPTY) 
     ([coll] (reduce conj clojure.lang.PersistentQueue/EMPTY coll))) 

    (defmethod print-method clojure.lang.PersistentQueue 
     [q ^java.io.Writer w] 
     (.write w "#queue ") 
     (print-method (sequence q) w)) 

    (comment 
     (let [*data-readers* {'queue #'queue}] 
     (read-string (pr-str (queue [1 2 3]))))) 

Answer 3

Clojure thực sự có thể được hưởng lợi từ một hàng đợi theo nghĩa đen. Điều này sẽ sạch hơn (và di động hơn) hơn là dựa vào Java interop.

Tuy nhiên, không khó để cuộn hàng đợi liên tục di động của riêng bạn, chỉ cần sử dụng các đồ gia dụng thông thường như danh sách.

Xem xét hàng đợi dưới dạng hai danh sách, một danh sách cung cấp phần đầu của hàng đợi và phần còn lại của đuôi. enqueue thêm vào danh sách đầu tiên, dequeue bật từ sau. Hầu hết các chức năng ISeq được thực hiện một cách trivially.

Có lẽ phần khó khăn duy nhất là điều gì xảy ra khi đuôi trống và bạn muốn dequeue. Trong trường hợp đó danh sách đầu là reverse d và trở thành đuôi mới và danh sách trống sẽ trở thành danh sách đầu mới. Tôi tin rằng, ngay cả với chi phí của reverse, rằng enqueue và dequeue vẫn là O(1), mặc dù số k sẽ cao hơn vectơ vani.

Chúc mừng queue ing!