ソートロジック大会

[omasu]

　お世話になります。

ａｒさん
　早速の対応ありがとうございます。


　私も動的（静的？）な確保にチャレンジをしておりました。
しかし、このレベルのコードは、手直しに失敗すると愛機がすぐ迷宮入りしてしまう
危険な領域であることを実感しております。

　マティさんやイグトランスさんのコードのように、
あらかじめ最大ソート件数を定義（Ｃｏｎｓｔ）しておき、領域（配列）を確保
データを取り込む際に、データ件数を取得し、ソート領域を指定する、
　そのように変更したかったのですが、私の実力では、まだまだのようです。
（実際ソート処理をする場合は、大まかな件数はわかっていても、正確に何件かはわからないため。）


ａｒさんのコード本体を利用し、シェル４を組み込み実行してみました。
　実行時間が１０万件で７．７２１秒から１．５２２秒と格段に早くなりました。
　恐れ入りました。m(_ _)m

　構造体に大変興味が湧いてきました。これから勉強してみます。

追伸：ａｒさんの「マージソート　その２」について
　　　実行時間の測定のために１００万件の入力データを固定し、そのうち何件をソートするか入力する。
　　　斬新なアイデアに感銘しております。
　　　実行時間比較では件数に対応した入力ファイル名をいちいち直し、コンパイルしていました。

　　　Ｉｎｐｕｔ文の入力の変わりに、データカウントで代用するという手段も考えていますが、
　　　今後の実用的な処理にするために、私が挫折中の静的確保についてもご尽力いただければ幸いです。

追伸２：私の環境だと５０万件までのソートはできるのですが、
　　　　常駐ファイルを全て落とし、メモリーを掃除した後だと、時間が計れます。
　　　　しかし、いったんディスクがカサカサし始めると、とたんに時間がかかり、計測失敗となります。
　　　　実行時間の安定性のため、１０万件までとしています。
　　　　ａｒさんの１００万件の使用メモリが２３ＭＢということ（動的な確保の場合）
　　　　一段と速度が速くなっていることから、５０万件の復活の可能性があるかもしれません。

[omasu]

お世話になります。

　ａｒさんの深い考えに今頃気づきました。
　対応済みだったのですね
　（しかも動的に）（メモリも最小）

Input "record number =?",nをコメントアウト

If n<1 Or n>rcd_max Then n=rcd_maxをコメントアウト
を
n=rcd_maxにしました。
　そのままデータ件数を実行できました。

　ありがとうございます。

[河川屋]

10/12の記事で気になったのがあるので２言。

＞安定性を求める場合はマージ？（データのならびに左右されない？）。
安定性を、
データの並びが変わってもソート時間一定
の意味で使っているようですが、安定性の意味が違います。
・同値のデータがあった場合、元の順序が保持される
というのが安定なソートで、そうならないのが不安定なソートです。
たとえば、１桁の整数
３１４一５９２を並べ換えると、
９５４３２一１となります（１と一は元の位置確認のための区別。）が、
このとき、１一となる保証があるのが安定なソート。
ただし、データに細工をする（元の要素番号を覚えておき、同値なら要素番号で判定する）といった方法はとらないものとして
安定かどうかを見ます。
単純挿入、バブル、マージは安定、選択、シェル、ヒープ、クイックは不安定。

＞トーナメント法　推定で何個も作成、なぜか単純選択法になってしまう。
これは、最初に優勝者を決めたときに、「誰とと誰が対戦しどちらが勝ったか」
を情報として保存する必要があります。保存する方法は、例えば２分木。
２位決めは、保存したデータを使って対戦済データを端折ります。
ヒープソートも、対戦方法を覚えておくやりかたの１つで、親ノードと子ノード
の関係がそのまま勝敗になるようにデータを入れ替えていき、ヒープが完成した
時点で優勝者および対戦表が完成しているのと等価です。

で、２分木を使ったソートというのも実在します。
（ヒープソートと二分木ソートは、全くの別もの。）
これは、
・データを足していく途中でもデータを検索する必要がある場合
　（例えば、文章中の単語の種類と数のカウント。同じ単語は登録しない。）
に用いられます。
具体例はこちら。
http://www.rs.kagu.sut.ac.jp/~infoserv/index.html
平成１１年度秋期第２種情報処理試験午後問７。（Ｃ言語、再帰あり）

大まかな動きは、
既存データの右に大きいデータを、左に小さいデータをブラ下げていく。
ブラ下げ終わったら、木をたどってデータを取り出す
（というか、Indexの作り方はこちらが普通の方法であり、順位をIndexにするほうが用途としては特殊。）
であり、トーナメント法式ではないです。

