第15章「配列」

概要

ANSI Common Lispの第15章「配列」を説明します。

配列の概要と機能

配列(Array)とは、一連のメモリ領域を占有するデータ構造です。例えば、10の要素を持つ配列であれば、10個分のメモリへの参照を格納できる一連の領域を占有しています。

C言語の配列であれば説明は以上なのですが、ANSI Common Lispで定められた配列には以下のような機能があります。
  1. 要素の型: 配列の要素は型が同じでなくても構いません。同じであることを要求する場合は指定する必要があります。
  2. 要素の数: 配列の要素の数は、基本的には作成時に定めますが、可変長配列として指定しておけば要素数を変更することもできます。
  3. フィルポインタ: 用意した配列のどこまで使っているかを示す「フィルポインタ」を使うと、要素の追加を動的に行うことが容易になります。
  4. 多次元配列: 配列は多次元でサポートされます。C言語のように1次元配列を使って擬似的に多次元配列を実装するのではなく、ネイティブで「次元」の概念がサポートされます。
2や3の機能を持たない配列を「シンプル」な配列と呼び、4の次元が1次元である配列を「ベクトル」と呼びます。シンプルなベクトルが最も高速なアクセスに向いており、文字列なども一部はこの構造で実装されます。また、第8章「構造体」も内部ではベクトルで実装されています(オプションでリスト構造を選ぶこともできますが、ベクトルの方が一般には高速です)。

このページではベクトルを中心に、配列の機能を紹介します。

配列の生成: make-array

