HOME Open Source
データ量が多くなると、検索処理に非常に時間がかかってしまい、ユーザは非常にストレスを感じてしまいます。そういったストレスを少しでも改善するための、一つの例として、クイックソートと二分木探索を利用したデータ検索のサンプルを公開したいと思います。内容は、10000件の個人情報のサンプルデータを検索するサンプルプログラムとなっています。このソースに添付している個人データは、個人情報テストデータジェネレーターにより、作成したサンプルデータです。サンプルデータに含まれる個人名などの情報は、実在の人物とはまったく関係ございませんので、あしからず。
ソースコードは、Microsoft社の製品 エクセル向けに書いたものなので、利用するには、ご使用のコンピュータに、エクセルがインストールされていることが、必須条件です。
以下は、サンプル画面です。
クイックソートと二分木探索の実装で、通常のFor文による検索処理に比べると随分パフォーマンスは改善されたと思いますが、もう少し、パフォーマンスを改善するすべがあります。それは、データのインデックス化という考え方です。理解できる方は、インデックス化により、更にパフォーマンスの改善を行ってみるのも良いかと思います。
Config設定のサンプルでFor文によるソート処理を実装していますが、今回のサンプルでは、この方式よりも高速にソート処理が行える、クイックソートという方式を採用しています。クイックソートの処理内容については、少し複雑で理解し難いところがあるかと思いますので、できるだけ分かりやすく、簡単に説明してみたいと思います。(ソースとにらめっこしているよりは、分かりやすいと思います。)
以下が、クイックソート(MstSortPersonalInfo関数)の実装例ですが、
Private Function MstSortPersonalInfo( _
ByRef recs() As StructPersonalInfo, _
ByVal lft As Long, _
ByVal rgt As Long) As Long
Dim p_axis As Long
If lft < rgt Then
'軸に採用した値の位置が返却される。
p_axis = MstQckSortPartition(recs, lft, rgt) '①
'軸に採用した値の、左側を本関数を再帰的に呼び出しソート。
MstSortPersonalInfo recs, lft, p_axis - 1 '②
'軸に採用した値の、右側を本関数を再帰的に呼び出しソート。
MstSortPersonalInfo recs, p_axis, rgt '③
End If
End Function
MstSortPersonalInfo関数の処理内容について簡単に説明すると、以下となります。
①のMstQckSortPartition関数は、軸となる値を決定し、その値がデータの中でどの位置に配置されるかが決定します。
②は、①で決定した軸となった値の左側を、MstSortPersonalInfo関数の再帰呼び出しによりソートします。
③は、①で決定した軸となった値の右側を、MstSortPersonalInfo関数の再帰呼び出しによりソートします。
これでは、処理内容が少し抽象的すぎるので、もう少し、具体的に説明したものが以下となります。
全部で7個のデータが存在し、説明には、軸をランダムに決定する仕様を採用しています。
①の処理に該当するのが、以下の1～4の手順、②と③の処理に該当するのが、5となります。
軸の決定方法については、中間値などを採用している方なども多くいらっしゃるようですが、結論から言うと、どの値を軸に採用しても、ソートは正しくなされるはずです。極端に言うとランダムに決定しても問題なくソートは処理されます。現実的には、いずれかの軸を選ぶことでソートが完了するまでの、速度に差がでることになるとは思いますが、どれを選べば一番効率が良いかを算出することは、難しいと思います(データの並びなどに依存)。なので、余計な演算を実行して軸の値を決定するよりも、私の場合は、常に左端の値を軸に採用(値を代入するだけ)するように実装しています。
作者は、本ソフトウェアの使用または使用不能から生じるコンピュータの故障、情報の消失、その他あらゆる直接的及び間接的被害に関して一切の責任を負いません。
ご使用にあたり、改善の要望、不具合の発生等ありましたら、画面下のアドレスまで、ご連絡頂きますよう、宜しくお願いいたします。ご面倒、ご不便をお掛けしますが、宜しくお願いいたします。