処理時間はｎlogｎだから、クイックやヒープと同等のオーダーのソート法ですが、
既ソート済／逆順データに対してはボロボロになります。

[omasu]

お世話になります

　久々のありがたいご意見番（失礼しました）の登場に感謝をしております。

当初の考えはそのとおりです。

過去ログにおいて
　時間: 2005年09月24日(土) 20
　題名: ありがとうございます。
　マージ=安定性を求める場合はマージ？（キーが同一の場合、最初のデータが先にくる？　ｆｉｆｏ）
という記述をしていたのですが、

皆様のありがたい討論の中に
　時間: 2005年09月29日(木) 02
　題名:なし
　＞クイックソートは速いアルゴリズムで非常に美しいですが、
　＞安定じゃないのだけが欠点ですね。
　クイックソートは、「n^2の時間がかかる数列が存在する」というのが最大の欠点

という記述により、
　マージ=安定性を求める場合はマージ？（データのならびに左右されない？）。
というように考え方が変わってしまいました。

申し訳ありません。

　もう少し、考え方をを皆様に確認をするよう、改めます。

トーナメント法、ヒープ、２分木も勉強していきます。
相対編成ファイルや、直接編成ファイルの概念も使っていこうと思います（シノニムに注意）

[ar]

標記の件、C言語アルゴリズム辞典より写してみました。
データの入出力などは、以前投稿のマージソートのコードを流用してください。
その際、以下の点変更願います。
　　1)　work = New [ELM(n) \ 2 + 1] CSVSORT　→　work = New [ELM(n)] CSVSORT
　　2)　mergesort_str(0, n - 1, data)　→　radixsort(n, 10, data, work)
　　3)　出力ファイル名、Print文などでmergeと記載されているところ

パフォーマンスは比較文字数と件数に比例するので、今回の10文字程度の比較なら相当速いみたいです。
手元の環境で、マージソートの半分近い時間で終了しています。
ただし、確保する配列数が増えるのでメモリの消費量は増えます(100万件時で約31MBでした)。
また、lstrcmp()を用いた比較と異なる順序を与えるので注意が必要です。

コード: 全て選択

'ラディックスソート
'	n		: データ数
'	length	: データの文字長
'	a		: データ配列(0～n-1)
'	work	: 展開用配列(0～n-1)
Sub radixsort(n As Long, length As Long, a As *CSVSORT, work As *CSVSORT)
	Const UCHAR_MAX = 255
	Dim i As Long
	Dim j As Long
	Dim count[UCHAR_MAX] As Long

	j = length - 1
	Do
		'count配列を初期化
		i = 0
		Do
			count = 0
			i = i + 1
		Loop Until i > UCHAR_MAX
		'
		i = 0
		Do
			count[a.keystr[j]] = count[a.keystr[j]] + 1
			i = i + 1
		Loop While i < n
		'
		i = 1
		Do
			count = count + count
			i = i + 1
		Loop Until i > UCHAR_MAX
		'
		i = n - 1
		Do
			count[a.keystr[j]] = count[a.keystr[j]] - 1
			work[count[a.keystr[j]]].keystr = a.keystr
			work[count[a[i].keystr[j]]].info = a[i].info
			i = i - 1
		Loop Until i < 0
		'
		i = 0
		Do
			a[i].keystr = work[i].keystr
			a[i].info = work[i].info
			i = i + 1
		Loop While i < n

		j = j - 1
	Loop Until j < 0
End Sub

[omasu]

>ラディクスソートの件
> 手元の環境で、マージソートの半分近い時間で終了しています。
> ただし、確保する配列数が増えるのでメモリの消費量は増えます(100万件時で約31MBでした)。

ありがとうございます！(~O~)。早速実行してみます。

今までＺｇｏｃｋさんの情報を受けるまで聞いたことのないソートでした。

　今、BytePtr型が、なぜ４文字なのか悩んでいます。

　バケツソート文字列版も作成途中ですが、（あれこれやりすぎて脳みそスタック不足）（◎！◎）
　「頭から１文字ずつバケツ化していく」、それと類似をしているのでしょうか？
　そうであればかなわないかな？
　やはりバケツは「プライマリーキーの数字で、なおかつ範囲が限られている場合」だと一番早い。
　［１から１０００の単一の数値をばらばらにし、それをソートする場合等」１パスでソート完了！
　作成中バケツの問題点として頭の数文字が全て同じ場合に無駄な時間を費やす事でしょうか、
　また、キーが全て同一の場合は、よくわかりませんが。

