ソートロジック大会

[マティ]

>私の年はいくつだと思いますか？

N88BASICからの世代と言っていたような気がするのと、ホスト経験者なので、
私と同じ３７才と予想。
（３４～４７才の間には収まると思われます）

あと、余談ですがクイックソート４改は最大ソート件数の制限はありません。
800万件以上の動作検証が面倒くさいのでやめました。
これで、ソート関連の投稿になりますよね！

[omasu]

お世話になります。

　出会いの経験
　　・ポケットコンピュータにてベーシックと出会う
　　・先輩（キキョウ屋）からＺ８０マシン入手　ＲＯＭベーシックと出会う
　　・外付けＦＤＤドライブを入手　ＤＩＳＫベーシックと出会う
　　・ＭＳ－ＤＯＳと出会う
　　・アセンブラと出会う　ハンドアセンブル全盛　Ｚ８０なら１６進数で、ある程度読める書ける、ＩＰＬ等改造して楽しんでいた
　　・マクロアセンブラプログラマーズハンドブックと出会う　マクロアセンブラにはまる
　　・社内でコボルと出会う　仕事でプログラムに携わる　趣味ではやらなくなる
　　・社内で系統が変わる　また、趣味でプログラミングを始める
　　・アクティブベーシックと出会う・・・・・（アクティブベーシック掲示板）

　　出会いはたのしいですね

　そんなわけで２０台前半から始め、２０数年　４６歳のＡＢ初心者です。

追伸：プログラミング関係です。
　　　マティさんの８００万件ソート実行中にｔｅｍｐフォルダを見てください。
　　　何をやっているのか、非常に楽しいことが起こっています。
　　　ずっと見入ってしまいました。
追伸：プログラミング掲示板が質問版になっていました。申し訳ありません。

[omasu]

お世話になります。

　マージソートの構造を理解できました。
　ａｒさんのマージソートを参考に非再帰版を作成しました。
　速度的には追い越すことはできませんでした。

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

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

ヘルプ：河川屋さんのヒープソートが実行できません。
　　　　どなたかご援助をお願いします。（質問版）
　　　　2005年08月26日(金) 22の投稿

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

[河川屋]

>河川屋さんのヒープソートが実行できません。
>どなたかご援助をお願いします。

いちおうコメントしておきます。

Sub Sort(S,E)

こうするということは、Ｓが１以外でも正しく動くことを意味するため、
ヒープソートの場合は特にやめたほうがいいです。
データ開始が０or１以外は意味ないヤヤコシサを持ち込むだけだから考えたくないです。

まず、ヒープとは。
メモリー管理の際のヒープは関係ありません。
ヒープとは、２分木の特殊な形式で、以下の構造をしています。
１．親と子の関係：親をｉとすると、子は、2iおよび2i+1。
　　　（ｉは１から始まるのを前提として。）
２．親子の大小関係：親と子では、親のほうが大きい数値である。
　　　　　　　　　　子の２つ(2i、2i+1)の大小関係は不明。

で、まず、データをヒープになるようにします。
その結果、DAT(1)にはデータの最大値が入ります。
これで最大値が確定したので、DAT(1)とDAT(N)を入れ替える。
次に小さい値は、DAT(2)とDAT(3)のいずれか。
ですが、そうするかわりに、ヒープを再構築する。
といっても、そんなに手間はかからない。
DAT(2)とDAT(3)のうち大きいほうとDAT(1)を入れ替える。
DAT(2)のほうとして、
DAT(4)とDAT(5)のうち大きいほうとDAT(2)を入れ替える。
DAT(4)のほうとして、
DAT(8)とDAT(9)のうち大きいほうとDAT(2)を入れ替える。
以下略。途中で入れ替え不要となれば打ち止め。最悪でも、高々logN回のオーダー。
これでヒープが復活したので、２番目に小さい値が確定。
DAT(1)とDAT(N-1)を入れ替える。
ヒープを再構築する。高々logN回のオーダー。
以下繰り返せばソート終わり。

あ、ヒープを作る話が残っていました。
データの後ろ半分(N\2+1) だけを考えると、子を持たないため、ヒープである。
ここから、データを１つづつ遡り、ヒープを構築する。(親をLとし、ヒープが成り立つよう
下に向かって調整する。このルーチンはヒープ再構築と同じである。)
これを繰り返した結果、i=1まで戻ればヒープ完成。
以上。

' ヒープソート　N88における最も普通の組み方。
L=(N\2)+1 : R=N
WHILE L>1
L=L-1 : GOSUB 3500'SHIFT
WEND
WHILE R>1
SWAP DAT(1),DAT(R)
R=R-1 : GOSUB 3500'SHIFT
WEND
RETURN
3500 '篩い落とし
I=L : J=2*L : X=DAT(L)
IF J<R AND DAT(J)<DAT(J+1) THEN J=J+1
WHILE J<=R AND X<DAT(J)
DAT(I)=DAT(J) : I=J : J=2*J
IF J<R AND DAT(J)<DAT(J+1) THEN J=J+1
WEND
DAT(I)=X
RETURN

