V.B.に特化した文字列の整列方法と整列方法の自動選択

小さくはない配列の整列で
通常法（本来の名称忘却） http://oshiete1.goo.ne.jp/kotaeru.php3?q=209365内回答 No3
for k=j to i を For k=j+1 to iに変更
クイックソート http://www.ne.jp/asahi/protech/hiroaki/programin …
シェルソート http://www5d.biglobe.ne.jp/~tomoya03/shtml/algor …
ループ変数を倍精度整数型に，配列を文字配列に，変数名を自分の使っている命名法に
再帰参照回数を減らすように，末尾も含めて整列されるように変更
文字列を SortDt$(N&)=Str$(Rnd(1)) で指定し
富士通 FMV Diskpower S3 20 (Win 95+VB6.0(V.S), 購入直後の状態)で実行した結果，
約30秒間(V.B. Timer関数で測定)で，クイックソート，シェルソート，通常法で実行可能回数が
Visual Basic 6.0 SP3 コンパイラ
n&=3 208943, 209490, 248245
n&=10 114149, 138935, 215415
n&=30 47967, 39833, 163284
n&=100 14118, 8353, 83524
n&=300 3913, 2064, 30516
n&=1000 987, 414, 9750
n&=3000 281, 105, 3348
n&=10000 68, 21, 947
となり，大型コンピューター(Fotran)で過去に経験しているクイックソート，シェルソートの利点を得られませんでした。
又，上記表はn&が対数目盛でほぼ等間隔になるように選択しました。n&に対する整列時間の変化が過去に報告されている内容とは異なります。したがって，整列に関する過去の経験は使えません。
大型コンピューターでは，クイックソートよりも早い整列方法が発表される等の研究が進んでいます。
おそらく Visual Basic 6.0 用に特化した整列方法があるかと思いますが，ご存知の方いらっしゃいませんか。
整列方法の自動選択(Win95で表示ルーチンの自動選択をマイクロソフトで行なっていましたから)を考えています。
関係情報をご存知の方いらっしゃいませんか。

No.1 回答者： you-m 回答日時： 2004/03/20 00:21

上述のクイックソートアルゴリズムは再帰呼び出しタイプのため、VBでは充分な性能を発揮できていない可能性があるかもしれません。

10年ほど前に、VB2でソート関数を作ったことがありましたが、再帰呼び出しのクイックソート関数だと、あっという間にスタックオーバーフローで実行時エラーになってしまったので、参考URLにあるようなロジックで再帰呼び出しをしないように実装したことがあります。
すでにそのときのVBのソースはなくなってしまいましたが、参考URLを参考にすれば、VB版を作るのは、容易かと思います。

参考URL：http://www.geocities.co.jp/SiliconValley-SanJose …

この回答へのお礼

JavaもCも最近(Fotranを覚えてから)発表された言語なのでご紹介をうけたサイトの内容は文法がわからず理解できませんでした。
5番の方の内容から.再起参照を行わないように変更しました。
Win95(FMV S3 20)での速度は.質問文に書いた速度より2－3割遅いという結果になりました。
なお.MS-Basic(MS-DOS 6.20, ペンテ200MHZ, 配列宣言の制限から1-300個で比較)では.クイックソート同士の比較では2-3割早いという結果になりました。

お礼日時：2004/03/25 00:04

No.2 回答者： tsukasa-12r 回答日時： 2004/03/20 12:26

＞大型コンピューターでは，クイックソートよりも早い整列方法が発表される等の研究が進んでいます。

なんだかよくわからないんですが、ソートのアルゴリズムは大型コンピュータとかＰＣとか、そういったこととは関係ないと思うんですけど・・・。だから、大型コンピュータでクイックソートよりも速いソートアルゴリズムがあったのなら、それはＰＣでも同じなんじゃないでしょうか。
ただ、ソートアルゴリズムの実装方法としては、大型コンピュータには大型コンピュータ用の方法があるでしょうし、ＰＣでは大型コンピュータのようにできないことはあると思います。
実験結果でクイックソートがシェルソートに比べて遅くなっているのも、きっと実装方法の問題だと思います。#1 の方のおっしゃるように再起呼び出しをしない方法にすれば、より速くなると思います。