実用的ソートロジックを将来構想として、キー列指定他、
　可変長文字列化、外部パラメータ指定など(どこから？)、
　いろいろな、構想をしていきたいと思います。

　他の、どの言語よりすばらしくなること
　アクティブベーシックの継承資産となれば幸いとおもっています。

[omasu]

お世話になります。

　ａｒさんのラディックスソートの実行結果について
　どこまで行くのか実行速度　(o!o)・・・(ｳﾙﾄﾗﾏﾝﾃﾞﾊﾅｲﾃﾞｽ)

近況報告：
　ソートキーをハッシングを使ってテーブルにセットすることに失敗しました。
　１０桁の文字キーを数値化すると３０桁が必要です。（ＱＷｏｒｄでもだめ）
　それをデータ件数のテーブルに圧縮セットすると、シノニム（コリジョン）が多発
　計算ロジックとコリジョンの回避ロジックに時間を費やし、かえって遅くなりました。

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

追伸：ａｒさんがクイックソートを作るとどうなるのでしょうか？

[ar]

残念ながら･･･というより当然ながら劇的に速くはなりません。
クイックソートは代表的なソートアルゴリズムですし、そのソースコードも書籍などで広く紹介されています。たぶん、これまで投稿された方々もそういったものを見て勉強し、コードを組んでいるはずです。当然、私もそうですから、クイックソート自体に差は無いと考えます。実際、投稿したものは「クイックソート改2」に相当しますが、1万件までのソート実行時間が他に比べて特に速いということはありません。ただし、5万件以降のソート時間には差が出てきます。これはどちらかというと、キー比較の仕方とかスワップ関係などアルゴリズム以外の要因が絡んでいるのではないでしょうか？

追伸1
クイックから挿入法への閾値（THRESHOLD）は、10～15くらいが最速でした。

追伸2
私が引用元にしていたのは、「C言語による最新アルゴリズム事典」（奥村晴彦著　技術評論社）です。
これはソースコードだけなら筆者のHPもしくはvectorで公開されているはずです。
BASICに慣れた身ではC言語の読み下しに骨が折れましたが、それだけの価値はあると思います。
もしユーザー参加型のプロジェクトができるようになったら、これのActiveBasicへの移植を提案したいですね。

コード: 全て選択

'work配列いりません
'quicksort_str(ELM(n), data)で実行してください

'クイックソート(スタック配列使用)
'	n : 添え字の最大値
'	a : 配列のポインタ
Const THRESHOLD = 10			'挿入ソートに切り替える境界値
Const STACKSIZE = 32			'たかだか Long のビット数程度(>log2Nの数であること)

Sub quicksort_str(n As Long, a As *CSVSORT)
	Dim i As Long
	Dim j As Long
	Dim left As Long
	Dim right As Long
	Dim middle As Long
	Dim p As Long
	Dim leftstack[STACKSIZE] As Long
	Dim rightstack[STACKSIZE] As Long
	Dim x As CSVSORT					'中間値
	Dim tmp As CSVSORT					'入れ替え用

	left = 0
	right = n
	p = 0
	While 1
		If right - left <= THRESHOLD Then
			If p = 0 Then Exit While
			p = p - 1
			left = leftstack[p]
			right = rightstack[p]
		End If
		middle = (left + right) \ 2			'(first + last) / 2
		x.keystr = a[middle].keystr	
		x.info = a[middle].info
		i = left
		j = right
		While 1
			While lstrcmp(a.keystr, x.keystr) < 0
				i = i + 1
			Wend
			While lstrcmp(x.keystr, a[j].keystr) < 0
				j = j - 1
			Wend
			If i >= j Then Exit While
			tmp.keystr = a.keystr
			tmp.info = a.info
			a.keystr = a[j].keystr
			a.info = a[j].info
			a[j].keystr = tmp.keystr
			a[j].info = tmp.info
			i = i + 1
			j = j - 1
		Wend
		If i - left > right - j Then
			If i - left > THRESHOLD Then
				leftstack[p] = left
				rightstack[p] = i - 1
				p = p + 1
			End If
			left = j + 1
		Else
			If right - j > THRESHOLD Then
				leftstack[p] = j + 1
				rightstack[p] = right
				p = p + 1
			End If
			right = i - 1
		End If
	Wend
	inssort_str(n, a)
End Sub

