アルゴリズムオタク

952 ：デフォルトの名無しさん：2008/07/01(火) 21:31:45

結局出せなかったか
ゴミめ

953 ：デフォルトの名無しさん：2008/08/03(日) 09:51:46

再帰が好きな人います？

954 ：デフォルトの名無しさん：2008/08/03(日) 13:19:42

好きというより得意

955 ：デフォルトの名無しさん：2008/08/03(日) 16:39:00

>>953
昔 LISP 触ってたから、今でも好きだよ。

956 ：デフォルトの名無しさん：2008/08/03(日) 21:23:51

Ｃでも再帰は普通に使うが

957 ：デフォルトの名無しさん：2008/08/04(月) 08:13:09

loop で考えるよりも再帰の方が考えやすい問題もあるわな

958 ：デフォルトの名無しさん：2008/08/04(月) 08:20:33

例えばフィボナッチ数を求める関数を作るときなんかそうだね。
先ずシンプルな再帰版を作って、次に結果を保存する版を作りたくなる。
その辺りで、どうせ組み込み型の整数では実現できる数が少ないことに気付いてテーブル作って終了w

959 ：デフォルトの名無しさん：2008/08/04(月) 08:36:48

n から m まで加算しろ
と, 言われた場合はループも再帰も不可

960 ：デフォルトの名無しさん：2008/08/04(月) 08:59:07

>>958
フィボナッチって、まずループで作っちゃうけどな。

961 ：デフォルトの名無しさん：2008/08/04(月) 09:11:16

ループも再帰も、単なる実装の問題だからどうでもいい。

962 ：デフォルトの名無しさん：2008/08/04(月) 09:22:54

#if 0 // 再帰
int addFromNtoM(int n, int m)
{
if (n < m) return addFromNtoM(n + 1, m) + n;
return m;
}
#elif 0 // 末尾再帰
int addFromNtoM(int n, int m, int s = 0)
{
if (n < m) return addFromNtoM(n + 1, m, s + n);
return s + m;
}
#elif 0 // ループ
int addFromNtoM(int n, int m)
{
int s = m;
for (; n < m; ++n) s += n;
return s;
}
#else // 要はこれになるからループも再帰も不可と言いたいのかな?
int addFromNtoM(int n, int m)
{
return (m + n) * (m - n + 1) / 2;
}
#endif

963 ：デフォルトの名無しさん：2008/08/04(月) 20:02:57

>>960
そもそもフィボナッチを作ろうと思ったことがない。
再帰の例で使われてるのしか見たことない。

964 ：デフォルトの名無しさん：2008/08/04(月) 23:23:48

>>963
つ 木構造
フィボナッチと置換すれ

965 ：デフォルトの名無しさん：2008/08/18(月) 00:54:15

O(1) (笑)

966 ：デフォルトの名無しさん：2008/08/18(月) 01:27:24

STLのpartial_sortの計算時間って、要素数N、ソートする要素数をKとするとNlogKらしいんだけどなんでそうなるの？
http://stdcxx.apache.org/doc/stdlibref/partial-sort.html

967 ：デフォルトの名無しさん：2008/08/18(月) 01:37:51

std::partial_sortって確か内部的にヒープソートを使ってたはず。

968 ：デフォルトの名無しさん：2008/08/18(月) 01:40:14

要素数kのheap作成がO(K)で、その後(N-K)要素をpush/popするのに
一回あたりO(logK)というだけ？

969 ：デフォルトの名無しさん：2008/08/18(月) 01:43:49

最悪の場合な。だから保証されている。
heap木を壊さないために必要。

970 ：デフォルトの名無しさん：2008/08/18(月) 01:44:00

Wikipediaのselection algorithmsのとこに載ってる、O(N+klogk)の変形quicksortの方が速そうだけど、
わざわざヒープを使ってるのには何か理由があるのかなぁ？
http://en.wikipedia.org/wiki/Selection_algorithm#Optimised_sorting_algorithms

971 ：デフォルトの名無しさん：2008/08/18(月) 01:46:18

> heap木を壊さないため

どういうこと?

972 ：デフォルトの名無しさん：2008/08/18(月) 01:47:38

理由はよくわからないが歴史的な経緯により
sort()はクイックソート、stable_sort()にはマージソート、
partial_sortにはヒープソートを使っていると「C++標準ライブラリ」には書いてある。

973 ：デフォルトの名無しさん：2008/08/18(月) 01:48:27

>>971
ヒープソートについてぐぐってみ。
正確にはO(log2N)必要。O記法によりO(logN)になってるだけ。

974 ：デフォルトの名無しさん：2008/08/18(月) 01:51:38

調べてみたらpartial_sort()の目的にヒープソートが合っているかららしい。
クイックソートは途中でソート処理を打ち切るのは困難であるが、
ヒープソートは容易であるのでpartial_sort()の用途に合っている。

975 ：デフォルトの名無しさん：2008/08/18(月) 01:53:03

stable_sortにquickやheapが使えないのはアルゴリズムの性質上そのとおりだと思うけど、安定であることが求められて以内partial_sortにquickが使えないのは納得できないなー。

976 ：デフォルトの名無しさん：2008/08/18(月) 01:55:11

>>974
資料希望。>>970には真逆のことが書いてあるわけで。

977 ：デフォルトの名無しさん：2008/08/18(月) 01:59:42

悔しければC++標準化委員会に入れば？

978 ：デフォルトの名無しさん：2008/08/18(月) 02:03:47

そうする。

979 ：デフォルトの名無しさん：2008/08/18(月) 02:05:08

まあ無理だと思うけど。

980 ：デフォルトの名無しさん：2008/08/18(月) 02:14:42

Wikipediaに書いてあるアルゴリズムは、STLのnth_elementとsortを組み合わせれば、自分でコード書かなくても使えることが分かった。
http://wordaligned.org/articles/top-ten-percent

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

981 ：デフォルトの名無しさん：2008/08/20(水) 03:25:02

次スレは？

982 ：デフォルトの名無しさん：2008/08/20(水) 09:59:55

/* ギャップバッファ
http://haiku.mine.nu/gapbuffer.zip
これの、GapBuffer_GetRealPosition()関数の戻り値が何を意味しているのかわかりません。

983 ：デフォルトの名無しさん：2008/08/20(水) 11:01:12

age

984 ：デフォルトの名無しさん：2008/08/20(水) 11:47:53

ギャップバッファー上のバイト位置から、
データとしての先頭からのバイト位置を計算。

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

985 ：デフォルトの名無しさん：2008/08/20(水) 22:42:01

>>384
すみませんが、よくわかりません。
if(i < this->gap_start)
return i - (this->gap_end - this->gap_start)
else
って事ですか？

986 ：デフォルトの名無しさん：2008/08/20(水) 22:51:02

初心者スレ行け