next up previous contents index
: リストと再帰呼び出し : リストの処理 : リストの処理   目次   索引


リストに対する基本計算

リストについては第 8 章の最初の節で簡単にふれた. リストというのは, 見かけは, 要素としてなにをいれてもいい 配列(ベクトル)のことである. たとえば, [3,2,"cat"] は, 数字 3 を 1 番目の要素, 数字 2 を 2 番目の要素, 文字列 "cat" を 3 番目の要素として持つリストである. リストの要素はまたリストでもよいので,

[3,[3,2,"dog"],"cat"]
は, 数字 3 を 1 番目の要素, リスト [3,2,"dog"] を 2 番目の要素, 文字列 "cat" を 3 番目の要素として持つリストである. さらには要素のない空リスト [ ] もある.

リスト L の先頭要素を取り出すには L[0] を用いてもよいが, 関数 car(L) を用いることも可能である. また, リスト L から先頭要素を除いたリストは, 関数 cdr(L) で求めることが可能である. たとえば,

[429] L=[3,[3,2,"dog"],"cat"];
[3,[3,2,dog],cat]
[430] car(L);
3
[431] cdr(L);
[[3,2,dog],cat]

となる. car(カァと読んでいい) と cdr (クッダーと読んでいい) は LISP 由来の関数名である.

リスト L の長さを戻す関数は length(L) である. 関数 append(L,M) は二つのリスト LM をつないだリストを 戻す. たとえば,

[432] L=[3,[3,2,"dog"],"cat"];
[3,[3,2,dog],cat]
[433] append(L,M);
[3,[3,2,dog],cat,3,[2,5],6]

となる.

リストの使い道は多岐にわたるが, 結果の大きさがあらかじめ予想できないときに 結果をかたつけておく ``袋'' として利用するのは, 一番初歩的な利用法の一つである.

例を一つあげよう. たとえば次のプログラムは, 第 7 章の 試し割りによる素因数分解法のプログラムで, N の素因子をリストにして戻す. リスト L がすでに求まった素因子を格納しておく ``袋'' になっている. 新しい素因子を得たら, 関数 append を用いて, L にその因子を加える.

プログラム

def prime_factorization(N) {
  K = 2;
  L = [ ];
  while (N>=2) {
    if (N % K == 0) {
      N = idiv(N,K);
      L = append(L,[K]);
    }else{
      K = K+1;
    }
  }
  return(L);
}

    
実行例
[430] prime_factorization(98);
[2,7,7]

リストをベクトルに, ベクトルをリストに変換する関数は それぞれ, newvect, vtol である. リストとベクトルの違いは何であろうか? リスト L に対しては L[1] = 3 といった代入ができないのが表面的な 違いであるくらいでほとんど同じものに見える. しかし, リストとベクトルではその内部でのデータ表現法が全く 異っている. ベクトルはメモリのなかでひとつづきの領域が確保され そのなかにデータはインデックス順に格納されると理解しておいてよい. リストはもっと複雑な構造である. データ領域とアドレス領域なる二つの領域を持っている データ構造をセルと呼ぶことにする. リストは, セルの集まりである. たとえば [1,2] というリストは, 次のような二つのセルの集まり である.

\begin{displaymath}
\begin{array}{\vert c\vert c\vert} \hline
1 & 次のセルのアド...
...rt} \hline
2 & 次のセルはもうないよとの印 \\ \hline
\end{array}\end{displaymath}

このような構造の帰結として, リスト L に対して, L[1000] を取り出すのと, ベクトル V に対して, V[1000] を取り出すのを比べると, ベクトルの方が早いことになる. しかし, リストはサイズのどんどん増えて行くデータを格納するには, ベクトルより有利である.

リストの内部構造を きちんと理解するには C 言語の構造体と構造体へのポインタまたは, 機械語の間接アドレッシングの仕組みを理解する必要がある. セルを C 言語の構造体で書くと次のようになる.

struct cell {
  void *data;
  struct cell *next_address;
};

問題 12.3   car, cdr はメモリ上でどのように動作しているのか考えてみよ.

上のプログラムでは L=append(L,[K]); を用いて, リストにどんどん要素を付け足していった. 実はこの方法は巨大なリストを扱うときにはよくない. メモリの無駄使いが生じる.

L = cons(K,L);
と書くとメモリの無駄使いが生じない. cons(K,L) は, carK, cdrL となるようなリストを生成するが, L にあらわれるセルの複製は作成しない. 内部的には, K を格納するセルを作成して, そのセルの次の元として, L を指すようにする. そして, K の先頭アドレスをもどしている. 一方 append(L,[K]) の場合には, 毎回 リスト L に現れるセル全ての複製が作成されて, その最後にK を格納するセルがつながれることになる.



Nobuki Takayama 平成15年9月12日