09/09/05 19:22:50
>>186
どう再分割するかが問題
狭い範囲にデータが集中しているようなものの場合その再分割を
たとえば値が集中した区画を単純に等分していくなら再帰が一段増える程度では済まんだろ
対象のデータ量の規模が大きいから1段増加するだけでもかなりのロスになる
何かlogNよりも大きい方法と比べているわけでないからlogNのオーダーであることは意味を持たない
結局データの分布を調べないといけないんだが
一度にfloatがとりうる各値の度数を調べるには無理がきかない体だ
確かに分布さえ分かっているのなら分布数え上げソートできなくもないが
何段になるか分からない再帰を行うよりも
オンメモリの範囲で分割して回数の分かっているマージを行う>>187の方が現実的