- 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/
- 623 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 16:27:15.88 ]
- >>622
んー、ソートは大小比較だけが唯一の条件じゃん？
でも、>>610 って、移動位置も条件になってね？
- 624 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 17:36:06.87 ]
- ハッシュがかなりぶつかってないのかなあ
デフォルトのハッシュってどんなもんなんだろ
- 625 名前：610 mailto:sage [2013/02/03(日) 17:54:08.19 ]
- >>623
位置移動って、どういうこと？
ソートだって移動処理を伴うと思うが、そういうことではない？
同値な要素が隣同士にあれば、どのような順番でもいいけど。
ソートは小さい方から順に並べないといけなくない？
- 626 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:05:42.28 ]
- >>625
順番かんけいないの？
であれば、個数をカウントするだけでいいな
多分O(n)で行ける
ってか、順番あってもカウントで行けるな
- 627 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:06:50.81 ]
- あっ、そうすると結局ハッシュか
- 628 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:07:56.28 ]
- >>625
ま、俺の勘違いっぽいので忘れて下さい
すまんです
- 629 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:36:21.33 ]
- >>619
618なんだが、QuickSortを使うのではなくそのアルゴリズムを使うって話
QuickSortのアルゴリズムのキモの部分は、Pivotを決めてそれより大きいか小さいかでPivotの左右に振り分ける
それを改良して、Pivotを同値がある数値にし、Compareを＝のみ真にして、真なら隣とスワップとする
同値が複数ある場合に備えて、1つスワップしたら、そのスワップする位置が内に1つずつズレていく
そのPivotを同値のある物にしなければならないから検索が必要になるってこと
要素に入っている数値全てに対して行なってもいいけど総当りになるから検索したほうがいいかなってこと
例えば、3, 5, 2, 3, 5, 2, 5, 2, 1なら
同値のある5を右端とスワップして、そのプログラムに通すと
3, 2, 3, 2, 1, 5, 5, 5ってなる
さらに3, 2, 3, 2, 1の部分を抜き出して左端に3を持っていきプログラムに通すと
2, 2, 1, 3, 3ってなる、2の場合も同じ
最終的に、1, 2, 2, 3, 3, 5, 5, 5ってなる、ソートされている状態だけど
3から始めたら、1, 2, 2, 5, 5, 5, 3, 3ってなる
QuickSortのアルゴリズム部分を改良したら行けるんじゃないか？って話
- 630 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:37:24.80 ]
- 要素のサイズが大きいとハッシュテーブルの方が有利になったりしないかな
あと、ハッシュテーブルのメモリ確保部分は工夫した方が良さそう
- 631 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 18:59:07.38 ]
- 検索なしでもいけるかも
フローを書くと
１）要素の最初の数値を左端に持っていきPivotとする
２）先頭から順番にPivotと比較して、＝ならPivotの隣とスワップする
３）Pivot位置をそのスワップしたものに移動する
４）要素全て調べたらPivot位置を１つ左にズラして、１）に戻る
こんな感じかな
- 632 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:06:26.24 ]
- 連投すまん
単純に考えて最大O(n/2)で済むように思う
詳しい人あってる？
あ、書き忘れてた
Pivot位置が２番目に来たらループ抜ける
- 633 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:12:36.63 ]
- ああ違うわ
O(n^2)だわ…
ソートしたほうが早いな…
- 634 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:16:41.44 ]
- これでよくね？
ideone.com/XdtCMM
- 635 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:18:28.48 ]
- バケツソートは既出だっつーの！
- 636 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:30:12.09 ]
- ソートと違って、保存先へのポインタが必要だから、バケツより速くするのは無理な気がするぞ。
- 637 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:31:16.34 ]
- バケツソートでなく
・データの1個目と同じデータの数を求め、配列（）に保存
・その過程で検索したデータも削除して元データスリム化 （不要？）
・データエンドまで繰り返し
・あとは求めたデータと数の配列から順に書き起こして終わり
データの移動をせず、答えを改めて記述する点がキモ
- 638 名前：610 mailto:sage [2013/02/03(日) 19:35:05.13 ]
- >>629 >>631-633
じつは俺も左に集めていく方法で速いのがないか色々試してた。
最初に提案されてからハッシュテーブルの実装をしばらく渋ってたのはそのせい。
でも、どう考えても O(n^2) のしかできなかった。
まぁ、久しぶりに脳をフル稼働した気分だし、
自分的には失敗しても得るものはあった。
ところで、ソートより速いハッシュテーブルでの実装が現実的に可能か謎だ。
データを木構造で持ってたら、要素ひとつの挿入に O(log n) かかって、
それが要素数分必要だから、結局 O(n log n) になる。
これより速くするなら木構造ではなく配列で持つ必要があるけど、
要素の型やグループ数などに汎用性を持たせようとすると、メモリ量が見積もれんな・・・
- 639 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:35:16.19 ]
- あぁ
データエンドまででないな
重複をパスしてかつ求めた数の総量＝元データ数になったら終わり
- 640 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:36:45.82 ]
- >>637
>>634
- 641 名前：610 mailto:sage [2013/02/03(日) 19:40:49.33 ]
- >>634
どういう意味かもう少し説明しほしいです。
ググってみたけど、今回のことにどう関係するのかよく分からなかった。
- 642 名前：デフォルトの名無しさん mailto:sage [2013/02/03(日) 19:46:10.70 ]
- >>641
どの数字がいくつあったか統計を取るということ。
- 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-
|
 |
