仮想リストビューでクイックソート

[戻る]
NOR 2010/08/04(水) 20:41:22
Visual C++ 2008 MFCです。

数千〜数万のデータをリストビューに表示するために、
仮想リストビューを使っており、表示自体は問題無くできています。

このリストビューに、カラムクリックによるソートの機能を持たせました。
ソートの処理はqsort_s()を使い、内部で持っているデータを並び替えています。
これもソート自体は問題無くできているのですが、
同じカラムを2回クリックして降順にソートする際、妙に時間がかかります。
qsort_s()内のコールバックの戻り値を逆にして、
1回目のカラムクリックでいきなり降順にした際には、高速にソートされます。

クイックソートには「ソート済みのものをソートすると遅い」
という弱点があったと記憶しているのですが、これがまさにその例でしょうか?

だとすると、仮想リストビューにカラムクリックのような
昇順降順の入れ替えが繰り返されるソートの動作を持たせる場合、
qsort_s()を使うのはよくないということになってしまうのでしょうか?

かもねぎ 2010/08/04(水) 22:13:51
http://www.kijineko.co.jp/tech/superstitions/qsort.html
こんな記事ありました。

仲澤@失業者 2010/08/05(木) 11:21:05
え〜と、回答ではありませんが、自分の場合、LVS_OWNERDATAを指定する場合は
ついでにLVS_OWNERDRAWFIXEDも指定して自分で表示します。

この場合なら、ソートを実装する場合、昇順のみソートして、
降順が指定された場合には、インデックスの解釈だけを逆にするという
方法がとれるので、降順ソートの実装は不要になります。
当然ですが、スクロールバーの状態を常に監視する必要がありますけどね(vv;)。

NOR 2010/08/05(木) 15:38:31
情報ありがとうございます。

かもねぎさんのリンクにある記事を元に、
qsort_s()をstd::sort()に置き換えてみようかと思っているのですが、
STLはあまり経験が無いので、質問させていただきます。

qsort_s()でソートする際には、contextにカラム番号や昇順降順の情報を持たせ、
コールバック内で比較するメンバや比較方法を分けているのですが、
これをstd::sort()でやろうとすると、どのようになるのでしょうか?

自分で調べてみた限りでは、
bool operator()(elem1, elem2)を持つ「関数オブジェクト」というクラスを作成し、
std::sort()の第3引数にこのクラスを渡し(その際コンストラクタで比較対象を設定)、
operator()の中でメンバ変数を使って比較すればよいと理解したのですが、
それでよろしいでしょうか?

かもねぎ 2010/08/05(木) 16:11:00
http://0xcc.net/blog/archives/000052.html
ここを見る限りでは関数オブジェクト渡しが速いみたいですね。

NOR 2010/08/18(水) 15:15:14
[[解決]]
情報ありがとうございます。
以下のようにqsort_s()をstd::sort()に置き換えてみたところ、
昇順ソート状態のものを降順ソートにする処理も高速になりました。

// CCompareはoperator()(elem1, elem2)を持つクラス
// sortCodeは比較対象のカラムと昇順降順を表す変数
std::sort(m_dataArray.GetData(),
          m_dataArray.GetData() + m_dataArray.GetSize(),
          CCompare(sortCode));

上記の「関数オブジェクト」というクラスでうまく動いているようなので、
解決とさせていただきます。

STLの経験が浅い自分としてはちょっと気持ち悪いですが、
このような使いかたをするのですよね。

std::sort()のアルゴリズムがどのような仕様なのかはわかりませんが、
qsort_s()のアルゴリズムは、リストビューのように
「昇順ソートされているものを降順ソート」するようなケースは
想定されていないということになるのでしょうかね。

古いスレッドには追加発言できません。