[omasu]

お世話になります。

　河川屋さんのご意見に感謝しております。
　ヒープソートはやはり非常に難しいロジックだと思います。
　なかなか動きません。

　マティさんのホームページのヒープロジックもトライをしておりますが、
　やはり難しいです。

　ネットで探し回りＣやＶＢからのコンバートもしておりますが、
　やはり動きません。

　勉強と努力が足りんと自分に言い聞かせております。

　　どなたかソートロジック実行速度比較環境にしていただける方はおられませんでしょうか？（質問版）

追伸：ネットで検索すると「ソートロジック大会」も検索されます。
　　　皆様の貴重なロジックを公開したいと思いますので、検索キーとして記述します。
　　　ベーシック、アクティブベーシック
　　　バブルソート、単純挿入ソート、単純選択ソート、シェーカーソート、
　　　シェルソート、コムソート、コームソート
　　　ヒープソート、トーナメントソート、ラディックスソート
　　　マージソート、クイックソート

[マティ]

oomasuさんご苦労様です。ヒープソートですが、以下のソースで実行可能でしょうか？
（配列のベースが分からなかったので２種類準備しました。）
動作確認を行っていないので、何かあればご連絡下さい。

ヒープソート（０ベース） [ここをクリックすると内容が表示されます]

ヒープソート（１ベース） [ここをクリックすると内容が表示されます]

PS.最近検索を行うと、ここが出る事が多くなってきましたね！

[omasu]

お世話になります。

　マティさんの「スループット」の早さ、
　「ターンアラウンドタイム」にはいつも恐れ入ります。

　実行してみましたが、エラーが発生、実行可能にまでは修正できましたが、ソートされません。
　現在、解析中です。
　どうも、中間変数のタイプのちがいが災いをしているようです。

以下に実行速度比較環境の再提示をいたします。
　もちろんイグトランスさんの母体です。

実行速度環境プログラムの再提示　マージ（非再帰）版 [ここをクリックすると内容が表示されます]

H17.12.17致命的なバグがあります。次の投稿をご利用ください。

[マティ]

配列はゼロベースのようなので、以下の処理でソートできると思います。

ヒープソート（０ベース） [ここをクリックすると内容が表示されます]

確認事項
①.Outputファイルの先頭項目は元データの行番号になっていますよね！
②.キーの作成方法がおかしいと思うのですが･･･
（KeyTableに行データの全体が格納されているように思えます。）
　途中から仕様を変更していませんか？

キーデータの確認方法 [ここをクリックすると内容が表示されます]

[omasu]

お世話になります。

＞確認事項
＞①.Outputファイルの先頭項目は元データの行番号になっていますよね！

　ソートロジック大会発足時から入力データに連番をつけ、出力データの先頭項目に付与しています。
　　ソート後の確認のためにつけた仕様です。

＞②.キーの作成方法がおかしいと思うのですが･･･
＞（KeyTableに行データの全体が格納されているように思えます。）
＞　途中から仕様を変更していませんか？

　マティさんに指摘されるまでとんでもないことを気づかずにいました。
　確かにキーの中にデータ全体が格納されています。
　いつこのようなバグを作りこんだのかは９月２３日以前である事以外、今ではわかりません。

　ロジックを確認したところ、バグは「Function GetKeyPart$」の中に存在していました。

修正後の実行速度比較環境のプログラムを再々投稿いたします。

実行速度環境プログラムの再々提示　マージ（非再帰）版 [ここをクリックすると内容が表示されます]

非表示とはいえ、何度も申し訳ありません。

　しかし、大問題なのは実行時間です。
　　このバグにより、実行時間は４倍ほど多くかかっていたもようです。
　　　全てのロジックを再計測いたしますので、もう少し時間をください。
　　　　申し訳ありませんでした。m(_w_)m

[ar]

だいぶ前に投稿したquicksortをソートロジック大会風にしたものです。といっても、関数名を変えて、基準値の取り方と挿入ソートを投稿物から移しただけというシロモノですが。
実行速度の再計測中とのことなので、せっかくだからやってもらおうかと（＾＾；
昔の実行速度環境プログラムで50万件までは動作確認しましたので動くと思います。ただ、100万件ではバッファの開放か何かでエラーが出ました（きちんと確認していませんが）。

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

記念すべき返信100通目は次の人にプレゼント（笑

[omasu]

