読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

ClojureでのImmutable Data Structureについてメモ

clojure Scheme

ClojureのHashMapとVectorアルゴリズムについて調べていました。

HashMapの方はHAMTというものがベースになっているようです。

Vectorの方ですが、有名なわかりやすい記事があります。

読んでいて気になったことがあります。後ろに1つずつ要素を追加していく事と、前方部分を切り出すことはO(log n)でかなり高速にできるようです。しかし、後ろに別のVectorを繋げる(concat)こと、後方部分を切り出す事(rest)は、繋げる・切り出すVectorの大きさ分O(n)かかるのでは無いか、ということです。

つまり「最初の1個と残り」に分けるのはあまり軽い操作とは言えないのではないか、という疑問があります。(確かめてはいません)

Clojureの内部ではどうしているのか調べたところ、PersistentQueueというものがあるようです。

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentQueue.java

コードのコメントに、Batched Queueというアルゴリズムが使われていると書かれています。Chris OkasakiのPurely Functional Data Structuresに書かれているもののようです。

調べたところ、その本の中からいくつかのデータ構造をClojure書いている人がいました。マクロによって、ML系を知っている人には読みやすくかかれています。

Batched Queueについて

Batched Queueもありました

構造ですが、取り出し用のLinkedList(以下リスト)と追加用のリスト、2つを1つとして扱います。取り出し・追加どちらの操作もそれぞれのリストを対象にします。操作前に取り出しリストが空のときは、追加用リストを逆にしたものを取り出し用リストとし、追加用リストはnilとします。

取り出しと追加がある程度交互に行われる時は、少ない要素数のreverseなのでほぼO(1)といって良いのではないでしょうか。連続した取り出し・追加もO(1)でできます。連続した取り出し・追加を切り替えるときにO(n)を意識する操作が発生しますが、O(n)が問題になる程度にキュー(n)が貯まる時はあまり速度を気にする状況でも無さそうです。

というわけで簡単ながら便利そうなので、Schemeなどでも使っていこうと思います。以下はScheme(gauche)での実装です。

(use util.record)

(define Queue (make-record-type "Queue" '(deq enq)))

(define queue (record-constructor Queue '(deq enq)))

(define deq (record-accessor Queue 'deq))
(define enq (record-accessor Queue 'enq))

(define nil '())
(define (empty-queue) (queue nil nil))


(define (check-queue q)
  (let* ([d (deq q)])
    (if (null? d)
        (queue (reverse (enq q)) nil)
        q)))


(define (head q)
  (let* ([d (deq (check-queue q))])
    (if (null? d)
        (error "empty queue")
        (car d))))


(define (tail q)
  (let* ([q (check-queue q)]
         [d (deq q)])
    (if (null? d)
        (error "empty queue")
        (queue (cdr d) (enq q)))))


(define (snoc q x)
  (let* ([q (check-queue q)]
         [e (cons x (enq q))])
    (queue (deq q) e)))


(print "enq -> deq -> enq -> deq")
(let* ([q (empty-queue)]
       [q (snoc q 1)]
       [_ (print (head q))] ;=> 1
       [q (tail q)]
       [q (snoc q 2)]
       [_ (print (head q))] ;=> 2
       [q (tail q)])
  q)


(print "enq -> enq -> deq -> deq")
(let* ([q (empty-queue)]
       [q (snoc q 1)]
       [q (snoc q 2)]
       [_ (print (head q))] ;=> 1
       [q (tail q)]
       [_ (print (head q))] ;=> 2
       [q (tail q)])
  q)
広告を非表示にする