#:g1: cl-skip-listの紹介

Posted 2014-05-24 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の145日目です。

cl-skip-listとはなにか

 cl-skip-listは、Kevin Thomas Raison氏作のCommon Lisp用スキップリストのライブラリです。

パッケージ情報

パッケージ名cl-skip-list
Quicklisp
CLiKihttp://cliki.net/cl-skip-list
Quickdocshttp://quickdocs.org/cl-skip-list

インストール方法

(ql:quickload :cl-skip-list)

試してみる

 どんな関数があるかは、Quickdocsで確認できます〈多分〉

 大半の操作について平均O(log n)のリストということなので、いつものように普通のリストとランダムアクセス性能を比べてみます。

(defun shuffle-list (list &aux (len (length list)))
  (mapl (lambda (u)
          (rotatef (first u) (nth (random len) list)))
        list)
  list)

(defun sl-iota (count &optional (start 0) (step 1)) (declare (fixnum count) (number start step) (optimize (debug 1))) (let ((sl (cl-skip-list:make-skip-list))) (loop :for i :from start :by step :repeat count :do (skip-list-add sl i i)) sl))

(defun sl-shuffle-list (sl) (let ((len (skip-list-length sl)) (ans sl)) (dotimes (idx len ans) (let* ((rand (random len)) (elt1 (skip-list-lookup sl idx)) (elt2 (skip-list-lookup sl rand))) (skip-list-replace-kv sl idx elt2) (skip-list-replace-kv sl rand elt1))) ans))

(let ((sl (sl-shuffle-list (sl-iota 100)))) (loop :with cur := (skip-list-values-cursor sl) :for v := (sl-cursor-next cur) :while v :collect v)) ;=> (94 89 9 20 41 32 61 95 18 64 68 97 21 1 4 28 60 37 91 30 44 84 2 45 13 10 51 ; 83 65 85 11 40 92 90 12 22 50 66 96 78 86 74 63 71 19 88 31 16 0 49 25 55 15 ; 99 87 79 81 70 77 76 82 8 38 72 98 67 17 39 34 26 14 54 7 27 43 24 80 36 75 73 ; 3 29 62 6 58 5 56 53 23 52 35 42 47 59 48 69 33 46 57 93)

こんな感じのものを定義して計測します。

計測/比較

(defvar *list* (*:iota 100000))

(progn (shuffle-list *list*) nil) ;=> NIL #|------------------------------------------------------------| Evaluation took: 11.173 seconds of real time 11.364000 seconds of total run time (11.364000 user, 0.000000 system) 101.71% CPU 36,785,033,479 processor cycles 219,712 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

(defvar *sl-list* (sl-iota 100000))

(progn (sl-shuffle-list *sl-list*) nil) ;=> NIL #|------------------------------------------------------------| Evaluation took: 0.858 seconds of real time 0.816000 seconds of total run time (0.816000 user, 0.000000 system) 95.10% CPU 2,824,862,635 processor cycles 217,578,528 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz |------------------------------------------------------------|#

通常のリストよりは大分速いことが分かります。

まとめ

 今回は、cl-skip-listを紹介してみました。
データ構造の紹介は、適切な例を探すのが面倒です。

comments powered by Disqus