O（1）またはO（log n）の任意の要素を削除できるデータ構造はClojureにありますか？

Question

コードでは、任意の大きなコレクションのO（1）またはO（log n）になるremove-nthとsome-collを探しています。

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

代替はまた、O（スライスを介して）（ログn）の分割及び連結を提供し（元の紙here有する）RRB-tree based vectors あります。さらに、Clojureの既存のベクターの上でこれをほぼ透過的に行うことができます。