- 1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ]
- データ構造とアルゴリズムに関する総合スレ。
【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
toro.2ch.net/test/read.cgi/tech/1217773415/
- 643 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:47:44.20 ]
- >>641
ハッシュでバケットを C++ 実装してるだけだよ
map 使ってるから、厳密にはハッシュじゃないけど
ideone.com/XdtCMM
見たんだよね？
- 644 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:55:38.84 ]
- mapだとO(n log n)になってしまうぞい
- 645 名前：610 mailto:sage [2013/02/03(日) 20:06:53.31 ]
- >>643
> 見たんだよね？
いや、ideone.com/XdtCMM でググっても何も出なくて、
ideone.com でググったら、どうもコード投稿サービスみたいな感じだから、
そこで XdtCMM を調べれば良いのかと思って [search] ボタンを探したが無くて、
諦めた。
>>634 の方法で時間を計ったら、qsort より 1.5 倍遅かった。
俺は >>619 で set（unordered_multiset）を使ってやったが、map の方が速かったのか。
あと今更すまん、>>619 は unordered_set って言ったけど unordered_multiset の間違い。
- 646 名前：610 mailto:sage [2013/02/03(日) 20:16:14.46 ]
- >>613
map を inordered_map に換えてみたら、qsort より6倍以上速くなった！
あとは、要素の型にどうやって汎用性を持たせるかだ。
qsort は void* の要素と型のサイズを引数に取る汎用関数なんで。
qsort みたいに要素１個につき1バイトずつ while でコピーする方法でやっても、
なお qsort より速くできるか・・・やってみるわ。
- 647 名前：610 mailto:sage [2013/02/03(日) 20:17:25.42 ]
- >>646
ごめん、アンカーミスった
>>643 ね
- 648 名前：610 mailto:sage [2013/02/03(日) 20:18:56.60 ]
- >>640
連投すまん
map を unordered_map に換えてみたら、です
ちょっと興奮を冷ますわ
- 649 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 20:30:18.30 ]
- >>644
それはわかってるけど、考え方の具体例を示しただけだから
STL なんだからコンテナ変えるだけでhash_map (標準ではないかな)でもなんでも試せるじゃん？
>>648
おめ！
君の努力と探求心の賜物だね
- 650 名前：610 mailto:sage [2013/02/03(日) 20:31:59.19 ]
- void* 使った汎用化は面倒なんで、関数テンプレートにしたわ。
>>611
正直ハッシュは本当にできるか疑ってたが、できてしまったな。
ごめんね。
しかし set と違って map クソ速いな。
どこで差が出るのかちょっと興味出てきた。
- 651 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 20:45:47.82 ]
- unordered_multisetよりunordered_multimapが速いとかかなり衝撃的
何が違うんだ・・・
- 652 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 20:52:21.18 ]
- >>651
コード晒した方が回答付きやすいぞ
コンテナに問題があるかもしれないが、使い方に問題がある場合が圧倒的だよ
- 653 名前：610 mailto:sage [2013/02/03(日) 21:02:28.84 ]
- >>651
unordered_multiset と unordered_map の比較ね。
たぶん、multiset に挿入するのと map に挿入するのは同じだと思うんだ。
同じハッシュ関数や比較関数、アロケータを使ってるから。
違うのは、set に対して multi の機能を加えている部分ではないかと。
今ちょっと別のことやっててソースをまだ見てないから
間違ってるかもしれんが、multiset に「同じ値」を挿入すると、
そのタイミングで「同値要素格納用メモリ」がそのツリーノードに
確保されるのではないか。
というのも、コンストラクタでハッシュテーブルの
スロットの最低数は指定できるが、マルチ特有の設定項目がない。
あと、俺が >>619 でやったのは、ハッシュテーブルから取り出す値の数も、
最初の要素数と同じだ。
でも、>>634 のはヒストグラムだから、取り出す処理は
理論上はグループ数だけ。
（別の言い方をすればツリーのノードはグループ数だけ）
要素数に対してグループ数が少ないほど、こちらの方が速い。
>>626 の意味が今更分かったw
あとは、自分で unordered_multiset らのソースを眺めてみるよ。
みんな今までありがと。
たいへん勉強になったよ。
- 654 名前：610 mailto:sage [2013/02/03(日) 21:13:13.45 ]
- 俺、すげーバカだった。
ヒストグラム法じゃダメじゃん。
例えば要素の型が、
struct Himawari {
int value;
int id;
};
で、value でしか比較しない場合、グループ化後、
同じグループの要素の id が全て同じになってしまう。
要素がint型とかfloat型とか、そういう単純な値ならいいけど。
- 655 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 21:46:02.02 ]
- >>654
実はそのケースもあると思ってた
でも、ちょびっと工夫するだけで結構楽にできると思うよ
- 656 名前：610 mailto:sage [2013/02/03(日) 22:03:30.43 ]
- じゃあ、ちょびっと熟考してみる。
- 657 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 22:30:08.32 ]
- バケツソートで数を数えるのではなく
テーブルに突っ込んでいけばいいのだが
ハッシュ＝値そのものなハッシュテーブルと同じなのよねやってる事は
- 658 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:22:01.97 ]
- 要素数100万の配列をc++のstd::sortでソートすると
10秒ぐらいかかっちゃうんだけどこれって異常に遅いよね・・・
ちなみに要素の型はpair< long long, long long >なんだけど、
なにが問題なのか誰か分かる？
- 659 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:26:09.16 ]
- コピー発生してる？
- 660 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:35:04.67 ]
- 比較関数が遅いとか。
- 661 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 16:45:11.08 ]
- うーむむ・・ためしにint配列でやったら２秒ぐらいだった
というか、蟻本の巨大ナップサック(p148)をそのまま写して、
最大のn=40でやってみたら10秒以上かかったけどいいのかなー
どうやらソートに時間かかってんなーって感じなのよ
こればっかりは自分の処理系？だけじゃなんともいえんのか・・・
- 662 名前：デフォルトの名無しさん [2013/02/04(月) 18:41:17.92 ]
- 環境も何もかかずにいったい何がしたいのか。
- 663 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 20:11:22.72 ]
- コピーが遅いんだろ
- 664 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 22:20:18.86 ]
- 最適化有効にしてる？
- 665 名前：661 mailto:sage [2013/02/04(月) 23:53:21.67 ]
- いやーすまぬ
Releaseにしてビルドしたらすごく速くなったわ
こんなに速度変わるとは
- 666 名前：デフォルトの名無しさん mailto:sage [2013/02/04(月) 23:57:54.34 ]
- ・・・
- 667 名前：デフォルトの名無しさん mailto:sage [2013/02/05(火) 00:24:44.09 ]
- 原因を解決したらもっと速くなりそうだな
- 668 名前：デフォルトの名無しさん mailto:sage [2013/02/05(火) 12:24:00.31 ]
- 色々酷いな
- 669 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 09:40:59.22 ]
- 結果報告しただけでもマシ
- 670 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 19:32:31.26 ]
- 2のべき乗の和で、例えば7は1+2+4で構成されてますが、
7から1,2,4が使われてると判定する良い方法はありますか?
- 671 名前： ◆QZaw55cn4c mailto:sage [2013/02/06(水) 19:34:59.98 ]
- >>670
繰り返し 2 で割りまくって余りをみていくしかないのでは？
- 672 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 19:38:43.95 ]
- >>670
16進数で論理演算したら？
- 673 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:09:47.71 ]
- >>670
& で1ビットずつ判定していけば
- 674 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:30:25.87 ]
- 値がdoubleかも知れないし
- 675 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:37:47.12 ]
- 整数にキャストすればいいだけ
- 676 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 20:38:52.35 ]
- 判定した値を何に使うかで違ってくると思う
例えばforeachに突っ込むなら判定処理は先延ばしにした方がいいだろうし
- 677 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 21:24:33.20 ]
- >>670
J言語だとこんなふう
(#2^i.@#)#:7
1 2 4
(#2^i.@#)#:1234
1 8 16 64 512
- 678 名前：デフォルトの名無しさん mailto:sage [2013/02/06(水) 22:04:58.56 ]
- J言語の書き込みなんて初めて見た
- 679 名前：670 mailto:sage [2013/02/07(木) 03:55:23.45 ]
- ビット演算で
2の0乗&7、2の1乗&7...で判定できるのですが、この方法だと3の冪乗1 3 9 27...のときに同じ方式が使えないですよね。
どう考えれば良いのでしょうか。。
- 680 名前：デフォルトの名無しさん mailto:sage [2013/02/07(木) 04:04:00.14 ]
- >>679
>>671
- 681 名前：デフォルトの名無しさん mailto:sage [2013/02/07(木) 07:17:09.20 ]
- まさか10進数の表示を自前でできないってことはないよね？
3進数はその10を3に変えればいいだけ
- 682 名前：デフォルトの名無しさん [2013/02/07(木) 08:40:46.92 ]
- >>670 >>679
ここに 3 のベキ乗でも通用する良質の答えがある
toro.2ch.net/test/read.cgi/tech/1358572977/31-
|
 |