配列を生成するにはmake-array関数を使います。必須の引数は「次元」だけです。
(make-array 3)
; => #(NIL NIL NIL)
(make-array '(3 3))
; => #2A((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL))
(make-array '(3 3 3))
; => #3A(((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL))
;        ((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL))
;        ((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL)))

次元とランク: array-rank, array-dimensions

ANSI Common Lispで「次元(Dimension)」という用語は上の例のように配列の要素数を決定できるような情報を示します。一般的には一番上が1次元、次が2次元、最後が3次元という風に呼ばれますが、ANSI Common Lisp的に言えば3, '(3 3), '(3 3 3)がそれぞれの次元ということになります。

一般的な呼び方の「次元」はarray-rank関数で、ANSI Common Lisp的な意味での次元はarray-dimensions関数で取得できます。
(array-rank (make-array 3))
; => 1
(array-rank (make-array '(3 3)))
; => 2
(array-rank (make-array '(3 3 3)))
; => 3

(array-dimensions (make-array 3))
; => (3)
(array-dimensions (make-array '(3 3)))
; => (3 3)
(array-dimensions (make-array '(3 3 3)))
; => (3 3 3)

型の指定: :element-type

make-array関数で作られる配列は、何も指定しなければ全ての型に対応します。全ての型の頂点はt型なので、型指定を省略するとt型であるものとして扱われる、ということです。
何らかの形で型を指定したい場合、:element-typeキーワード引数で型を指定します。
(make-array 3 :element-type '(integer 0 100))
; => #(0 0 0)

上の例は'(integer 0 100)という型を指定していますが、'fixnum'double-floatなどを指定することもできますし、あらゆる型指定子が使えます。

初期値の設定: :initial-element, :initial-contents

配列を生成する際には、初期値を設定することもできます。一つの値を全ての要素に設定する場合は:initial-elementキーワード引数を、全ての要素に対応する値を設定するには:initial-contentsキーワード引数を使います。
(make-array 3 :initial-element 1)
; => #(1 1 1)

(make-array 3 :initial-contents '(1 2 3))
; => #(1 2 3)

下の例のような場合はcoerce関数で型の変換をして配列を生成することもできます。
(coerce '(1 2 3) 'vector)
; => #(1 2 3)

可変長配列: :adjustable

概要で説明した通り、ANSI Common Lispの配列は可変長にすることができます。可変長配列を使うには、:adjustableキーワード引数を指定します。
(defparameter *vec* (make-array 3 :initial-element 1 :adjustable t))
; => *VEC*

*vec*
; => #(1 1 1)

見た目は普通の配列ですが、可変長なのでadjust-array関数を使えば要素数を後から変更することができます。
(adjust-array *vec* 10)
; => #(1 1 1 NIL NIL NIL NIL NIL NIL NIL)
*vec*
; => #(1 1 1 NIL NIL NIL NIL NIL NIL NIL)

フィルポインタ: :fill-pointer

可変長配列は実際に配列の要素数を変更するため、比較的重い処理になりますが、見かけ上の要素数を変更するならフィルポインタを使うこともできます。

先に多めの要素を確保しておきますが、:fill-pointerキーワード引数で要素よりも短い要素番号を指定しておきます。
(defparameter *vec* (make-array 10 :initial-element 1 :fill-pointer 3))
; => *VEC*

*vec*
; => #(1 1 1)

そして、フィルポインタの変更が必要になればfill-pointerアクセッサをsetfマクロと共に使用します。
(setf (fill-pointer *vec*) 10)
; => 10

*vec*
; => #(1 1 1 1 1 1 1 1 1 1)

可変長とフィルポインタの併用: vector-push, vector-pop, vector-push-extend

フィルポインタはこのように可変長引数とは独立した機能ですが、組み合わせれば「バッファ」として使うこともできます。

まず、可変長とフィルポインタのキーワード引数を合わせて配列を生成します。
(defparameter *vec* (make-array 3 :element-type 'base-char 
                                  :adjustable t 
                                  :fill-pointer 0))
; => *VEC*

*vec*
; => ""

要素の型に'base-charを設定したところ、表示が変わったと思います。実は、文字列は一般に'base-char型の1次元配列(ベクトル)なので、*vec*は文字列になっているのです。

ここに文字を追加してみます。文字を追加するにはvector-push関数を使います。
(vector-push #\c *vec*)
; => 0
(vector-push #\o *vec*)
; => 1
(vector-push #\m *vec*)
; => 2

*vec*
; => "com"

ところが、もう少し追加しようとすると、うまく追加できません。
(vector-push #\m *vec*)
; => NIL
*vec*
; => "com"
vector-push関数の返り値がnilの場合は、ベクトルのフィルポインタが要素数を超えてしまったことを意味します。このような場合は、adjust-array関数で要素数を変更しても構いませんが、ANSI Common Lispではもっと便利なvector-push-extend関数が定められているので、自動で要素数を変更しながら、要素を追加していくことができます。
(vector-push-extend #\m *vec*)
; => 3
(vector-push-extend #\o *vec*)
; => 4
(vector-push-extend #\n *vec*)
; => 5
(vector-push-extend #- *vec*)
; => 6
(vector-push-extend #\l *vec*)
; => 7
(vector-push-extend #\i *vec*)
; => 8
(vector-push-extend #\s *vec*)
; => 9
(vector-push-extend #\p *vec*)
; => 10

*vec*
; => "common-lisp"

このように、可変長配列とフィルポインタを併用した使い方は文字列のバッファとして使えるので、しばしば用いられます。

配列の参照

配列への参照は、aref関数またはsvref関数で行います。これらはアクセッサとして定義されているので、setfマクロと共に使えば値の設定を行うことができます。

配列はarrayクラスを親クラスとして階層化されています。型については第4章「型とクラス」にまとめていますので、そちらも参照してください。

配列一般への参照: aref関数

arefアクセッサは、配列一般に対する汎参照として使用することができます。
(defparameter *array* #2a((1 2 3)(4 5 6)))
; => *ARRAY*
*array*
; => #2A((1 2 3) (4 5 6))

(aref *array* 1 2)
; => 6

(setf (aref *array* 1 2) 60)
; => 60
*array*
; => #2A((1 2 3) (4 5 60))
arefの第1引数は参照したい配列、第2引数以降は配列の次元( Dimension )に対応するインデックスです。そのため、arefは可変長引数を取るということになります。

simple-vectorへの参照: svref関数

arefは非常に便利なアクセッサですが、配列の次元に合わせて可変長引数を取るので、必ずしも処理が高速な訳ではありません。

そのため、配列の中でも最も使用頻度の高いsimple-vector(要素数が可変長ではなく、フィルポインタもなく、ランクが1次元のベクトル)に対しては特別なアクセッサが用意されています。それがsvrefです。
(defparameter *sv* #(1 2 3 4 5 6))
; => *SV*
*sv*
; => #(1 2 3 4 5 6)

(svref *sv* 5)
; => 6
(setf (svref *sv* 5) 60)
; => 60

*sv*
; => #(1 2 3 4 5 60)
svrefは第1引数にsimple-vectorを取り、第2引数にインデックスを取ります。svrefarefと異なり固定長引数なので、より高速にアクセスできます。

0 件のコメント :

コメントを投稿