あと、
＞整列方法の自動選択(Win95で表示ルーチンの自動選択をマイクロソフトで行なっていましたから)を考えています。
↑この辺り、意味が理解できません・・・。

この回答への補足

＞意味が理解できません・・・。
3番4番の方が指摘している内容です。速度がデータ数の２乗に増加する通常の方法と.これよりも増加が遅い方法があり.最高の速度を得るにはこれらを切り替える必要があります。
また.ある程度以上の配列を作成した場合にスワップが発生します。スワップを最小することが高速化につながりますので.使用可能メモリーにより使用する配列の大きさを変更して分割ソートに切り替える必要があります。いずれにしろ、Windowsでは2GB, 8.4GB, 32GB, 120GB, 倍精度整数の壁がありますので分割ソートは必要になります。あるいは、ヒープソートのような一部分しか整列しないという方法が必要になるかもしれません。

再起呼出をまったくしない方法で試しましたが.２－３割遅くなりました。

＞ＰＣでは大型コンピュータのようにできないことはあると思います。
このあたりの内容を知りたくて質問しました。

補足日時：2004/03/25 00:36

No.3 回答者： imogasi 回答日時： 2004/03/20 16:36

雑感。

ＯＫＷＥＢで論じれるようなレベルでなく、もっと複雑な難しい問題では。
>小さくはない配列の整列
「配列」と言うからには、データはメモリにあって、ディスクＩ／Ｏは使ってないでしょうね。メモリに初期データがセットされてソートが終わるまでを測っているでしょね。
そもそもソートにおいて、メモリの配列のソート部分は、ソート全体の一部であって、メモリの少なかった昔は完了総時間に占める割合は特に低かったと思う。メモリがメガ単位になろうとする今も、やはりその点はあると思う。
使っていないと思っても、配列もサイズや要素数が多いと
一時的にディスクに情報を退避させたりしてるかもしれないです。リソースの多寡が影響するとするとスピードを決める要素が複雑になります。
大型機のソートプログラムはレコードのディスクＩ／Ｏを含めて考えないといけない場合が多い。特に科学計算以外は。
○大型機はＴＳＯ、マルチタスクなどになっており、処理プライオリティ指定などもあって、そのソートだけの作業時間なども正確に測れていますか。
○コンパイル済みのソートユティリティを使う大型機と
インタプリタなどのパソコン言語と一緒に比べてませんか。
○＞大型コンピューターでは，クイックソートよりも早い整列方法が発表される等の研究が進んでいます。
それは何と言う方法ですか。クイックソートが早いと言うのは、学理（数学）的に比較回数の少なさから言われているもので、それ以上のアルゴリズムが見つかったら、特許ものではないですか。不勉強な私ですが聞いたことはない。いろいろディスクやデータ並びの性格なども組み合わせてベストミックスの方法は日夜研究されていると思いますが。
○データのソートキーのクセによっては、クイックソートより早く終わるアルゴリズムもあるでしょう。
データの偏りを十分吟味しないで、一回のテストで、ソートアルゴリズムのスピードを論じるのは無理があると思いませんか。
○配列のソートではＡ．比較Ｂ.データのメモリ内移動Ｃ．演算等を使いますが、マシン語レベルで機械によってはどれが早いか差があるはずです。ソートアルゴリズムはそのどれを多用するかにより差が出るはず。
○文字列キーソートと数値ソート（特に１０進か浮動か）について機械によって得意（早い）が差があるはずですが。

この回答へのお礼

いろいろご感想ありがとうございます。
1.時間計測については、同時に複数のタスクを実行しなければ割込み作業中（割込みが発生した事による他のタスクに切り替わるまでの時間。大体３０クロック程度）の時間を含めてしまうという問題がありますが.ほぼ正確な時間を得られています。時間帯や優先度を変えて（少なくとも4人のオペレーターの比較をしています）実行していますので、大型における測定方法には間違いがないはずです。私の測定はその限りにありませんが（複数のタスクを同時に実行した結果、Ｎ＝10のソートに１時間かかるというとんでもない結果を出した実績があります。単に金曜日の夕方に月曜日の朝までかかるであろう計算を全部一度に仕掛けただけです）。
2.パソコン(FM7, Pc-9801)でも大型でもミニコン(Unix)でも比較しています。これは大型で得られた結果を多機種でも応用しようということで調べました。
3.名称はおぼえていません。「新しい方法が出たよ。今度調べるから」としか聞いていませんから。なお、この方法の有効性が示されるのは数１０万程度の整列の場合であり、パソコンではメモリーが足らないでしょう。
4.ご指摘の通り癖がありますので、初期値を変えて行っています。質問文には省略しましたが、間の数も調べていますので、多少値がずれるかもしれませんが傾向は変わらないです。
5.ご指摘の通り機械語レベルや比較対象の違いでは差があるでしょう。ですから、VBに特化した方法が知りたいと思ったわけです。