'挿入ソート
'	n : 添え字の最大値
'	a : 配列のポインタ
Sub inssort_str(n As Long, a As *CSVSORT)
	Dim i As Long
	Dim j As Long
	Dim x As CSVSORT
	i = 1
	Do
		x.keystr = a.keystr
		x.info = a.info
		j = i - 1
		While j >= 0
			If lstrcmp(a[j].keystr, x.keystr) <= 0 Then Exit While
			a[j + 1].keystr = a[j].keystr
			a[j + 1].info = a[j].info
			j = j - 1
		Wend
		a[j + 1].keystr = x.keystr
		a[j + 1].info = x.info
		i = i + 1
	Loop Until i > n
End Sub

[zgock]

私の発言のtypoと言い間違いから混乱をさせたようで申し訳ありません。
ラディックスソートについてもヒントを出した程度で、
実装はarさんにおまかせする格好になってしまいました。

ご指摘のとおりヒープソートは「安定したソート」ではありません。
言いたかったのは
「データ内容による速度のばらつきがクイックソートほど極端ではない」
という点でした。

今回のようにソートキーが固定長でかつ短い場合、
ラディックスは有効だろうなと思いましたが、
ここまで差が出るとは思いませんでした。

ラディックスはキーの長さが速度に単純比例しますから、
キーの長さが現在の１０倍を越えるとクイックと逆転すると思います。

バケツほどではないですが、ワークを大量に使用しますので、
ワークが確保できる程度の件数で、かつキーの長さが有限：ラディックス
ワークが確保できない程度で、キーの長さが有限：マージ等
キーの長さが長いか不定：クイック等比較系ソート
という使い分けをするといいのかな、と感じました。

#奥村先生の「アルゴリズム辞典」は名著だと思います。
#（最初のPascal版、Ｃ版、最新のJava版と全部持ってますｗ）

[omasu]

お世話になります。

ｚｇｏｃｋさん、ありがとうございます。
　私の勝手な判断と、このような丁寧なメッセージに恐縮しております。
　もっといろいろなロジックがあるぞと、示唆していただければ幸いです。

ａｒさん、ありがとうございます。
　クイックソートを実行してみました。（まだまだ、コード全体がないと苦労しますが(^ ^;)
　私がまだ未到達なクイックソート、劇的なスピードアップもかなり期待してしまいました。(^ ^)なぜ？！
　解明にはまだまだ時間がかかりそうです。申し訳ありません。

コームソートもしっかり学習しました。
　もっと早いコームロジックを模索中です。（完成度が高く、早くする場所がない？）(_ _)（突っ込まれるかな）

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

コームソートロジック（ノーマル）のコードも掲示します。
母体はイグトランスさんのコードです。
　イグトランスさんの美しく、解りやすい（私にはまだまだ難しい）、高度なロジックを愛用しています。

[ここをクリックすると内容が表示されます]

[omasu]

お世話になります。

コームソートの模索により、すこし早くなりました。

　クシ（コーム）関心するネーミングがやっと理解できました。
　最初は荒いクシですき、次は少し細かいクシですき

コームソートのギャップの減らし方を例のごとく、１万件のソートを３千回実施、
　最速値は１３．８５５～１４．１６４でした。

　単純にギャップの減らし方を、件数を１．３で割る→件数を１．４で割るに変更すればすこし早くなると考えます。

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

追伸：コームソートは何かの委員会にて１．３という最速値を決定したのでしょうか？
　　　アクティブベーシックのみ１．４が早いのでしょうか？Ｃは、ＶＢは、？

[omasu]

お世話になります。

　処理速度はどんどん速くなっておりますが、(o!o) ｳﾙﾄﾗﾏﾝﾃﾞﾊｱﾘﾏｾﾝ
　　作成速度はどんどん遅くなっております。(v!v) ﾊﾞﾙﾀﾝｾｲｼﾞﾝﾃﾞﾓｱﾘﾏｾﾝ

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

①．シェルソート（ノーマル）　　シェルソートのノーマル速度がないので作成しました。
　　２で割るのか、３で割るのが正規か、解りません。

[ここをクリックすると内容が表示されます]

②．シェルソート（ノーマル・再帰）　　初めて作った再帰処理です。
　　シェルを再帰で作ってもあまり意味がなかったようです。
　　しかし、ノーマルとは逆の作りになるとは思いませんでした。

[ここをクリックすると内容が表示されます]

③．マージソート（非再帰・非ワーク）　　非再帰・非ワークにチャレンジ。
　　１万件までは早いのに５万件を超えると急に遅くなります。
　　改修の必要性を感じます。

[ここをクリックすると内容が表示されます]

④．マージソート（ａｒさん版）　　ａｒさんのコードをソートロジック大会の実行速度比較環境に移植しました。
　　さすがのロジック速度には恐れ入ります。

[ここをクリックすると内容が表示されます]

