こんにちは。
（Visual C++ 6.0/MFC 使用）
長文失礼します。
CListCtrl::SortItems()について、どんなソートアルゴリズムを使用しているか推測で
きる方がおられればお教えください。
リストコントロールに数万件のアイテムを追加してソート（昇順／降順）を行っている
のですが、数万件ともなると結構時間が掛かる（10秒くらい）ので、なんとか高速化で
きないかと考えております。
当初は各サブアイテム（数列程度）の内容全てを文字列としてInsertItem/SetItemして
おりましたが、さすがにこれでは（ソートではなく）リストへの追加自体が時間が掛か
りすぎるためオーナードローに変更し、LPARAMのみをInsertItemすることで高速化しま
した（データ本体は既に別のところ－ドキュメントクラスに存在します）。
さらに高速化できないかと思い、オーナーデータに変更しました。
以外にも（？）オーナーデータにするまえから2万件のLPARAMの追加は2秒程度で完了し
ておりましたので、あまり高速化はできませんでした。とはいえ、0.2秒程度になったの
で10倍の高速化ではあります。（非オーナーデータはもっと遅いと思っていました）
オーナーデータにすることによって、CListCtrl::SortItems()が使えなくなりましたの
で自前で実装したのですが、クイックソートでも元もとのオーナーデータ SortItems()
の倍くらい掛かることがわかりました。
クイックソート以上のソートアルゴリズムを知らないので困ったのですが、方法を変え
ることでSortItems()に大分近い速度を出せるようになりました。
保持しているオーナーデータをソートするのではなく、そのオーナーデータを別の領域
に二分探索で並べ替え（というよりは新たに配列を作るという言い方になるでしょう
か）ることで実現したのですが、二分探索挿入ですと元もとの並べ替え前のデータの並
び方によって比較関数呼び出し回数がかなり変わってきます（状況によって10倍くらい
変わる）。
そこで、再びオーナードロー／CListCtrl::SortItems()に戻し、ユーザ定義の比較関数
の呼び出し回数を調べたのですが、SortItems()の場合はソート前のデータの並び方に関
わらず、比較回数がかなり一定で安定しています。
ためしに 150行の SortItems()で確認すると、ほぼ800回近辺の比較回数なのです。
これはいったいどんなソートアルゴリズムなのでしょうか．．．
ちなみに、オーナーデータにしてクイックソートで自前でソートすると、大体SortItems
()の倍くらい比較関数が呼び出されます。
当方アルゴリズム自体に詳しいわけではなく、WEB で調べてなんとか実装しているとい
う状態なので、どんなアルゴリズムなのか皆目見当がつきません。
状況からこのアルゴリズムではないかと推測可能な識者の方がおられましたら是非お教
え頂けると幸いです。
なお、上の例において、比較関数は全く同じものを使っていますので比較関数によるソ
ートの時間差は発生していません。CPU キャッシュのヒット率は無視ですが。
比較関数の呼び出し回数がほぼそのままソート時間に比例しています。
多少は手を加えているかもしれませんが、クイックソートだと思いますよ。
それより倍も早いアルゴリズムがあればもっと知られていると思います。
自前で実装したクイックソートのコードを示してみてはどうでしょうか？
こうすれば早くなるといったアドバイスがもらえるかも。
無駄に再帰してるとか比較してるってのはありがち。
>リストコントロールに数万件のアイテムを追加してソート（昇順／降順）を行っている
のですが、数万件ともなると結構時間が掛かる（10秒くらい）ので、なんとか高速化で
きないかと考えております。
追加するアイテムがあるのであれば、InsertItem/SetItemする前にソートしていく方法は
駄目ですか？
# STLとか使用すれば、自前でソートするよりも早いかと思いますが。。
クイックソートは（既にソート済みなど）データの並びが最悪の場合O(n^2)となってしま
い、決して「常に最速」のソートアルゴリズムではありません。
SortItem()の実装はわかりませんが、例えばqsort()などはある程度対象となる要素数が
少なくなってきた場合は挿入ソートを用いるなどして、高速化をはかっていたはずです。
また、マージソートなどもクイックソートと同じくO(n log n)で高速なソートアルゴリズ
ムです。
また、メモリに余裕があるのなら、ソート済みデータをあらかじめ用意しておくというの
もひとつの手だと思います。
アドバイスありがとうございます。
qsortを忘れてたのでqsortに置き換えて実験してみました。
...なんでqsortを全く意識していなかったかわかりました。LPARAMにあたるユーザ定義の
値を引数に取れないからですね。
クラスに閉じ込めようとするとLPARAM部分をstaticにしなくてはならないのが嫌だったた
めでした。
ちなみに、実際はテンプレートクラス内でソートを行っているのですが、上記LPARAMに当
たる変数をstaticにする場合、あちこちからこのファイルがインクルードされているため
そのヘッダファイル内でテンプレートクラスの静的変数の実体を定義すると多重定義にな
ってしまいます。脱線してしまいますが、テンプレートクラスのstatic変数はどこに書け
ばいいのでしょうね．．．今回は別のcppファイルに書きましたが。
よくよくMSDNを見てるとqsort_sなんてありますね。Visual C++ 6.0では使えなそうな気
がしますけど。
話を戻します。
qsort では、私が自前で作成したソートと変わりません。CListCtrl::SortItems()が異様
に速いようです。
内部的にいろいろと複合技を使っているのかもしれません。
250アイテムのソートですが、結果の一例です。もちろん条件によって変わりますが、ほ
ぼ同じ条件から同じ条件へのソートを行った際の比較関数呼び出し回数です。傾向的には
このような感じです。
プロポーショナルフォントになると表示が崩れているかもしれません。
qsort SortItems
1列目 1877 1315
2列目 2098 1512
3列目 2500 1600
4列目 2394 1386
5列目 1996 1297
6列目 2158 1198
7列目 2311 1425
8列目 2680 1458
前回倍くらい違うと申し上げたのは言いすぎですが、倍近いものもあります、という意味
です。
ここまでの結果だけ見ると、SortItems()がやたら速いということになります。
CListCtrl::SortItems()が何か細工しているような気がします。私の頭ではわかりません
が何らかの大小比較キャッシュのようなものでも持っているのですかね。
テンプレートクラスのstatic変数をヘッダファイルに書いて多重定義になるのはコンパイ
ラ（VC++6）のせいじゃないですかね。
VC++8は大丈夫でした。
参考：
http://ml.tietew.jp/cppll/cppll/thread_articles/8420
通りすがりさん。
ありがとうございます。Visual C++ 6.0だからですね。
新しいSDKも追加できないのでXPやVistaからの機能を使おうとすると自前でGUIDや定数
を定義したりで大変です。
Visual Studio 2008も出たことですのでそろそろ潮時ですね。
また、標題の件については、CRTのqsortでもSortItemsにかなわないと言うことで、リス
トコントール内でかなり特殊な実装がされているものと理解しました。
そこまではデバッガで追いかけられませんので、こういうものだということにして本件
クローズさせていただこうと思います。
ご意見頂いた皆様、誠にありがとうございました。
返信する
最新の投稿: お久しぶりです、いかがお過ごしでしょうか。 最新のメンバー: gantez 最近の投稿 未読の投稿
