コンピュータの基礎的で古典的なアルゴリズムのひとつとして、整列(Sort)アルゴリズムがあります。これは、複数の要素を、ある順序規準にしたがって、順序よく並べ直すというものです。順序規準としては、あいうえお順とかアルファベット順のような辞書的順序や、値の大小というのが基本的です。
ソートに関しては、
Mops細説B面の最後の方に、Douglas Hoffmanさんの
マージソートと、自分で書いた
コムソートについて、Mopsのコード例を説明しました。ので、ここではソートアルゴリズム全般の話、それとよく使われると言われるクイックソートのコードとアルゴリズムを少し詳しく解説して、ついでに少し一般論も書いてみようかと思います(また長大で無内容な説明！(||_ _)。クイックソートのコードは、自分で端から書いたものじゃなくて、Wil Badenという方の書かれた"qsort"コードを少しもじったものを使います(ってか、アルゴリズムがわかりやすくなうように、だいぶ変えちゃいました。速度落ちたかも^^;;)。この"qsort"は標準Forthのコードで、ここにあったものです。だいたい、よく見かけるC言語で書かれたコードと、やってることが同じなので、わかりやすいかと思います。ちなみにC言語の標準ライブラリにqsort()という関数があって、クイックソートを実装しているそうです。まあ、それを
システムコールで呼んでも良いんですが、Mopsだと比較の関数ポインタ渡すの面倒だし、そんなもん使っちゃコードの解説ができません(^^;;)。
ソートアルゴリスムのパラダイム
どのようなソートアルゴリスムが「いい」とされるかの規準ですが、要は、速くかつ余分なメモリー領域の消費が少ないのが、いいソートアルゴリズムです。まあ、アルゴリズムの一般的な評価基準ですね。ただ、「速い」という点についてですが、ソートの場合、これは、比較・配列手数の回数が少ないというところで判断します。その手数のことをソートにかかる「所要時間」と考えるわけです。実際には、他にも一時的なメモリ領域を準備したり、データを構造化したりするなど、付随的な操作が必要な場合もあるので、現実にコードの実行速度が速いかどうかは、比較・配列の手数だけでは決まりません。ですが、一応の目安にはなるということです。
処理速度規準
一般論ですが、処理速度効率の規準としては、処理されるべきデータの大きさの規模を表現するような整数Nをとり、数Nがうんと大きくなったとき、Nの増大に伴ってどの程度の規模で所要時間が増えていくか、を考えます。Nが大きくなっても、所要時間がなるべく急速に増えたりしないものが速度効率のよいアルゴリズムといえるわけです。そういうアルゴリズムを単純に「速いアルゴリズム」といってしまうこともあります。が、これは「効率」であって、実際の処理の「速さ」そのものではないことに注意しましょう。ソートの場合は整列されるべき項目の個数をNとしてとります。
処理速度効率は、時間計算量と呼ばれる「Nの式」で表わされます。ま、効率の逆数、っていことですかね。大きい方が効率が悪い、と。その規模(ランク)を示すときはO([Nの式])という形で表します。Nが大きくなっても所要時間が変わらないときは、O(1)と書きます。ま、うるさくいえばO(N0)なんでしょうね(N=1って意味じゃないですよ、念のため。^^;;)。ソートアルゴリズムでは、そういう速さのはないと思います。アルゴリズムの時間計算量の規模として良く見かけるものを小さい(速い)順に並べると、O(log N)、O(N)、O(N log N)、O(N2)、O(2log N)、O(2N)くらいですかねえ。なんか数値kで、O(Nk)と表記できるものより小さいものは、多項式時間のアルゴリズムと呼ばれていて、「計算機で計算するのが現実的といえる程度には効率的」なアルゴリズムと考えられているようです。まあ、O(N10)なんてのは、本当は効率が悪すぎて、「現実的」かどうか怪しいんですが、そこは、形式的に切れるところで、という話なわけです。O(2N)というのは、総当たりで調べるしかない、という意味なわけで、ある意味そのアルゴリスムの効率は最悪ということです。Nがごく小さいときじゃないと、手間が相当かかります。こういうものは、現実に入力されたデータについて、何か特徴がないかを下調べして、それを利用して効率を上げるという方法が、一般的には考えられます。ただ、現実問題としては難しく(下調べに手間がかかったりもするし)、長年未解決の問題がある領域のようです。なお、logという記号は、対数を意味し、log25などと書くと、「2x=5」となるような値xを意味します。アルゴリスムの時間計算量を表現するlogには、小さい添え数字がついてませんが、常に2であると仮定されます。いつも2だから省略しちゃってるんですね。この小さい添え数字は底(base)と呼ばれるんですが、底が2の対数を考えるってのは、ビットで考えるという意味なわけで、これデジタル関係ではよくある話です。ちなみに、情報量とかもビットで表します。ほんとは、情報理論(Shanon理論)はデジタルには限られない話なんですけど、そっちはyes/noの二値で切るっていう発想なのだろうと思います。ともかく、コンピュータ関係のlogでは小さい2が省略されていると思ってください。
計算効率を考えるとき、最悪の場合の手順を考える見方と、平均的場合を考える見方があります。平均を考えるのは、複雑な事情を勘案しないといけないので一般には難しいのだそうですが、ソートアルゴリズムに関しては、研究が進んでいるという事情もあり、だいたい平均的処理効率がわかっています。普通実用的なのはだいたいO(N log N)の効率を持っています。ソートの効率としては限界のようです。わかりやすいが遅い例としてよく使われるバブルソートはO(N2)になります。
クイックソート
いくつか知られているソートアルゴリズムの中でも、大抵の場合一番速い、と言われているのが、クイックソートです。名前も速いことを強調してますね。でも、最悪の場合はO(N2)になることもあります。つまり、入力されたデータの並び方によって、手間が異常に増えたりするんですね。平均はO(N log N)ですみます。こういう、入力データの性質によって性能に段差が生じるソートアルゴリズムは不安定ソート、生じないものは安定ソートなどと呼ばれます。安定ソートアルゴリズムとしてはヒープソートが有名ですが、ここでは説明しません。
時間計算量ということでいくと、クイックソートはヒープソートや
マージソートより大抵は多くなるはずなわけですが、現実にはそれらより速いことが多いのです。というのは、比較・整列の手順そのものが、クイックソートが一番簡単になっているからです。簡単な処理は複雑な処理よりコードが短く、手数が多少多くても、一回あたりの速さのおかげで速いソートができてしまうのです。
とりあえず、コードを一瞥
まあ、能書きはこれくらいにして、コードを出しておきます。
qsort.txt
そう長くはないですね。Arrayクラスのオブジェクトを使って、数値のリストをつくり、それを小さい順に整列するというコードになっています。このオブジェクトは、1セル(4バイト)のアレイが実体で、インデックス(0から始まる)を用いたメッセージ(at: ( idx -- val )で取り出し、to: ( val idx -- )で格納)で値を操作できるようになっています。実質からみて普通のForth風アレイを使っても大差なかったんですが、一応、
コムソートや
マージソートと揃えました(Ordered-ColはArrayのサブクラス)。ざっとみて、2dupと2dropというワードが気になるかもしれません。これらは、どちらもスタック操作ワードです。まず、2dupですが、これは、スタック上の二つのアイテムを対としてみて、その対を複製(dup)するワードです。つまり、スタック効果は
2dup ( x0 x1 -- x0 x1 x0 x1 )
となります。
2dropは、同じように二つのアイテムを一対として、それをスタックから落とします。つまり、二つアイテムを捨てるんですね。スタック効果は、
2drop ( x0 x1 -- )
となります。
あと、特徴として、再帰(ワード"recurse")が二回使ってあります(ワード"(qsort)"の定義中)。CとかJavaとかネットでよく見かけるコード例でも、同じように再帰を使っていますね。あとで少しいじってみましょう。
Mops/Forthで書かれたアルゴリズムを自分で追える人は、追ってみてください。途中でわからなくなったとしても、有益です。
クイックソートアルゴリズムの特徴
まず、大雑把に、クイックソートアルゴリズムが、どういう理屈に基づいてリストを整列するのかを考えてみます。端的に言うと、これは、相対的に大きい要素と小さい要素を塊として分ける、という原理に基づいています。左から右に小さい順に並べたいとするなら、相対的に小さいものは左側、大きいものは右側に寄せます。初めは全体を二分し、次に分割された各部分に同じ手続を適用する、という順で、再帰的に段々と適用範囲を細かくしていきます。そして、この分割手続が適用された塊が最終的に2個以下になれば、最後に左右に振り分けられる「塊」は一個の要素なわけで、結果としてはまさに、小さい順に左から並んでいるはずです。
「相対的に大きい」とかいうのはどうやって決めるのかというと、いま分割しようとしている塊の中から適当に要素をとってそれを基準値として使います。この基準値より小さい要素は左に、大きい要素は右に振り分けるのです。基準値アイテムはピボットなどと呼ばれることが多いようです。この基準値は、ちょうど真ん中の大きさがとれれば理想的です。クイックソートの効率の「最悪の場合」というのは、この基準値に、いつも最大値とか最小値とかをとってしまうことによって生ずるのです。これを回避しようとして、右端、真ん中、左端の三つくらいのアイテムをとって平均した値を基準値に使うことで最適化するコード例もあります。ですが、これは数値の整列でないと適用しにくいように思われます。文字列の整列のとき、平均をとるのは結構難しいですよね。
ときたところで、「おや？」と思ったあなたはさすがです。基準値アイテムを取る、といってたのに、三つのアイテムを平均したら、それに当たるアイテムがあるとは限らないじゃないか、と。そのとおりです。でも、クイックソートの原理としては、ピボットアイテムが存在するかどうかというのは本質的ではないのです。要は、ある箇所を境に、相対的に小さな要素と相対的に大きな要素の二つに分割できるように分けられれば、ソートはできるのです。
標準的な解説では、
| 基準値より小さいアイテム |
基準値 |
基準値以上のアイテム |
のように分割すると説明して、実際にそうなるように実装しているものもあります。もちろん、それでいけないことはないんですが、そうしなければいけないわけではないのです。最低限、
と分けられれば、ソートのためには充分なのです。というのは、分割後のグループAの左隣のグループにはAのどの要素よりも小さいか等しいものしか含まれておらず、右隣のグループには、Aのどの要素よりも大きいか等しい要素しか含まれていないからです。このグループの要素を2個にまで砕いていけば、最終的には小さい順に左から整列されることは、少し考えればわかります。特定の要素を分割地点に置こうと考えるより、単に二つに分けると考えると、分割時の手続が大雑把ですむ分だけコードが単純になると予想できるわけで、その分、速くなることもあるでしょう。ここで用いるqsortのコードも、この方法を採用しています。このグループ分けの部分のコードがクイックソートの本体で、分割された各部分にそれを引き続き再帰適用していきます。
Partition
分割処理の本体となるワードはpartitionです。定義コードは:
: partition ( l r -- l1 r1 l2 r2 )
2dup + 2/ at: numbers >r ( r: -- pivot )
2dup
begin
swap begin dup at: numbers r@ ( pivot ) < while 1+ repeat
swap begin r@ ( pivot ) over at: numbers < while 1- repeat
2dup <= if ?Exchange swap 1+ swap 1- then
2dup >
until
r> drop \ throw pivot away
swap rot ;
1ワードの定義としてはちょっと長いですね。このワードのすることは大別して二つあります。ひとつは、区間の左端と右端のアイテムのインデックスを入力として、基準アイテムを決め、それにしたがってより大きいものは右に、より小さいものは左に寄せて分割すること。もうひとつは再帰適用に備えて、必要な分割後の二つの小区間のそれぞれの左端と右端のアイテムインデックスを出力することです。
BEGINループ
beginとかwhileとかについて説明しておきます。これは
ループのためのワードです。Mops/Forthには、だいたい、3つの種類の
ループがあって、ひとつが前に説明しことのあるDO-LOOP、もうひとつが、ここにあるような、BEGINを使うもの、そして、三つ目はFOR-NEXT
ループです。FOR-NEXT
ループだけは、Forth標準(94)には含まれていません。BEGIN
ループでは
ループのインデックスが自動でついてはきませんが、単純な機構の
ループで、脱出の仕方についていくつかのバリエーションがあり、便利です。begin-while-repeat
ループでは、まずbeginとwhileの間に
ループを続けるかどうかを決定するコードを書きます。これは最初に実行されます。ここで、トップスタックに真偽値を残すのです。0は偽、0以外は真と判断されます。whileがこれを消費して、もしも、真であれば、whileとrepeatの間にあるコードを実行し、repeatに至ったところで、beginまで戻って再実行します。スタック値が偽であったときは、repeatの後ろに飛んで、
ループを抜けます。もうひとつ、begin-until
ループも使われていますね。この
ループでは、まず、beginとuntilに囲まれた部分のコードを1回は必ず実行します。その過程で、トップスタックに真偽値を残しておきます。untilはその値を消費し、それが偽であればbeginに戻って再実行します。真(非0)であれば、そのまま通りすぎて
ループを抜けます。真になるまで(until)繰り返す、という意味ですね。
流れの説明
さて、処理の流れを説明しましょう。
最初に、分割を適用する区間の中間のアイテムを取って、これを基準値とします。この値は"pivot"として、コード中に
コメントを付けておきました。Forthらしくリターンスタックに入れておきます。Forthでは、リターンスタックは一時使用メモリ領域としてプログラマが利用できるのです。">R"は、
データスタックのトップ値を取って、リターンスタックに格納するワードです。pivotは、begin-while-repeat
ループの中で何度も参照されるので、Mopsでは局所変数の方が若干の速度効率化が図れると考えたんですが、実際にやってみると、大差はない(1~2%くらい)んですが、リターンスタックを使った方が速いという結果がでました。ちょっと、予想外なんですが、リターンスタック操作ワードもコンパイル時に最適化されますし、様々な事情が関連した結果でしょう。この辺については、別の機会にもう少し考えてみたいと思います。
最初の"begin"の手前で2dupしているのは、入力値が、出力値の一部として必要だからです。上に述べたように、このワードは二つの区間に分割した境界を出力しなければいけないので「左端、区切1」が区間1、「区切2、右端」が区間2となって、右端と左端はまた使われることになるのです。
最初のbeginは終わりの方のuntilまでの
ループですが、これは後回しにして、まず、その中に入れ子になってあるbegin-while-repeat
ループを説明しましょう。初めのものは、左端から項目をひとつずつ調べていって、pivotの値以上のものがないか調べます。スタックを使った大小の比較はわかりにくいかもしれませんが、"A B >"は、"A > B"ということです。値A、Bは消費されて、この不等号が成り立てばTrue、成り立たなければFalseをスタックに残します(前にも説明しましたが。)。ここでは、大小比較ワードを埋め込んでしまいましたが、この部分を別の比較ワードに取り替えれば、いろいろなソートができるわけです。
最初のswapで、左端を指すインデックスがトップスタックにくることに注意してください。なわけで、初めは左端から調べているわけです。R@は、リターンスタックのトップにある値を
データスタックのトップにコピーするワードです。全体の手順としては、pivot値をリターンスタックから
データスタックに写しとり、リスト内のアイテムがそれより小さいうちは何もしないで次に移っていき(インデックスを増やしていく)、見つけたところで
ループを抜けるという内容です。抜けたときに止まったところのインデックスがスタックに残っています。pivot値がこのリストの範囲内に存在しているので、この
ループは必ずどこかで止まります。2番目のbegin-while-repeatは、今度は右端から、pivot値以下の値がないかを調べます。初めのswapで今までスタックの下にしまってあった右端を指すインデックスをトップスタックに置きます。手順としては、初めと逆で、pivot値より大きいものは飛ばしてインデックス値を減らしていき、それ以下のものに当たったところでインデックス値を残して
ループを抜けます。
さて、スタックの上二つの値は、左端からみたとき最初にpivot値以上だったアイテムを指すインデックス値と、右端からみたとき最初にpivot値以下だったアイテムを指すインデックス値となっています。もしも、左のインデックスが右のインデックス以下になっているなら、左側に小さいものを寄せ、右側に大きいものを寄せるという基準からは順序が逆転しているので、これらの場所を交換します。これをするのが、ワード"?Exchange"です。この内容は後でみることにしましょう。この二つのインデックス値のところまでは値を調べたことになるわけですから、それぞれのインデックスを左側は1つ増やし、右側は1つ減らします。 最初のbeginからここまでの操作を、インデックス値が交差して行き過ぎるまで繰り返す、というのが"2dup > until"です。
このbegin-until
ループを抜けたなら、基準値はもういらないので、リターンスタックから取り出して捨てます。r>はリターンスタックのトップから値を取り出して
データスタックに置くワードで、それをdropで捨てます。
全
ループの結果として、左端、右端、区切2(元は左端)、区切1(元は右端)の四つの値がこの順でスタックに残っています。値の状況としては、次の二つが考えられます。
どちらの場合も、分割後の左側の塊としては左端から区切1まで、右側の塊としては区切2から右端までを採るとよいことがわかります。下の図の場合には、区切の間にある値はpivot値に等しいことがわかる(走査のときに両方がその上で停止している)ので、もう場所を動かす必要はないからです。これより左側にはこの値以下の要素が、右側にはこの値以上の要素が集められているので、それぞれの塊を整列しさえすれば、このアイテムを固定しておいても、全体として整列されるはずだからです。
そのようなわけで、出力としては(左端、区切1)と(区切2、右端)の二つの対を作って、それぞれに分割手続を再帰適用すればいいことになります。"swap rot"は、このようにスタック上に二つずつ並ぶように操作しています。
?Exchange
アレイアイテム交換ワードは次のように定義されています。
: ?Exchange { idxL idxR -- idxL idxR }
idxL idxR = if idxL idxR exit then
idxL at: numbers idxR at: numbers \ l-val r-val
2dup = if 2drop idxL idxR exit then
idxL to: numbers idxR to: numbers
idxL idxR ;
このワードは、入力-出力でスタックアイテムに変化を加えることはありませんが、にもかかわらず、二つのアイテムを入力として扱っています。名前付きパラメタを使っています。スタック操作でも同じことはできます。実際、初めはスタック操作で書いていました。ただ、このワード内でスタックアイテム数は多くなりがちなので、局所変数を使った方が実行速度が上がるかもしれないと考えて、試してみたのです。これは、予想通り、若干速くなりました。もっとも、変数の名前の付け方が悪かったのか、コードの見た目が、スタック操作によるよりもゴタゴタした感じになってしまいました。すみません。
初めのチェックは、入力インデックスが同じ値でないかどうかを調べています。同じアイテムを取り出してまた同じ場所に戻すというのは無駄なので、一応ここでチェックして、同じなら後は飛ばして、インデックス値(入力値)をもとのスタックに戻した後、ワードを抜けます。exitは、そこの定義ワードを抜ける、というワードです。
インデックスが違うなら、対応するアレイアイテムを取り出します。
インデックス値だけでなく、アイテムの値が同じ(つまり、pivot値に等しい)だったら交換するのは無駄なのでその場で抜けてもいいわけです。格納する分が省けます。これを三行目でやっています。抜けない場合にはアイテム値はまだ必要なので、複製しておいて比較し、抜けるときには落とします。抜ける前に入力値をスタックに戻しておくことも忘れてはいけません。
こういったチェックをつけると、値を比較してみる分だけ手間が増えてしまいます。正直いって、最初のインデックス値のチェックも、初めはどうかなと思ったんですけど、やってみたらどっちのチェックに関しても、少し実行速度を上げる効果があるようだったので追加したのです。原典のコードにはチェックはありませんでした。しかし、どうも、このコードに関しては、値の取り出し・格納にかかわるメモリーアクセスが、実行速度に結構響くようです。それでも、ソートすべきアレイの中には同じ値の項目はない、ということが保証されているなら、三行目のチェックは外した方がいいでしょう。
チェックを通り抜けてきたなら交換です。スタックには、下から、左アイテム、右アイテムの順で値が置かれているので、まず左インデックスの場所に格納し、次に右インデックスの場所に格納することで、アイテムの交換が実現できます。終わったら、入力値を
データスタックの元の位置に戻して完了です。
ちなみに、条件次第で本体部分の処理をしたりしなかったりするワードの名前の頭に"?"を付けるのは、Forth系ではよくやる手のようです。Forth系ではアルファベット以外で名前を始めることができるし、名前に混ぜてはいけない特殊文字が少ないのも強みと言えます。
(qsort)
最後に、クイックソートそのものである(qsort)を説明します。これは両端のインデックス値を入力として取るのですが、最終的な形式として「アレイオブジェクトを渡せば全体をソートする」ようにしたかったために、名前に括弧をつけておき、これをさらにもう一段の本体ワード"qsort"から呼び出すことにしました。
: (qsort) ( l r -- )
2dup >= if 2drop exit then
partition
( l2 r2 ) recurse
( l1 r1 ) recurse \ tail recursion!
;
ま、Partitionと再帰だけですね(^^;)。前のrecurseは、(区切2、右端)という出力に対する再帰適用、二番目のrecurseは、(左端、区切1)という出力に対する再帰適用と考えることができます。
初めのチェックは、左右のインデックス値が重なっていたり、順序が逆転したりしているときには、ソートする余地がないので、入力値を落とすだけで処理を終える、ということを意味しています。これが再帰の脱出口ですね。このチェックを通ったなら、partition処理を加えます。ワードpartitionからは、分割後の左右の小区間のインデックスが帰ってくるので、それぞれに再帰的に同じ処理を加えていきます。模式的には、次の図のような流れになります。
小区間の両端インデックスについて上の方をスタックの上の方に残ったものとすると、まず、右上に駆け上るわけですね。で、2dropを経由して左下斜め方向に戻ってきて、今度は、下の房の方にうつるわけです。
再帰をいじってみる
さて、再帰が二回も使われていますね。最後のものは末尾再帰なので、簡単に外せます。例えば、
: (qsort1) ( l r -- )
BEGIN
2dup >= if 2drop exit then
partition
recurse
AGAIN ;
でOKです。begin-againもBEGIN
ループの一種で、無限ループです。ですが、exitはワード自体を抜ける、つまり、セミコロンまで飛ぶワードですから、ちゃんと抜けられます。
で、これで再帰がひとつ減ったので、実行速度が上がるかと思ったら、ほとんど全く変わりませんでした。というか、違いが検出できません。実は、もうひとつの再帰も
ループに書き換えて、再帰のないコードにして試してみました。で、今度こそ少しは速くなるか、と思ったら、やっぱり、ほとんど違いありませんでした(Mopsのアレイオブジェクトは32kアイテムが限界なので、30000アイテムでやってみたんですが)。まあ、機構上はリターンスタックの消費量は減ってると思いますが。でも、このワードは局所変数を使っていないので、再帰のときにリターンスタックに保管されるのは、リターンアドレスだけ、なのです。PowerMopsでは8バイトアラインメントになっているので、32ビットマシンでも、リターンアドレスひとつで8バイト使います。でも、一回たった8バイトですよ、ぶっちゃけて言えば。いってみれば、PowerMopsでは再帰は初めから最適化されている、といってもいいんじゃないですかね。最適化を狙って、再帰で定義されたものを頑張って
ループに書き直す必要はほとんどありません。なので、やめときます(^^;;)。
再帰を使うことにしたとして、他のプログラミング言語では、再帰したい関数の名前を使って呼び出すことが多いですよね。Mopsでも、そういうふうにできないこともありません。まあ、遊びですが、次のようなワードを定義してみてください。
: use-recurse postpone nonleaf postpone reveal ; immediate
このワードを使うと、あ～ら不思議、定義中のワードも呼び出せちゃいます(^^;;)。使い方は、
: (qsort2) ( l r -- ) use-recurse
2dup >= if 2drop exit then
partition
( l2 r2 ) (qsort2)
( l1 r1 ) (qsort2)
;
という感じですか。どこでも、コロン、ワード名の後、本体の定義が始まる前に、"use-recurse"と書いておけばいいわけですが。ちょっと"普通の"再帰に近づいたでしょうかね。
なお、iMopsでは、recursiveというワードが定義されていて、上のuse-recurseと同じように使えます。他方、上のuse-recurseは定義できません（nonleafというワードが定義されていないので）。
おまけですが、一応ソートが三つできたんで、速さを比べてみました。クイックソートと
コムソートは、大体同じくらいの速さです。
マージソートはちょっと遅いです。
マージソートのコードは、よく見ると、毎回アイテムを二度移し替えているので、この分のメモリーアクセスが引っ掛かってるのだろうと思います。まだ最適化の余地はありそうです。
クイックソートも
コムソートも、まだ最適化の余地はありますが、劇的には変わらないでしょう。上の話では触れていませんが、Mopsのアレイオブジェクトは、ランタイムにレンジチェックをして、インデックスがはみ出ていないか調べています。このチェックを外すという裏技(？)があるんですが、これをするとかなり速くなります。
クイックソートと
コムソートの速さを比べると、ランダムなアレイで1000項目程度なら
コムソートの方が速いんですが、10000項目くらいになると、クイックソートの方が速くなるようです。感じとして、
コムソートの時間計算量は、O(N log N)より少し大きい規模で増えている感じがします。
追加 -- ちょっとマニアック
ふと思い立ってやってみた最適化について、追記します。
条件分岐や
ループ、まあ、begin-untilとか、begin-while-repeat、Do-Loop、For-Nextのような
ループ、それとif-thenもそうなんですが、こういうのがワードの中に含まれていると、高速に操作できるスタックアイテムの数が厳しくなってきます。その場合でも、だいたい4個まではOKなんですが、ワードPartitionではwhileの前で５個になってますね。これだと限界を超えてしまいます。そんなわけで、一部のアイテムを局所変数にした方が速いかもしれない、と思ったわけです。そしたらびっくり。なんと整列時間が3-4割も減りました。整列前のアレイをつくる分の時間も含めてですから、ソート自体の時間は半分ぐらいになったんじゃないですかね。これで、もう、1000項目程度のアレイでも、
コムソートよりクイックソートの方が速くなってしまいました。その定義は次のようなものです。
: partition { l r \ pivot -- l1 r1 l2 r2 }
l r + 2/ at: numbers -> pivot
l r
begin
swap begin dup at: numbers pivot < while 1+ repeat
swap begin dup at: numbers pivot > while 1- repeat
2dup <= if ?Exchange swap 1+ swap 1- then
2dup >
until
swap l -rot r
;
不思議なことに、名前付きパラメタとして局所変数を使っちゃうと、pivotも局所変数にしても遅くないんですね、これが。"-rot"は、"rot rot"と同値です。downも同義語です。
上の定義だとスタックアイテムが最高4項目に抑えられているので、非常に高速になります。何でかってのは、要はメモリーアクセスが省けるってことです。普通はデータキャッシュがあるので、メモリーアクセスしてもそんなに遅くはならなんじゃないかとも思うんですが、この場合は、単純にインストラクション数がワード総体で4割くらい減っていて、しかも、
ループで繰り返されるんで、こんなに差が出たのだと思います。キャッシュとかの話、前に書きましたっけ？書いた記憶はあるけど、だいぶ前だなあ。どこに書いたんだろ(^^;;)。だだ、理屈でそうなるだろうと予測しても、実際にはOSが介入してくるんで、本当にどう動いてるのかはよくわかりません。実測で速い方が、まあ速いだろう、とか、当たり前のことしか言えないんですよね。一般論としては、こういう細かいことを考えて最適化しようとしても大した効果は得られず、アルゴリズムの変更自体の方がドラスティックに利きます。ただ、速さが二倍になったってのは大きいわけで、それでちょっとびっくりしたわけです。
if-thenとか
ループを含んでいないワードならば、5-6項目程度ではメモリーアクセスは必要になりません(7つまで、です。)。なので、スタックだけで操作するのが一番効率が良くなります。どうしても多くなりそうだったら、局所変数とのバランスが大事ですね。まあ、細かい最適化が趣味の人(お、俺だけか？)には、一応参考になるんじゃないでしょうか。でも、クドいようですが、こういう最適化は、実際に動作時間を計って比べられるのでなければ、理屈だけで高速化しようとしても、実際はどうなっているかわかりません。普通は大きな差はでないので、コードを読みやすく、保守しやすくするのが最優先ですね。コードサイズを小さくしたいとか、無駄にメモリー領域を取らない、とかいうことならいいんですが。
ちなみに、
ObjPtrのnumbersを、もう初めからForth風アレイにして、
: item@ ( ^array idx -- val ) inline{ cells + @} ;
: item! ( val ^array idx -- ) inline{ cells + !} ;
とでも定義してat:とto:に代えれば(語順は変わりますが)、もっと速くなるかもしれません(試してない)。
再追記
少し保守化しまして(^^;;)、標準的なForth流に書き換えてみました。ついでに、局所変数を使っていた?Exchangeの定義も、局所変数なしにします。これで、標準的なForthでも動くコードになるはずです。って、はじめのWil Badenさんのコードは標準Forthで動くものだったはずなわけですが。
変更するワードだけ書きます。ってか、(qsort)を除いて全ワード書き直しですが。初めにある、
ObjPtr Numbersの宣言を、アレイの宣言に変えます。
10000 CONSTANT ArraySize
Create numbers Arraysize Cells Allot
一応、1万アイテムということで。で、アイテムの取り出し変更用の補助ワードを書きます。
: to:numbers cells numbers + ! ;
: at:numbers cells numbers + @ ;
インライン展開した方が速いかもしれませんね(またそれかよ(~ ~;;)。PowerMopsでは、
: to:numbers inline{ cells numbers + !} ;
: at:numbers inline{ cells numbers + @} ;
標準Forthでは、
: to:numbers S" cells numbers + !" evaluate ; immediate
: at:numbers S" cells numbers + @" evaluate ; immediate
とします。
次は、?Exchangeを局所変数なしで書き直します。
: ?Exchange ( l-idx r-idx -- l-idx r-idx )
2dup = ?EXIT
2dup swap at:numbers swap at:numbers \ l-val r-val
2dup <= if 2drop exit then
>r ( l r lv ) ( R: rv ) over ( l r lv r ) to:numbers ( l r )
over r> ( l r l rv ) swap to:numbers ;
スタックの途中経過も所々書いてみました。括弧書きはコードとしては要りません。
Partitionの変更は単純で、セレクタとオブジェクトの間の空白を取り除くだけです。ま、そういう風に仕組んだんですけど。
: partition ( l r -- l1 r1 l2 r2 )
2dup + 2/ at:numbers >r ( r: -- pivot )
2dup
begin
swap begin dup at:numbers r@ ( pivot ) < while 1+ repeat
swap begin r@ ( pivot ) over at:numbers < while 1- repeat
2dup <= if ?Exchange swap 1+ swap 1- then
2dup >
until
r> drop \ throw pivot away
swap rot ;
で、最後に、qsortを適応させましょう。
: qsort ( -- ) 0 ArraySize 1- (qsort) ;
まあ、これだけです。あと、テスト用に乱数を生成してリストに格納したいですね。乱数生成関数もForthで組んでもいいんですが、簡単に降順、つまり、大きい順に並んだリストで試すという方法もあります。例えば、
: SetArray ArraySize 0 do Arraysize i - i to:numbers loop ;
これで、降順のリストを生成し、qsortして、ちゃんと昇順(小さい順)に並び変わっているか確かめればいいわけです。
ちなみに、Carbon MacForthのデモ版で動作は確認しました(てへへ)。格納／取り出しワードのインライン化の効果は、MacForthデモ版ではあまり大きくありませんでした(4から5%程度の高速化)が、PowerMopsでは大きく効きました(50%弱の改善)。多分、PowerMopsの方がアグレッシブに最適化してるのが表面化してくる、とか、そんな感じかな。
ええ、さらに注意です。
インライン定義はコードを呼出し先に埋め込んで、呼出しのためのコードを端折ることで高速化を図るんですが、Mopsマニュアルによると、コードは短いものであること、頻繁に呼び出されるものであること、を前提としていると書いてあります。実際、改行を入れることはできません。特殊な機構なので、あまり無闇に使うと、コードが大きくなるし、予想外の結果になったりすることもありえます。まあ、程々にですね、使いましょう。値の取り出し格納といくつかの
四則演算くらいかなあ。ま、よほど特殊な条件があるか、ナノセカンドマニアででもない限り、インラインとかはあまり考えても意味ないです、はい。
最終更新：2019年09月21日 09:14
