Next: 3.2 差分リスト Up: 3 差分リストの使い方 Previous: 3 差分リストの使い方

3.1 クイックソートの原理

クイックソートは, ソートすべき数値の集合の中から一つを取りだし, その数よりも小さい集合と大きい集合との２つに分け,それぞれの集合の中で, さらに一つを取りだし, その中で大きい集合と小さい集合とに再帰的に分類していく方法である. クイックソートを使えば, NlogN 回の比較回数で済ますことが期待できる.

図 3.1: クイックソート

まず, リストで与えられた数列の中から数値を１つ取り出して, ２つの集合に分けることを考える.(とりあえず,数値が同じだった場合のことは考えない)

  qsort([H|T]) :- true | compare(H,T).

  compare(V,[H|T]) :- V > H | compare(V,T), 小さい方の集合に H を加える.
  compare(V,[H|T]) :- V < H | compare(V,T), 大きい方の集合に H を加える.

とすればよい. しかし, グローバル変数という概念は, KL1の世界にはないため, 集合を蓄える場所として KL1 ではゴールの引数を使用(利用)する.

   qsort([H|T]) :- true | compare(H,T,L_small,R_small).

   compare(V,[H|T],L_small,R_large) :- V > H |
           compare(V,T, L_small に H を加えたもの, R_large).
   compare(V,[H|T],L_small,R_large) :- V < H |
           compare(V,T, L_small, R_large に H を加えたもの).

では, L

small に H を加えたものをどう表現すればよいだろう. 長さがわからない場合はリストで表現するとよい. (長さがわかっているような場合には,複合項やベクタを利用する方法もある. )例えば, 1 と 2 と 3 の集合は [1,2,3] と長さ3のリストで表現すればよい.

リストで情報をどのような順番で記録して行けばよいのであろうか. この記録の仕方には, 2つの方法がある. スタックとキューである.

LIFO法(スタック)
データを次々に積み上げて行く方法である.

図 3.2: LIFO

述語 compare の場合には, L
small に H を加えたものは [HL
small] になる. 集合の初期値は, 空集合であるので, [](空リスト)にしなければならない.
```
   qsort([H|T]) :- true | compare(H,T,[],[]).

   compare(V,[H|T],L_small,R_large) :- V > H | New_L = [H|L_small],
       compare(V,T,New_L,R_large).
   compare(V,[H|T],L_small,R_large) :- V < H | New_R = [H|R_large],
       compare(V,T,L_small,New_R).
```

FIFO法(キュー)
データを次々に後尾に挿入して行く方法である.

図 3.3: FIFO

small に H を加えたものは,L

small を [H

次に加える変数] にする. また最後は, [](空リスト)で集合を閉じるようにしなければならない.

   qsort([H|T]) :- true | compare(H,T,ExL_small,ExR_large).

   compare(V,[]   ,L_small,R_large) :-  true | L_small = [], R_large = [].
   compare(V,[H|T],L_small,R_large) :- V > H | L_small = [H|New_L],
       compare(V,T,New_L,R_large).
   compare(V,[H|T],L_small,R_large) :- V < H | R_large = [H|New_R],
       compare(V,T,L_small,New_R).

これらの記憶方法には, 共に異なる特徴がある. LIFO法では, 実行中のゴールが, 生成したデータの集合を常に参照でき, 集合内のデータを検査しながら仕事ができる. またデータの入ってきた順とは, 逆にデータが並ぶので,データの並びを逆転するのにも向いている. 一方, FIFO法では,実行中のゴールは, 生成したデータの集合を参照できないが,外部のゴールから, 生成したデータが見え, 並列処理できる(並列性がある).

どちらの方法がよいかは, プログラマがアプリケーションを見て判断する. この場合,LIFO法での利点はないので, 並列性のある FIFO法の方が好ましいようである. (LIFO法でもできないわけではない.)

これで, 数を 1つ取り出して, それよりも小さいものの集合と大きいものの集合が得られた. 次に小さいもの集合の中で, さらに数を 1つを取り出して, 同様に分類するようにしなければならない. 再分類する処理方法は全く同じなので, もう一度最初から呼ぶようにすればよい.

   qsort([H|T]) :- true | compare(H,T,L_small,R_large),
        qsort(L_small), q_sort(R_large).

   compare(V,[]   ,L_small,R_large) :-  true | L_small = [], R_large = [].
   compare(V,[H|T],L_small,R_large) :- V > H | L_small = [H|New_L],
       compare(V,T,New_L,R_large).
   compare(V,[H|T],L_small,R_large) :- V < H | R_large = [H|New_R],
       compare(V,T,L_small,New_R).

このプログラムは, 動作中は図のように ``compare"が木のノードとして,足(ゴール同士がつながるストリーム)を2本持ち, 末端に ``qsort"つながるような形になる.

図 3.4: Binary Tree

このプログラムを述語名を木の名前にして, 値が同一だった場合の処理やデータの終わりの処理を付け加えれば次のように完成する.

  node([],V,L,R) :- true | L = [], R = [].
  node([H|T],V,L,R) :-  H > V  | R = [H|NR], node(T,V,L,NR).
  node([H|T],V,L,R) :-  H < V  | L = [H|NL], node(T,V,NL,R).
  node([H|T],V,L,R) :- H =:= V | node(T,V,L,R).

  terminal([])    :- true | true.
  terminal([H|T]) :- true | node(T,H,L,R), terminal(L), terminal(R).

Next: 3.2 差分リスト Up: 3 差分リストの使い方 Previous: 3 差分リストの使い方

KLIC