Clojure中的不可變隊列

在Clojure中獲取簡單，高效的不可變隊列數據類型的最佳方式是什麼？Clojure中的不可變隊列

它只需要兩個操作，入隊和出隊與通常的語義。

我認爲是當然的名單和載體，但據我所知，他們的表現相對較差（即O（N）或更糟）進行修改，在年底分別開始 - 所以不理想的隊列！

理想我想和O（log n）的兩個入隊和出隊操作的適當的持久數據結構。

2010-06-28 mikera

爲了避免人們寫作如何使用缺點列表來實現推送/彈出棧（就像我差不多），不要忘記問題是關於* queues *。 :-) – 2010-06-28 22:05:08

剛剛注意到在最新的1.2快照Clojure Java源代碼中有一個名爲PersistentQueue的類....可能是我自己的問題的答案 – mikera 2010-06-28 22:09:07

它一直在那裏，因爲永遠（剛剛檢查過1.1，但我認爲它比較老比起那個來說）。請注意，默認情況下不提供工廠函數和讀取器語法;使用'clojure.lang.PersistentQueue/EMPTY'來獲得一個空的實例。然後'conj'，'pop'和'peek'就像他們應該用一個隊列一樣工作。見例如我對這個問題的回答：http://stackoverflow.com/questions/2760017用'c.l.PQ'和Java'LinkedBlockingQueue'編寫的代碼。 – 2010-06-28 22:31:11

問題已解決 - 爲其他人提供的解決方案可能會對您有所幫助。

我發現Clojure的有clojure.lang.PersistentQueue的類，它需要什麼。

您可以創建這樣一個實例：據我所看到的，你現在需要互操作使用Java創建實例，但作爲米哈爾有益指出，你可以使用偷看，流行

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

然後連接。

來源

2010-06-28 22:46:23 mikera

PersistentQueue確實是您的最佳選擇。爲了將來的參考，下面是一張總結clojure數據結構的性能特徵/保證的表格：http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html – dvogel 2010-06-29 05:37:27

爲什麼要使用'atom'？ – 2015-09-09 15:21:09

@ raxod502在這種情況下使用原子有什麼問題嗎？ – dgellow 2015-12-05 09:42:10

我用下面的函數queue創建PersistentQueue。或者，如果要打印和讀取隊列，您可能需要使用打印方法和數據讀取器。

通常的Clojure函數已經實現了PersistentQueue。

偷看 - 獲得頭
彈出 - 返回一個新的PersistentQueue無頭
連詞 - 添加項目到尾
空？ - 如果空
序列 - 內容作爲一個序列（列表）


    (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])))))

來源

2015-01-28 19:39:35 miner49r

Clojure中能真正從字面隊列中受益。這將比依靠Java interop更清潔（並且更便於攜帶）。

但是，使用普通家庭項目（如列表）來推出自己的可移植持久隊列並不難。

將隊列看作兩個列表，一個提供隊列的頭部分，另一個提供尾部。 enqueue添加到第一個列表中，dequeue從後者彈出。大多數ISeq函數都可以實現。

大概是唯一棘手的部分是當尾巴是空的，你想dequeue會發生什麼。在這種情況下，頭部列表爲reverse d，併成爲新尾部，空列表成爲新頭部列表。我相信，即使有reverse的開銷，即enqueue和dequeue保持O(1)，雖然k將是當然比一個香草矢量更高。

快樂queue ing！

來源

2016-10-08 00:28:11 CurtainDog

Clojure中的不可變隊列

回答

相關問題