#:g1: random-access-listsの紹介

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

(LISP Library 365参加エントリ)

 LISP Library 365 の133日目です。

random-access-listsとはなにか

 random-access-listsは、SRFI 101: Purely Functional Random-Access Pairs and Lists の参照実装のVincent Toups氏によるCommon Lispへの移植です。

パッケージ情報

パッケージ名random-access-lists
Quicklisp
プロジェクトサイトVincentToups/random-access-lists · GitHub
Quickdocshttp://quickdocs.org/random-access-lists

インストール方法

(ql:quickload :random-access-lists)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。

 READMEにも書いてありますが、参照実装ほぼそのままとのこと。
ランダムアクセス可能ということで、リスト構造には向いていないシャッフルをして、通常のリストと比較してみます。

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

(defun ra-iota (count &optional (start 0) (step 1)) (declare (fixnum count) (number start step) (optimize (debug 1))) (if (< count 0) (error "Negative step count ~S ~S" 'iota count)) (*:let *loop ((n 0) (r '())) (if (= n count) (random-access-lists:ra-reverse r) (*loop (the fixnum (+ 1 n)) (random-access-lists:ra-cons (+ start (* n step)) r)))))

(defun ra-shuffle-list (rlist) (let ((len (random-access-lists:ra-length rlist)) (ans rlist)) (dotimes (idx len ans) (let* ((rand (random len)) (elt1 (random-access-lists:ra-list-ref ans idx)) (elt2 (random-access-lists:ra-list-ref ans rand))) (setq ans (random-access-lists:ra-list-set (random-access-lists:ra-list-set ans rand elt1) idx elt2)))) ans))

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

(progn (shuffle-list *list*) nil) ;=> NIL #|------------------------------------------------------------| Evaluation took: 28.361 seconds of real time 28.361773 seconds of total run time (28.353772 user, 0.008001 system) 100.00% CPU 67,896,428,292 processor cycles 616,080 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

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

(progn (ra-shuffle-list *ra-list*) nil) ;=> NIL #|------------------------------------------------------------| Evaluation took: 0.847 seconds of real time 0.844053 seconds of total run time (0.836052 user, 0.008001 system) [ Run times consist of 0.056 seconds GC time, and 0.789 seconds non-GC time. ] 99.65% CPU 2,028,218,283 processor cycles 214,637,872 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

メモリは多く消費しますが、速度は圧倒的に速いですね。

関連

まとめ

 今回は、random-access-listsを紹介してみました。
ランダムな場所に要素を追加したり、アクセスしたりする場合に活躍するのかもしれないですね。

comments powered by Disqus