13/02/03 14:47:22.77
>>618
いや、だから、「ソートアルゴリズムを使えば O(n log n) でできる」と
>>610 に書いたんだが。
あと、結果のリストから同値があるものを探すのは今回は必要ないです。
あくまで目的（出力）は同値な要素が必ず隣同士にあるリスト。
>>617
たしかに O(n log n) よりもひとつ速いとなると O(n) しかないね。
ハッシュの方は試しに、要素の型を int に限定して、
std::unordered_set<int> を使ってやってみた。
残りのテンプレート引数はデフォルトで。
単純に、配列の要素を順に unordered_set に insert してから、
イテレータで順に取り出して元の配列に代入した。
配列の要素数は 10000000 個で、rand () % 3000 の値を入れた。
コンパイラは g++ (tdm64-1) 4.7.1 で、最適化オプションは O3。
qsort 関数は1秒で終わったが、ハッシュの方は15秒かかった。
話にならんかった。
やっぱ楽しないで、自分でハッシュ関数やアロケータを作って
テンプレート引数に入れるべきか・・・
俺の直感では単純なソートよりも条件は緩いはずなのに、
ソートと同程度のソートではないアルゴリズムが思いつかないのは意外だ。