Clojure中是否有任何數據結構允許刪除O（1）或O（log n）中的任意元素？

Question

在代碼中，我正在尋找remove-nth和some-coll，對於任意大的集合，這將是O（1）或O（log n）。

(= 
    (remove-nth (some-coll "a" "b" "c" "d") 2) 
    (some-coll "a" "b" "d")) 

我最好找只使用標準庫的解決方案，但我很感興趣的是使用外部庫解決方案。

Answer 1

沒有在標準庫中，但finger trees（介紹它們的原始文件是here）完成了工作（並且通常是非常棒的功能數據結構）。您可以通過O（log n）拆分和O（log n）拼接獲得O（log n）刪除。

(defn remove-nth [xs n] 
    (let [[left _ right] (ft-split-at xs n)] 
    (ft-concat left right))) 

(def cdl (apply counted-double-list '[a b c d e f])) 

(remove-nth cdl 3) 
;; => (a b c e f) 

一種替代方案是RRB-tree based vectors（與原始紙here） ，其也提供O（log n）的分割（通過切片）和級聯。另外，你可以在Clojure的預先存在的載體上幾乎透明地做到這一點。