私のClojure関数は、リストやベクトルで非常に遅くなる可能性がありますか？

Question

私はClojureのを学んだし、私はちょうどこの機能を書いた：

(defn replace-last [coll value] 
    (assoc coll (dec (count coll)) value)) 

私はそれがリストおよび/またはベクターのいずれかのために非常に遅くなる可能性が高いだとちょっと心配です - 私は理解していませんまだ十分知っていない。

ありがとうございます！

Answer 1

ベクターの場合、これはかなり高速です。ベクターの約束の1つは、わずかに変更されたコピーの高速作成です。

リストの場合、これはまったく機能しません。これらは結合（clojure.lang.Associative）ではないため、assocの有効な引数ではありません。他の可能なアプローチとしては、実際のリストを戻す必要がある場合（seq（可）とは対照的に）、あなたは不運です。リストの最後の要素のアクセス/置換は、基本的に線形の時間操作です。一方、最後の要素を除いてあなたのリストのように見える怠惰なseqであれば、butlastの半遅延型を実装することができます（clojure.coreのものはまったく怠惰ではありません）。

(defn semi-lazy-butlast [s] 
    (cond (empty? s) s 
     (empty? (next s)) nil ; or perhaps() 
     :else (lazy-seq (cons (first s) 
           (semi-lazy-butlast (next s)))))) 

(defn replace-last [s x] 
    (if (empty? s) ; do nothing if there is no last element to replace 
    s 
    (lazy-cat (semi-lazy-butlast s) [x]))) 

これは、あなたが実際にあなたの配列を消費してそれに近い得るまで最後の要素を交換延期：lazy-catとすることを使用します。

サンプルの相互作用：

user=> (take 10 (replace-last (range) :foo)) 
(0 1 2 3 4 5 6 7 8 9) 
user=> (take 10 (replace-last (range 10) :foo)) 
(0 1 2 3 4 5 6 7 8 :foo) 
user=> (replace-last() :foo) 
() 

Answer 2

これはベクトルと同じくらい速く、リストにはまったく機能しません。