追伸：イグトランスさんのコードがいつの日か早くなっているようです。
　　　（環境・条件・コード等、ただいま追求しています。）

[イグトランス]

ところで，図書館でアルゴリズムの本を借りて読んでいたところ，
ソートの話が出てきて，クイックソートも当然出てきました。
というわけでそれを参考にして新たに作っています。

今しばらくお待ちください。
入出力は完成しましたが，肝心のソートが未だバグありで動きません。

[河川屋]

omasuさんへ

以下のシェル法プログラムは間違っています。

Sub Sort(ByVal S As Long,ByVal E As Long)
　　Dim Bunkatu As Long
'　Bunkatu=E '間違い
　 Bunkatu=(E-S+1)\2 '正しい　(Sの値が１以外をとってよいものとみなす。)
　　Do
　　　 Bunkatu=Bunkatu\2
'　　　For i=S+Bunkatu To E Step Bunkatu　'間違い(これではシェル法の本領を発揮できず、遅い。)
　　　　For i=S+Bunkatu To E　'正しい
　　　　　 j=i
　　　　　 While j>=S+Bunkatu And _
　　　　　　　 lstrcmp(KeyTable[Index[j]],KeyTable[Index[j-Bunkatu]])<0
　　　　　　　　 Swap(Index[j],Index[j-Bunkatu])
　　　　　　　　 j=j-Bunkatu
　　　　　 Wend
　　　 Next i
　　Loop Until Bunkatu=1
End Sub

または、
　　Do
　　　Bunkatu=Bunkatu\2
　　　For k=0 To Bunkatu-1
　　　　For j=k+Bunkatu To E Step Bunkatu
と、ループのネストを１段深くする。
（こうする意味は特に無いですが、これでも可。）


こういうところを間違えると、 Bunkatuの数列をどう設定するか、など、まるで関係なくなってしまいます。


で、コムソートについての私の意見ですが、
・コムソートとバブルソートベースのシェル法は実質１行しか違わない
（下記において、 LOOP WHILE....のほうの１行が決定的な違い。）
　　　SUB SHELL(X(),N)
　　　IGAP=N
　　　DO WHILE IGAP>1
　　　　IGAP=IGAP/2　　 'shell
　　　' IGAP=IGAP/1.3　 'comb
　　　　IMAX=N-IGAP
　　　　DO
　　　　　IEX=0
　　　　　FOR I=1 TO IMAX
　　　　　　IPULUSG=I+IGAP
　　　　　　IF X(I)<=X(IPULUSG) THEN
　　　　　　　W=X(I) : X(I)=X(IPULUSG) : X(IPULUSG)=W
　　　　　　　IEX=1
　　　　　　 END IF
　　　　　NEXT
　　　　LOOP WHILE IEX=1　　　　　　　'shell
　　　' LOOP WHILE IGAP=1 AND IEX=1　 'comb
　　　LOOP
　　　END SUB
ということまでは既に書いたよね？
つまり、IGAPに対し完全にソートしてからIGAPを小さくするのがシェル法、
ソート不完全なうちにIGAPを小さくするのがコムソート。
（だからといって、コムソートのほうが効率が悪いとも言い切れないが。）

加えて、
・初出は米国Byte誌の1991年4月号。

これは要注意であって、欧米の場合かなりマジメな雑誌でも、エイプリルフールである
場合を考えないとなんない。
つまり、作者は、何もかも承知の上でひっかけようとしている可能性のあるといういこと。
で、ひっかけでなくマジメな記事だとしても、シェル法との差が無さ過ぎるから、
NlogNの性能まではいくら何でも出そうにないです。

[omasu]

お世話になります。

　河川屋さんの確実なご指摘、ご指導に感謝しております。
　シェルソートノーマルについて、確かに不具合がありました。
　とんだ、エイプリルフールをしてしまいました。
　申し訳ありません。

　実行テストおよび、実行時間で気づくべきでした。

　コムとシェルの違いのレッスンも理解できました。

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

　シェルソートのロジックの見直しを行いました。

①．シェルソート（ノーマル）　　　河川屋さん校正版 [ここをクリックすると内容が表示されます]

②．改シェル法（クヌース大先生）　河川屋さん [ここをクリックすると内容が表示されます]

③．シェル２（クヌース大大先生） [ここをクリックすると内容が表示されます]

④．シェル３（０．８９７５＋￥３） [ここをクリックすると内容が表示されます]

⑤．シェル４（０．８９７５＋０．４５） [ここをクリックすると内容が表示されます]

追伸：イグトランスさんの新ロジック、心待ちにしております！。