ソート(Sort)というのは、順序よく並べることです。めちゃくちゃな順番で並んでいるリストを、特定の順番にしたがって並べ替えます。普通、大小関係を考えて、小さい順にならべます。基本形としては数値を大小関係に沿って並べ替えられればいいわけです。順序チェック手続を取り替えれば、別の順序関係でもいけるわけですからね。
マージ(Merge)ソートというのは、コンピュータにソートをさせるためのやり方の名前です。ま、ひとつのアルゴリズム(Algorithm)ってことです。速い、らしいです。
CやJavaでのプログラム例の文献は腐るほど溢れてます。多分、Forthの例も本はあるでしょう。ソートアルゴリズムの追求なんていうのは大昔からある分野で、かなり研究されています。まあ、私のような古い人間には、如何にもコンピュータがやること、というイメージですね。そんな古いコンピュータを知ってるわけじゃありませんが。
こういうちゃんとしたことが、私にできるわけもないので、Douglas Hoffmanさんがcomp.lang.forth.macにポストして下さったコードを使います。楽しくお勉強しようと、まあ、そういうことです。
マージソートの考え方は、わかりやすい、っちゃあ分かりやすいです、はい。基本は、まずはじめから小さい順に並んだリストが二つ(リスト1とリスト2とします)あって、それを混ぜ合わせて長いリストをつくるとき、その長いリストも小さい順に並ぶようにする方法を考えます。ま、"順"というのは"左から"ということにしましょう。
簡単ですよね。混ぜ合わせるときに、小さい順にとって、長いリストに左から詰めていけばいいわけです。リスト1の左端とリスト2の左端の大きさを比べます。で、小さい方をとって、長いリストに左詰めで格納します。あとは、引っこ抜かれた方のリスト(1か2)と、長いリストの左端に関するデータを1繰り上げればいいわけですね。大きさが同じだったら、両方移すか、どっちか一方をデフォルトにする、と。後者の方がコードは単純そうですね。で、この過程が"マージ"(併合)という名前の由来ですね。
上の手続を一個一個の要素にバラしたところから再帰的に適用していくわけです。まず、1対の1項目リスト同士を2項目リストにマージするのは簡単ですよね。対になれなかったやつには、また後でね、と、とりあえずほかしときます。1回目の全体適用が済めば、小さい順に並んでいる2項目リスト(と余った1項目リスト)ができます。で、今度は2項目リストにマージ手続を適用すれば、また、だいたい4項目の整列リストの集まりができます。これを繰り返し適用していけば、だいたい、リストの大きさは、その都度倍々で大きくなっていきます。これを最後まで完遂すれば、全部整列できます。でも、半端が出ることがあるのは分かりますよね。この半端のせいで、変に時間がかかったりするのもアレなので、いきなり1項目からやるんじゃなくて、半分、その半分、とトーナメント風にわけてから、適用します。だって、ほら、例えばですよ、1025個のうちの1個が最後まで仲間はずれになったりして、しかも、一番大きい数値だったりしたら、1024と1をマージするにも、1024回比較したりするわけでしょ。512と513でも多くても1024回比較すれば終わるわけですけど、それで全部終わりでしょ。前のは1024個のリストつくる段階で、512と512をマージしたりしているわけで、変な半端がつくと、1回余分なことをしないといけない感じじゃないですか。この半端の繰り込みはリストが小さいうちにやっておけば、一般にはロスは小さいわけですよね、多分。ま、ともかく、トーナメント制が合理的であろう、と。
そこで、いよいよ、コードです。Googleにリンクする方法もありますが、ローカルにコピーしてきちゃいました。
"トーナメント風にわけ"る方法としては、RECURSEが使われています。どの言語でも、その言語の再帰(recurs)手続を使って実装するのが普通のようです。Dougさんのコードを見て、個人的には、そうかRECURSEってこんなふうに使えるんだ、という感じがしました。
まず、
objhandle tempObj
objPtr temp class_is array
objPtr numbers class_is ordered-col
はオブジェクトと、オブジェクトポインタの宣言ですね。TempObjには、与えられたでたらめなリストの写しを動的に生成して、直接にはこのリスト順番を操作します。このリストの一部分を整列して突っ込んでは元のリストに戻し、ということをするわけですね。後の二つは、
ObjPtrです。これは、オブジェクトのポインタ(「まんま」ですね)を格納するための一種の変数で、宣言時にclass_isでクラスをセットしておくと、直接にメッセージを送ってメソッドをバインドすることができます(クラスのセットの形式は他にもあります)。実行時点で、そのクラスのどれかオブジェクトのアドレスを格納するようにすればいいわけです。メッセージは、コンパイル時点でクラスがわかっているので、Early Bindになります。
実は、あとで分かりますが、ObjHandleであるtempObjには、arrayクラスのインスタンスが生成され、そのポインタがtempの格納されます。ですから、中身は同じものですね。いってみれば、tempは与えられるリストの写しのエイリアス、です。メッセージ送付形式が単純になるからこうしたのだと思います。numbersの用途も、大体同じです。ただ、こちらは、与えられる元リストのエイリアスです。ランダムなリストはorderd-colクラスのインスタンスであることが予定されているわけで、そのベースアドレスをnumbersの格納します。実体としてみると、リストはordered-colで与えられますが、整列の途中は同じ要素数で動的に生成されたarrayで行い、整列の都度、元のリストに詰め戻します。この過程でnumbersとtempが代理として働くわけです。
次のmergeの定義を、区切り毎に見ていきましょう。このワードが再帰的に呼び出されるわけです。
: merge { left mid right \ left_end num_elements tmp_pos -- }
mid 1 - -> left_end
left -> tmp_pos
right left - 1+ -> num_elements
...
長い(部分)リストの左端と右端とその(大体)真ん中の値をもらって、それを二つにわけて、順に混合して元の長い部分リスト全体を整列するわけですね。まず、leftを頭(temp_pos)として格納しておきます。これは、後でリストを整列した形で詰め直すときに、どこまで詰め戻したかに関する情報を保存しておく変数です。はじめは、左端、つまり、一個も戻していないわけです。さらに、わけた後の左側のリストの終わりの文字のオフセットとして切れ目の左隣の文字を左端(left_end)に格納しておきます。長いリストの文字数も保存しておきます。
BEGIN
left left_end <=
mid right <= and
WHILE
left at: numbers
mid at: numbers <=
IF
left at: numbers
1 +> left
ELSE
mid at: numbers
1 +> mid
THEN
tmp_pos to: temp
1 +> tmp_pos
REPEAT
....
これは、分割した二つのリストの要素同士をそれぞれの左端から順に比べ、小さい方をコピーして、左から順に整列した形でtempを詰め直しています。どっちかのリストが尽きるまで続きます。
一個ずつとっていけば、どちらか一方が必ず先になくなるので、残った方のリストの処理が必要になります。続くコードは、左が残った場合、そして右が残った場合の事後処理です。
BEGIN
left left_end <=
WHILE
left at: numbers
tmp_pos to: temp
1 +> left
1 +> tmp_pos
REPEAT
BEGIN
mid right <=
WHILE
mid at: numbers
tmp_pos to: temp
1 +> mid
1 +> tmp_pos
REPEAT
....
さて、ここで受け持たされた長い(部分)リストの全体は整列されました。インプットされた全体リストの該当する部分を、これで埋め直しておきましょう。
num_elements
FOR
right at: temp
right to: numbers
1 --> right
NEXT
;
これで、左右二つのリストのマージによる整列はできました。わかりやすいですね、コードは。後は、細分区間に再帰的に適用する構造を考えて、それをRECURSEで実装すればいいわけです。
ちょっと概念図を書いてみると、
MERGE
[Step(n-1)] \
[Step(n)] MERGE
[Step(n-1)] /
MERGE
のようにも描けますね。ここで、[Step(k)]は、k段階での長部分リスト、つまり、左側、右側の半分毎にはもう整列されているリストです。この基本単位が連鎖しているわけです。右端のMERGEに着目して、縦横見方を替えれば、上がリストの左側、下がその右側と考えることができます。与えられてくる半々の整列も、実は前段階で適用されたMERGEの結果、というわけです。これが、連鎖していきます。
さてコードを見ましょう。
: m_sort { left right \ mid -- }
right left <= IF exit THEN
right left + 2 / -> mid
left mid recurse
mid 1+ right recurse
left mid 1+ right merge
;
まず、最初の"right left <= IF exit THEN"は、リストの要素が0以下だと整列のしようがありませんから適用しないよ。ということです。エンドレスというわけにはいきませんから。
そして次の行は、分割するための真ん中を決めています。オフセットは0ベースですから、真ん中を一個増やした方が綺麗に分かれます。"merge"を適用する段階ではそうしています。
そして、"left mid recurse"は上の図の、上の"[STEP(n-1)] MERGE"に当たり、"mid 1+ right recurse"は下のそれに当たります。そして、図の斜線と"[STEP(n)] MERGE"部分が、"left mid 1+ right merge"であるのは当然ですね。
recurseに喰わせるパラメタとmergeを呼び出すときのパラメタの個数が違うのは、概念図の斜線部分が入ると入らないとの違いだ、で納得していただけますでしょうか(^^;;)。形式的には、recurseが"再帰"しているのはm_sort本体であって、Mergeではないから、ということでしょうか。もっとも、m_sortのコードの実体は、中点をとってmergeを呼び出すことではあります。コードの形から見ると再帰しているのは分割するところだけのようにも見え、もしかすると、"再帰"で行われるのはトーナメント制の作成だ、と考える人もいるのかもしれません。最後のMergeはその結果全体に"自動的に"適用されるのだ、と(これじゃわけが分かりませんが)。詳しいコンピュータ科学の考え方は知りませんが、いわゆる数学的帰納法の"(k-1)で成り立つ"っちゅうのに当たるのはMergeなので、これが再帰的に適用されるという言い方は間違ってないと思うんですがねえ。ま、中身がわかれば、名前はいいでしょう。
さて最後のワードです。
: mergeSort ( ^obj -- )
-> numbers
\ instantiate an object in the heap, same size
\ as the array to be sorted
limit: numbers [[[']]] array newObj: tempObj
obj: tempObj -> temp
0 limit: numbers 1- m_sort
release: tempObj \ deallocate heap memory
;
もとの
コメントも残しておきました。
はじめに、整列したいordered-colクラスのリストのベースアドレスをパラメタとして要請します。これは、objPtrとしてnumbersに格納されます。そして、要素数の同じArrayをヒープ内に生成し、それを、tempに格納します。後は、全リストを与えて再帰適用を含んだワードm_sortを呼び出します。終わったらヒープを解放します。
ordered-colクラスのサイズがshort int(16ビット)になっているので、整列できるリストの項目数は、215-1=32767を越えることができません(下手するとクラッシュします)。が、範囲内なら、体感上はめちゃくちゃ高速です。30000くらいでやっても、一瞬です。結果を見ようとプリントはしない方がいいです。相当長い時間固まってしまいます。1000でやってみて、ちょっと壊しちゃったかと思いました(G3 400MHzで表示に20秒強くらいだったと思います。)。ま、並んでましたけどね、小さい順に。
この方法の弱点は、RECURSEを使う点です。これは、機械、とくにメモリへの負担が大きいのです。リターンスタックにいっぱい積むことになる、ということですが、多分、C言語の場合ほどには、負担は無いのではないかと思います。C言語は内部機構としてスタックを一個しか使わない(しかも自動生成でプログラマに見えない)ので、あらゆるデータを(リターン)スタックに詰め込まないといけませんから。んー、でもこの例だと、Cのプログラムの書き方によっては大差ないかな...。
ま、こんなところです。
最終更新：2019年01月01日 11:39
