コムソート

もう一つソートをやってみました。自分でもできそうなやつ、ということでコムソートにしました。虚無僧と、じゃないです(||_ _)。コームとか、コウムの方が近いですか。コム(Comb)は、くし(櫛)のことらしいです。クシで鋤いていく感じからそういわれるようです。「隣同士を比べて並び替える」を何度も繰り返すバブルソートと呼ばれる方法の改良版なのだそうですが、動作が速い上にメモリーもあまり使わないのだそうです。コードも単純ですから、ま、優秀なソートですね。1990年頃に開発された、ソートとしては新しいものらしいです。

手順は単純です。まず、リストの全長を1.3で割って(小数点以下切り捨て)、それをギャップに設定します。そして、そのギャップの分だけ離れた場所にある2要素を比較して、逆順だったら入れ替えるという処理を繰り返します。左端から順に、ずらしていって、右側が端に当たってギャップが取れなくなったところで終わりです。次に、ギャップをまた1.3で割って、新しいギャップとして、同じことを繰り返します。ギャップが0になったら、最後の仕上げとして、バブルソートをかけます。バブルソートは遅いのが欠点なのですが、もうあらかた揃っているので、ほとんど時間はかかりません。1000個のリストでためしてみると、大低あと一回で全部揃います。30000でも7回くらいのようです。

"1.3で割る"というのは怪しげですが、この値は経験的に決められたものらしいです。だんだんとギャップを狭めていくことを、クシの目を細かくしていく、と考えるようです。

単純に比較回数を減らそうとしたら、ギャップを割る定数を大きくすればいいわけですが、まず、最低限1より大きくないといけません。で、3項目リストのことを考えたら、1.5以下じゃないと、整列できません（ってことはないな、バブルソートになってしまう、ってことですか。）。というふうに考えていくと、上限がだんだん下がってきそうですが、1.3付近に収束するんですかね。やってみると、ギャップが0になった時点での整理漏れが1.3くらいで一番少ないようです。

さて、Mopsで実装です。普通にやってもアレなので、普通じゃない手を二つ使いました。ひとつは、1.3で割るときに浮動小数点数を使わなかったこと。もう一つは、Local Sectionを使ったことです。前者は多分、かえって遅くなるやり方ですが、後者は速くなる手だと思います。ま、浮動小数点数の回避のやり方は、固定小数点数の計算方法で、昔、コンピュータが小数が苦手だった頃は、普通に使われていた方法だと思いますが。

LOCAL SECTIONというのは、Mops特有の技巧です。局所変数をセクション内の複数のワードで共有できるようにする方法です。MopsはC言語系のライブラリ関数を呼んだりするせいで、局所変数を長い間保持しておきたいという事態が起こりやすいようです。局所変数は1ワードの間有効ですから、長ーいワードを定義すればいいわけですが、それはコードを読みにくくし、保守を難しくします。大域変数を使えばいいともいえますが、局所変数がレジスタ変数で効率がいいことを考えると、局所変数が何らかの形で保持できれば、それに越したことはないといえます。かくして、Local Sectionが実装された、ということのようです。

ですから、Local Sectionは、そのセクション全体が一つのワードであると考えるとわかりやすいでしょう。一つのワードを、外見上、複数のワードに区切って定義することができる、と。実際、本体であるワード以外のセクション内のワードは、セクションの外から呼び出すことはできません。セクション内では自由に呼び合うことができます。まあ、後方で定義されているワードを呼び出すのには工夫が要りますが。また、セクション内のワードがセクション外のワードを呼び出すのは自由です。

Mopsマニュアルでは、Local Sectionは固有のテンポラリオブジェクトを持つことができるように書かれていますが、Carbon PowerMops以降は、これはできなくなっています。ま、ちょっと残念ですが、あまり必要にならないので、私はそれほど気にしていません(^^;;)。
追記：PowerMops 5.6から、この点はマニュアル通りに動くようになりました！つまり、2005年以降はローカルセクションが固有のテンポラリオブジェクトを持つことができます。メソッドのローカルセクションについても同じです。

前置きが長くなりました。コードを見ましょう。

まず、

[[ObjPtr]] Numbers class_is Ordered-Col

Local  CombSort  { \ left right size pitch yet -- }
.....

はじめの1行は、与えられるリストのポインタを格納するためのObjPtrです(マージソートを参照)。次のコードから、ローカルセクションが始まります。まず、Localと書いて、その後に"セクション名"、そしてMopsの標準的なやり方での"局所変数の宣言"を書きます。名前付きパラメターを持つこともできます。要するに、このセクション名のワードを一つ定義するのだと考えてもいいです。

