差分リストを作ることを試してみた。

全部実装していないけど。ベンチマークに必要な分だけ実装。

差分リストについて

差分リストはリストのようなもの。appendがO(1)でできるのがlistとの違い

データ構造	cons	snoc	append	listから変換	listに変換
リスト	O(1)	O(N)	O(N)	-	-
差分リスト	O(1)	O(1)	O(1)	O(N)	O(N)

ただし、リストに変換する時にはO(N)のコスト

snocはconsの逆

(snoc '(1 2) 3) => '(1 2 3)

impl

;; definition
(define (DL undl)
  (lambda () undl))

(define (list->dl xs)
  (fold-right dlcons (dlempty) xs))

(define (dl->list dl)
  ((dl) '()))

(define (dlempty) (DL identity))

(define (dlcons x xs)
  (DL (compose (cut cons x <>) (xs))))

(define (dlsnoc xs x)
  (DL (compose (xs) (cut cons x <>))))

(define (dlappend xs ys)
  (DL (compose (xs) (ys))))

;; how to use
(dl->list (dlempty)) ; => ()
(dl->list (dlcons 1 (dlempty))) ; => (1)
(dl->list (dlcons 2 (dlcons 1 (dlempty)))) ; => (2 1)
(define xs (dlcons 2 (dlcons 1 (dlempty))))
(define ys (dlcons 'a (dlcons 'b (dlempty))))
(dl->list (dlappend xs ys)) ; => (2 1 a b)
(dl->list (dlsnoc xs 3)) ; => (2 1 3)

benchmark

ちなみにgaucheのversionは0.9.1

gosh -V
Gauche scheme shell, version 0.9.1 [utf-8,pthreads], x86_64-pc-linux-gnu

;; bench
(use srfi-1) ;iota

;; list
(let1 xs (iota 10000)
  (time
   (dotimes (i 1000)
     (append xs xs)))
  (equal? (append xs xs) (append xs xs)))

;; difference list
(let* ((xs (iota 10000))
       (xs* (list->dl xs)))
  (time 
   (dotimes (i 1000)
     (dlappend xs* xs*)))
   (equal? (append xs xs) (dl->list (dlappend xs* xs*))))

appendは早い。

gosh> ;(time (dotimes (i 1000) (append xs xs)))
; real   0.307
; user   0.300
; sys    0.000
;(time (dotimes (i 1000) (dlappend xs* xs*)))
; real   0.001
; user   0.000
; sys    0.000
#t

ただ、変換する部分の処理で時間はかかる。

(time (begin (iota 100000) #t))
(time (begin (list->dl (iota 100000)) #t))

;(time (begin (iota 100000) #t))
; real   0.014
; user   0.010
; sys    0.000
;(time (begin (list->dl (iota 100000)) #t))
; real   0.197
; user   0.160
; sys    0.030
#t

!

関数をたくさん作るのでメモリ消費がすごいです。(1000万個の要素を作った時にメモリが枯渇しました)