アルゴリズムオタク

アルゴリズムオタク at TECH

966:デフォルトの名無しさん
08/08/18 01:27:24
STLのpartial_sortの計算時間って、要素数N、ソートする要素数をKとするとNlogKらしいんだけどなんでそうなるの？
URLﾘﾝｸ(stdcxx.apache.org)

967:デフォルトの名無しさん
08/08/18 01:37:51
std::partial_sortって確か内部的にヒープソートを使ってたはず。

968:デフォルトの名無しさん
08/08/18 01:40:14
要素数kのheap作成がO(K)で、その後(N-K)要素をpush/popするのに
一回あたりO(logK)というだけ？

969:デフォルトの名無しさん
08/08/18 01:43:49
最悪の場合な。だから保証されている。
heap木を壊さないために必要。

970:デフォルトの名無しさん
08/08/18 01:44:00
Wikipediaのselection algorithmsのとこに載ってる、O(N+klogk)の変形quicksortの方が速そうだけど、
わざわざヒープを使ってるのには何か理由があるのかなぁ？
URLﾘﾝｸ(en.wikipedia.org)

971:デフォルトの名無しさん
08/08/18 01:46:18
> heap木を壊さないため

どういうこと?

972:デフォルトの名無しさん
08/08/18 01:47:38
理由はよくわからないが歴史的な経緯により
sort()はクイックソート、stable_sort()にはマージソート、
partial_sortにはヒープソートを使っていると「C++標準ライブラリ」には書いてある。

973:デフォルトの名無しさん
08/08/18 01:48:27
>>971
ヒープソートについてぐぐってみ。
正確にはO(log2N)必要。O記法によりO(logN)になってるだけ。

974:デフォルトの名無しさん
08/08/18 01:51:38
調べてみたらpartial_sort()の目的にヒープソートが合っているかららしい。
クイックソートは途中でソート処理を打ち切るのは困難であるが、
ヒープソートは容易であるのでpartial_sort()の用途に合っている。

975:デフォルトの名無しさん
08/08/18 01:53:03
stable_sortにquickやheapが使えないのはアルゴリズムの性質上そのとおりだと思うけど、安定であることが求められて以内partial_sortにquickが使えないのは納得できないなー。

976:デフォルトの名無しさん
08/08/18 01:55:11
>>974
資料希望。>>970には真逆のことが書いてあるわけで。

977:デフォルトの名無しさん
08/08/18 01:59:42
悔しければC++標準化委員会に入れば？

978:デフォルトの名無しさん
08/08/18 02:03:47
そうする。

979:デフォルトの名無しさん
08/08/18 02:05:08
まあ無理だと思うけど。

980:デフォルトの名無しさん
08/08/18 02:14:42
Wikipediaに書いてあるアルゴリズムは、STLのnth_elementとsortを組み合わせれば、自分でコード書かなくても使えることが分かった。
URLﾘﾝｸ(wordaligned.org)

この記事と同じように速度測ってみて、使い分けることにするわ。スレ違いっぽいのでこのへんで。

981:デフォルトの名無しさん
08/08/20 03:25:02
次スレは？

982:デフォルトの名無しさん
08/08/20 09:59:55
/* ギャップバッファ
URLﾘﾝｸ(haiku.mine.nu)
これの、GapBuffer_GetRealPosition()関数の戻り値が何を意味しているのかわかりません。

983:デフォルトの名無しさん
08/08/20 11:01:12
age

984:デフォルトの名無しさん
08/08/20 11:47:53
ギャップバッファー上のバイト位置から、
データとしての先頭からのバイト位置を計算。

return i - (this->end - this->start);
あたりの間違いだろうな。

985:デフォルトの名無しさん
08/08/20 22:42:01
>>384
すみませんが、よくわかりません。
if(i < this->gap_start)
return i - (this->gap_end - this->gap_start)
else
って事ですか？

986:デフォルトの名無しさん
08/08/20 22:51:02
初心者スレ行け