続いて、セクション内部的なワードを定義していきます。

: Comb
 BEGIN
  right size <
 WHILE
  left at: numbers
  right at: numbers \ -- lv rv
  2dup >
  IF \ if left > right, interchange values
   left to: numbers
   right to: numbers
   true -> yet
  ELSE \ if left <= right, do nothing
   2drop
  THEN
  1 dup ++> left ++> right \ paralell transposition
 REPEAT
;

怪しげな英語のコメントも付けてみました。コメントも説明が必要ですね(^^;;)。名前のCombは「くし」という名詞のつもりじゃなくて、「くしけずる」とか「鋤く」とか、動詞のつもりでした。"right"、"left"、"size"は全部局所変数ですね。セクション内の別のワードで設定されて、ここにやってきます。

この"くし"は二本歯です。"left"が左の歯、"right"が右の歯です。後で出てくる"pitch"の分だけ間が空いています。この「くし」を、与えられたリストに当てて、値を二つ掻き出します。はじめは左に歯をリストの左端に合わせます。スタックには、左、右の順で積み込みます。

次に"2dup"でこの二つの値をコピーしてその大きさを比べます。左に小さい方を置きたいので、もし右の方が小さかったら、リストの値を入れ替えます。スタックは、上の方が右の値ですから、「左、右」と押し込めば入れ変わります。逆順じゃないときには、何もしません。余分な値は"2drop"で落としておきます。

なお、値を交換したときには、局所変数"yet"を"TRUE"にしていますが、これは後でバブルソートに使うためのものです。

そして、「くし」を一つだけ右に平行移動して、また同じようにくしけずります。これをずーっとやって、右の歯がリストの右端に当たるまで続けます。

次のコードは：

: BUBBLE
 BEGIN
  0 -> left
  1 -> right
  false -> yet
  comb
  yet
 NUNTIL
;

これは、最後の仕上げに使うバブルソートです。要は、ピッチ(ギャップ)を1に固定したコムソートで、もう逆順がなくなるまで、何回でもかけるわけです。はじめに"false"にセットした"yet"が、もし逆順があれば"true"になって帰ってきますから、「ならもう1回」となるわけです。逆順がなくなれば、"yet" は"false"のままで帰ってきますから、ループを抜けて終了です。

さあ、本体です。

:LOC CombSort ( ^obj -- ) \ { \ left right size pitch yet -- }
 -> numbers
 limit: numbers dup -> size
 10 * 13 / -> pitch
 
 BEGIN
  pitch 0>
 WHILE
  0 -> left
  pitch -> right
  comb
  pitch 10 * 13 / -> pitch
 REPEAT

 BUBBLE
;LOC

ここで、このセクションは大団円を迎えます。この本体ワードの定義は、普通の、コロン、セミコロンではなくて、":LOC"で始め、";LOC"で終わることになっています。そして、セクションの最後に来ます。

このワードは、Ordered-Colクラスのリストのポインタを引数としてとります。まずそれを、"numbers"に格納します。そして、"Limit:"メッセージでリスト全体の大きさをとります。これは、局所変数"size"に格納されると同時に、"1.3"で割って局所変数"pitch"に格納されます。 このpitchが「くし」の目のサイズを決めるもので、一応、最初の目が決まるわけです。

1.3で割るために、10を掛けてから13で割っています。こういうやり方をすると、大きな数値が来たときには、10を掛けた時点で桁が限界をはみ出してしまい、正しい結果が得られない場合もあります。ですが、今の場合には、Ordered-Colクラスのサイズの限界が2バイト整数なので、この範囲なら桁がはみ出してしまう虞れはありません。もっと大きいサイズのリストをソートしたいなら、別のクラスを定義してつくることになるでしょう。そのときには、素直に浮動小数点数を使えば大丈夫です。

次のループですることは、"left"を左端にセットし、ピッチの分離れた値に"right"をセットした上で「くしけずり(Comb)」ます(^^;;)。戻ってきたら、"pitch"をまた1.3で割って、目を細かくして、同じことを繰り返します。"pitch"が0になったら、このループは終わりです。

最後の仕上げに"BUBBLE"をかけます。

体感的には、確かにマージソート並には速い感じですが、多分、項目数を相当大きくしないと、体感じゃわからないでしょうね(^^;;)。小さいリストならバブルソートでも差はないでしょうね。コムソートの改良版というのもあるそうで、"pitch"が9か10になったときはその後のしくじりが多くなって最後のバブルソートに負担がかかって遅くなるので、そのときには無理矢理11にしてしまうのだそうです。ま、簡単に変えられますよね。

---

トップページへ
< 目次へ

---