申し訳ありません！m(_w_)m
　記念すべき返信100通目を取ってしまいました。！！！ (しかし、「おくゆかしい」方々の存在も考慮しました（笑）

マティさんのありがたいご指摘により、ソートロジック大会の信憑性もランクアップしたおもいです！m(_w_)m

マティさんへ
　ヒープソート実行できました。
　　ありがとうございます。
　　　こんな難しいロジックでありながら、速度的には少し疑問が残ります。

ａｒさんへ
　クイックソートの大会実行速度比較環境移植について
　　ありがとうございます。
　　　［どなたか！］に対する、返信と受け止めます。

大会実行速度実行時間比較について再計測をいたしました。

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

　　今回の比較環境のバグに謝罪をいたします。申し訳ありませんでした。
　皆様のありがたいロジックの速度を正しく提示できなかったことに、深くお詫び申し上げます。

追伸：マティさんの８００万件ソートですが、
　　　高度すぎるため、速度比較から別格の件数比較へと分類をさせていただきました。申し訳ありません。

追伸：１０００件と５０００件の比較は、もういらないような気がします。
　　　あまりにも皆様のコードが早すぎて、速度のむらの［はんちゅう］のようです。

追伸：皆様へ、私のほうが速い、進言およびご指摘ををお願い致します。

備考：返信回数と閲覧回数はいったい何件まで表示可能なのでしょうか?、どの件数で＃＃とかになるのか一瞬、期待してしまいました。m(_ _)m

[omasu]

お世話になります。
　ついにメモリーを増設しました。

増設１ＧＢｙｔｅ、ＰＣを買い換える前に、メモリ増設を！（シャキシャキです。）

実行速度計測に対し、掲示上、１万件からの計測に変更しました。
　　　　　　　　　　計測終了を１０秒以上までとした場合の時間全てが計測できました。

あまりにも鈍足なロジック（ｏｍａｓｕ作）やシェル等重複するロジックを整理しました。

しかし、シェルソートが５０万件以上から実行できなくなっているため、悩んでいます。（質問版）

マティさんのクイック改４は、ａｒさんのメモリーソートが５百万件のため、
　１千万件からとさせていただきました。
　しかし、５千万件以上からエラーとなります、悪戦苦闘です。（質問版）

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

追伸：ＡＢ４．１２．０２のバージョン情報がＡＢ４．１２．０１？

[マティ]

omasuさんごめんなさい、ファイルサイズと取得する処理を手抜きしていました。
前回投稿したプログラムでは、ファイルサイズが２ＧＢまでしか処理出来ませんでした。

コード: 全て選択

'宣言の修正
'   Dim nSize As Long
    Dim nSize As Int64, nSizeLow As DWord    '修正＆追加

'ロジックの修正
'   nSize = GetFileSize( hFileLoad, NULL )
    nSizeLow = GetFileSize( hFileLoad, VarPtr(nSize)+4 )
    nSize = nSize + nSizeLow

これで、実行可能になると思います。

クイックソート改4の改良版も載せておきます [ここをクリックすると内容が表示されます]

PS.テストデータを作成するのに９時間もかかってしまいました。

[omasu]

お世話になります。

　マティさん、ありがとうございます。

クイックソート改４（改０．０７）実行してみました。
　みごと、５千万件（７．７Ｇ）の実行ができました。

ついでに一億件（１５．４Ｇ）も実行しました。（とても「ついで」でなかったのですが m(_w_)m ）

メモリ１．２５Ｇでは［Const xReSort=1024000］まで実行できました。
（一億件実行中、ディスク空き容量２Ｇ・・きわどい！）

テストデータの作成時間ですが、本当に時間がかかりますね！
　１千万件　約　２時間
　５千万件　約１１時間
　１億件　　約２１時間
（テストデータ作成大会ではありません、皆さんは真似をしないでください。）

でも、１万件くらいのブロック単位でファイルアウトすれば早くなるかも、どなたか！

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

追伸：クイックソート改４の基本構造をご教授願えれば幸いです。
追伸：シェルソート全て１０万件までは動くのですが、５０万件から全て実行不可となっています。
　　　タイプはＬｏｎｇですが、その件数で変わるものではないと思いますが、不思議です。
　　　過去のＥｘｉｔ　Ｆｏｒバージョンでは動きます。ただいま、ロジックを見直し中です。

[omasu]

お世話になります。

シェルソート５０万件以上実行不可について

　よくわからないのですが、５０万件の実行には
　シェルソートは［Const TableSize=700000］７０万件の定義が必要と解りました。
　１００万件を規定値とすれば全てのシェルロジックは実行可能です。

過去にハッシング手法を使ったソートが失敗に終わりましたが、

　単純挿入法のロジックで速度更新がありました。
　　このコードは(数値ソートが早い)を利用したものです。

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

(H18.1.5コードをファンクション化しました。)

　今回は亜流のロジック投稿で恐縮しております。
　あらかじめキーテーブルストック時に本コードを埋め込めば、
　クイック（中級編）１００万件で４．１０６秒です。
　ロジック速度測定外ですが、利用価値はあると思われます。

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

(H18.1.5ファンクション化すると少し早くなりました。)