[SML 7132] 並び替えの致命傷

[AOKI Atsushi]

ＳＲＡ先端技術研究所青木です。

先ほど、じゅんのメーリングリストにポストした内容を、ＳＭＬへ
も出すことにしました。参考にしていただければ幸いです。アホな
Smalltalker が育ちませんように。

------------------------------------------------------------
R2D2 (AOKI Atsushi)        http://www.sra.co.jp/people/aoki/


青木です。

集まりの並び替えの際に、注意しなければならないことを書きます。
たとえば、次のような簡単なプログラムを例にして説明しましょう。
ある配列を、順序のある集まりへ、と移し替えるものです。

| anArray aCollection |
anArray := #(0 9 1 8 2 7 3 6 4 5).
aCollection := OrderedCollection new.
anArray do: [:each | aCollection add: each].
^aCollection
==> OrderedCollection (0 9 1 8 2 7 3 6 4 5)

移し替える際に、降順（大から小に進む順）にソートしよう（並び
替えよう）として、次のように書くプログラマが多いと思います。
順序のある集まりに換えて、ソートされた集まりを生成し、降順の
ための比較ブロックを指定しておいて、要素を加えてゆくというも
のです。

| anArray aCollection |
anArray := #(0 9 1 8 2 7 3 6 4 5).
aCollection := SortedCollection new.
aCollection sortBlock: [:n1 :n2 | n1 >= n2].
anArray do: [:each | aCollection add: each].
^aCollection
==> SortedCollection (9 8 7 6 5 4 3 2 1 0)

このプログラムコードは、まったく褒められません。VisualWorks
のハイブリッドなクイックソートのアルゴリズムを有効に利用して
いないからです。OrderedCollection を SortedCollection に換え
ればいいじゃん！では済まされないのです。次のように書くべき。

| anArray aCollection |
anArray := #(0 9 1 8 2 7 3 6 4 5).
aCollection := OrderedCollection new.
anArray do: [:each | aCollection add: each].
aCollection := aCollection asSortedCollection: [:n1 :n2 | n1 >= n2].
^aCollection
==> SortedCollection (9 8 7 6 5 4 3 2 1 0)

では、どれぐらいの性能（動作スピード）の差が出るのかを示しま
しょう。乱数ストリームを用いて、１０万個の要素を取り出して、
それらの並び替えに要する時間を、ミリ秒単位で測定してみます。

Time millisecondsToRun: [
	| aStream aCollection |
	aStream := Random new.
	aCollection := SortedCollection new: 100000.
	aCollection sortBlock: [:n1 :n2 | n1 >= n2].
	100000 timesRepeat: [aCollection add: aStream next].
	aCollection]
==> 90665 "←約 90 秒、すなわち、1 分 30 秒だよ！"

Time millisecondsToRun: [
	| aStream aCollection |
	aStream := Random new.
	aCollection := OrderedCollection new: 100000.
	100000 timesRepeat: [aCollection add: aStream next].
	aCollection := aCollection asSortedCollection: [:n1 :n2 | n1 >= n2].
	aCollection]
==> 344 "←たった 0.35 秒"

ご覧のように、とんでもない差となります。計算量は要素数の肩に
かかってくるので、指数関数的に増加するのです。プログラムコー
ドの一行の間違いが、動作性能の致命傷であることを、肝に銘じて
プログラミングをするように！

要素の個数が不定であり、それらを随時、並び替えておかなければ
ならいない、という止むを得ない場合を除いて、アホなコードを書
かないように気をつけましょう。ハイブリッドなクイックソートの
アルゴリズムが有効に働くプログラムコードを作ってくださいまし。

------------------------------------------------------------
R2D2 (AOKI Atsushi)        http://www.sra.co.jp/people/aoki/