Lispy Days

趣味で Lisp な日々 (index) (weblog) (view) (edit) (help)

検索には search 関数を使っているわけですが,ふと性能が気になったのでテスト.

;; CMUCL post-18e (19a?)
CL-USER> (time (search "abc" x))

; Evaluation took:
;   3.64 seconds of real time
;   3.167927 seconds of user run time
;   0.0 seconds of system run time
;   3,674,156,913 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; CLISP 2.32
[3]> (progn (setf x (make-string (* 10 1024 1024) :initial-element #\Space)) nil)
[4]> (time (search "abc" x))

Real time: 0.604639 sec.
Run time: 0.598959 sec.
Space: 0 Bytes

CMUCL のほうが遅い.CLISP 比 5 倍くらいと悲惨なのでとりあえず単純な探索アルゴリズムを実装してみる.

(defun search-str (pattern str)
  (declare (simple-string pattern str)
       (optimize (speed 3) (space 0) (safety 0)))
  (loop with len of-type fixnum  = (length pattern)
    with last of-type fixnum = (length str)
    for p1 of-type fixnum from 0 below (- last len) do
    (loop for p2 of-type fixnum from 0 to len
          when (= p2 len) do (return-from search-str p1)
          while (char-equal (schar pattern p2) (schar str (+ p1 p2))))))

これをコンパイルして同じ文字列を探索させると

CL-USER> (time (search-str "abc" x))

; Evaluation took:
;   0.3 seconds of real time
;   0.284611 seconds of user run time
;   0.005258 seconds of system run time
;   302,351,489 CPU cycles
;   0 page faults and
;   0 bytes consed.

おー.さすがにネイティブコードコンパイラだけある!! で CLISP のほうは

;; CLISP 2.32
[6]> (time (search-str "abc" x))

Real time: 14.196836 sec.
Run time: 14.049627 sec.
Space: 0 Bytes

…ということで CLISP では組み込みの search, CMUCL では自前の文字列検索ルーチンを使う事にする.