少なくとも、万人単位でVBプログラマーの方々がいらっしゃいます。私のような、素人（ソートプログラムを自分で書けなくて検索し探してきたような人間です）よりは皆様が詳しいでしょう。

ディスクアクセスの問題についてはご指摘の通りです。したがって、メモリーに負担をかけない程度（次第に数を増やして行くと傾向が変化しますので見当つきます）の大きさを求めるという作業を現在行っています。大きな問題としての分割ソート・マージルーチンは完成しています（作業用補助記憶装置の分割もできないことではありません）ので、この境界をどのように決定して行くかが、現在抱えている問題です。メモリー分断による暴走という問題も多分控えているでしょう。

お礼日時：2004/03/21 00:54

No.4 回答者： tsukasa-12r 回答日時： 2004/03/20 18:06

http://www.ne.jp/asahi/protech/hiroaki/programin …
の関数で実際にやってみようとしたら、実行時エラーになってしまいました。（配列のインデックスが -1 になっていた。）
というわけで、
http://www5d.biglobe.ne.jp/~tomoya03/shtml/algor …
の関数をつかってやってみましたら、再起呼び出しでも全然遅くありませんでした。

Dim strData() As String
Dim strWork() As String
Dim dtStart As Date
Dim dtEnd As Date

Call GenerateData(lngCount, strData)

dtStart = Now
For i = 1 To lngRepeat
　　strWork = strData
　　Call BubbleSort(strWork)
Next i
dtEnd = Now
Debug.Print "Bubble Sort : N = "; lngCount & " : " & DateDiff("s", dtStart, dtEnd) / lngRepeat

のような感じで
Pentium3 730Mhz メモリ384MB Access2000 の VBA でやってみましたら

　　　　N=100　N=300　N=1000　N=3000　N=10000
--------------------------------------------------------
Bubble　　0.007　　 0.06　　 0.7　　　6.4　　　74
Shell　　　0.0018　　0.007　 0.032　　0.12　　 0.6
Quick　　 0.0011　　0.0043　0.018　　0.06　　0.24

のようになりました。
おおよそ、
Bubble : N^2
Shell : N*LogN
Quick : N*LogN
のオーダーになっているようです。

結論としては
http://www.ne.jp/asahi/protech/hiroaki/programin …
の関数が何かおかしいようです。

この回答への補足

ご指摘のサイトの内容から、再度行いました。結果として.
質問文のクイックソートよりも1-2割遅い。
「何かおかしい」点は移植時に変更されている(<=, >= を <, >に)ので、私の結果では現れなかった。
となりました。
MS-Basic(Ms-dos6.20, ペンテ200MHZ, 配列宣言の制限から1-300個で比較)では、回答にあったような速度変化が観察されました。ですから.ソフト作成における間違いはないかと思います。
Win95に関係した何かがあるように思われます。

補足日時：2004/03/25 00:05

この回答へのお礼

つたない私のソフト作成に皆様のご助力をいただきありがとうございました。

現在主流となっているであろうNET系ソートルーチンの作成につきましては他の質問にあるようにクイックソート等の利点が使えるようです。また回答いただきました皆様の手法が私の環境では使えないという結果が得られました。
VB+Win95に特化したルーチンをご存知の方がいらっしゃるかも知れないと思いひたすら待ちました。
しかし質問後半年以上過ぎた12月になっても追加の回答がありませんでした。
Visual Basic + Windows 95の環境下では高速化を可能とする手法をご存知の方がいらっしゃらないということがわかりました。

通常法で数百程度のデータ数ですと十分高速です。ディスクキャッシュが効いている状態では外部記憶装置の影響をほとんど考慮する必要がないようです。通常法+外部配列+ファイルマージという手法で乗り切ることにしました。

お礼日時：2004/12/07 00:31