data-structures - 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 预先存在的向量之上几乎透明地执行此操作。