最適化とは、一般的なものを限定化することにより特定の局面での効率を上げることですが、CLの場合、最適化で調整できるパラメータは最も一般的な設定がデフォルトになっていることが殆どです。

これらの項目を制限したり、特定化することによって最適化します。

リストかベクタか

sequenceには主なところでは、list、vector、stringがあります。リストは要素にアクセスするのに最悪の場合O(n)(nはリストの長さ)のコストがかかりますが、ベクタは、長さによらずO(1)です。

ランダムアクセスや要素をシャッフルするような場合は、劇的にパフォーマンスが違ってきますが、配列を使うべきところにリストを使ってしまうのは、lispプログラマの古典的な問題として知られています。

• 2.2 良いLispプログラミングは難しい

	要素の型指定	サイズの動的な変更	ランダムアクセス	シーケンシャルアクセス	任意の場所への要素の挿入
リスト	不可能(ポインタが指すものの型は指定できない)	可	不向き	可	可
ベクタ	可能	可変長(固定の方が効率は良い)	可	可	不向き

ベクタの最適化(要素の型を指定する)

ベクタの型を指定しての最適化で最適化される点には2つあります。

処理速度の向上(主にアクセサとの連携で)

データ容量の縮小

配列のデータのサイズは、(+ 基本データ領域のサイズ (* 長さ 要素が確保するビット))となります。

ベクタの型の最適化において特定化するポイントは主に下記の通りです

フィルポインタを付けない

伸縮可能にしない

要素の型をできるだけ限定する

stringは、文字を要素とする特化したvectorで、他に要素が0か1に特化したbit-vectorがあります。

デフォルトで用意されている要素の型が限定されたベクタの型には下記のようなものがあります

型	フィルポインタ	伸縮可能	要素の型の限定	displacedか	専用のアクセサ
t(=指定していない)	あっても良い	あっても良い	T(されていない)	そうでも良い	なし(elt)
vector	あっても良い	あっても良い	T(されていない)	そうでも良い	aref
simple-array	なし	なし	T(されていない)	違う	aref
simple-vector	なし	なし	T(されていない)	違う	svref
string	あっても良い	あっても良い	character	そうでも良い	char
simple-string	なし	なし	character	違う	schar
bit-vector	あっても良い	あっても良い	bit	そうでも良い	bit
simple-bit-vector	なし	なし	bit	違う	sbit
なお、simple-vectorのように、fill-pointerなし、固定長、displacedでないベクタでありつつ、要素の型は指定したvectorを作成する場合は、simple-arrayのサブタイプを指定します。

;; (unsigned-byte 8)を要素に持つベクタの型
(simple-array (unsigned-byte 8) (*))

など

型を指定した例

;; 要素数
(defconstant 100_000_000 (expt 10 8))

vectorを指定 (fill-pointerあり、adjustable)

(declaim (vector *big-vector-vector*))
(defvar *big-vector-vector* (make-array 100_000_000
                                        :adjustable T :fill-pointer 100_000_000))

(reduce (lambda (x y) (+ x y)) *big-vector-vector*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
  5.927 seconds of real time
  5.904369 seconds of total run time (5.888368 user, 0.016001 system)
  99.61% CPU
  14,188,101,966 processor cycles
  66,208 bytes consed

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

simple-vectorを指定(make-arrayでパラメータを指定しない場合のデフォルト)

(declaim (simple-vector *big-vector-simple-vector*))
(defvar *big-vector-simple-vector* (make-array 100_000_000))

(reduce (lambda (x y) (+ x y)) *big-vector-simple-vector*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
  4.537 seconds of real time
  4.532283 seconds of total run time (4.516282 user, 0.016001 system)
  99.89% CPU
  10,862,211,222 processor cycles
  100,080 bytes consed

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

要素を(unsigned-byte 8)にしたベクタ (simple-array (unsigned-byte 8) (*))

(declaim ((simple-array (unsigned-byte 8) (*))
          *big-vector-u8*))

(defvar *big-vector-u8*
  (make-array 100_000_000 :element-type '(unsigned-byte 8)))

(reduce (lambda (x y) (+ x y)) *big-vector-u8*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
  4.647 seconds of real time
  4.636290 seconds of total run time (4.572286 user, 0.064004 system)
  99.76% CPU
  11,124,966,564 processor cycles
  98,896 bytes consed

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

bit-vectorを指定

(declaim ((bit-vector 100000000) *big-vector-bit-vector*))
(defvar *big-vector-bit-vector*
  (make-array 100_000_000 :element-type 'bit))

(reduce (lambda (x y) (+ x y)) *big-vector-bit-vector*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
  4.867 seconds of real time
  4.852303 seconds of total run time (4.844303 user, 0.008000 system)
  99.69% CPU
  11,651,081,796 processor cycles
  33,456 bytes consed

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

アクセサで扱う型を指定しての最適化

上記のベクタの型を指定しての最適化と併せ、アクセサで扱う型も特定化することで高速化します

(reduce (lambda (x y)
          (declare (bit x y))
          (+ x y))
        *big-vector-bit-vector*)
;⇒ 0
#|------------------------------------------------------------|
Evaluation took:
  4.682 seconds of real time
  4.688293 seconds of total run time (4.688293 user, 0.000000 system)
  100.13% CPU
  11,208,257,712 processor cycles
  107,792 bytes consed

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