＜集大成＞アルゴリズム大辞典

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 321 名前：306 [2007/11/27(火) 15:19:23 ] >>309 だらだらコード書くよりSTL使った方がやりたいことが分かり易いかと。 ﾌｧﾝｸﾀ書くのが億劫で擬似と言っただけです。 対象のデータ構造は特定しません。というかあわよくばデータ構造による差が分かれば尚良いです。…が面倒なのでﾗﾝﾀﾞﾑｱｸｾｽって事いいです。 STLは、書きながら思ったけど本当に突っ込まれるとは思いませんでした。一般に同じ様な実装だと思ってました。すみません。 確認したのはgcc3.4.4/4.2.2、VC8、bcc5.5、SGI3.3です。 >>311 補完ありがとうございます。 >>314 その最速が今揚げてる議題です。 322 名前：デフォルトの名無しさん mailto:sage [2007/11/27(火) 23:05:25 ] >>321 で、コスト設定はどうするの？ 少なくとも「イテレータの移動、比較、スワップ、スワップ」くらいのコスト比を 決めてくれないと、とても定数部分の違いは算定できないと思うんだけど。 現実のCPUみたいなキャッシュや分岐予測があるモデルだと、解析は さらに面倒なことになるけど、それはどれくらい考えないといけないの？ あと、 Bentley-Sedgewick は読んでみた？ 323 名前：デフォルトの名無しさん mailto:sage [2007/12/28(金) 03:47:56 ] うざ 324 名前：デフォルトの名無しさん [2008/03/05(水) 01:18:02 ] みんなアルゴリズムをどんな風に知っていったの？ ライブラリを主に使ってるから、ソート程度しか知らないんだけど、 今日、先輩プログラマにアルゴリズムも知らんのか？と言われた。 325 名前：デフォルトの名無しさん mailto:sage [2008/03/05(水) 02:01:07 ] 書籍 326 名前：デフォルトの名無しさん mailto:sage [2008/03/05(水) 23:39:34 ] アルゴリズムを知っているかどうかは使い捨てプログラマかどうかの目安の一つだな 327 名前：デフォルトの名無しさん [2008/03/06(木) 03:11:28 ] >>325 推奨書籍はありますか？ 328 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 07:54:07 ] 問題が解決出来るかどうか であって、アルゴリズムを知ってるだけじゃ駄目だろ。 アルゴリズムを知ってるだけでは、Fizz-Buzz問題でさえ解けるのは半数なんだそうだ 329 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 07:55:37 ] 奥村さんのアルゴリズム辞典が定番かね。 330 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 09:19:28 ] Introduction to Algorithms(MIT Press) 331 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 09:35:24 ] >>327 [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press [KT] J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley [I] 石畑 清，アルゴリズムとデータ構造，岩波書店 [S] R. Sedgewick, Algorithms in C, Addison-Wesley [CLRS] はこの分野では定番で，標準的な教科書．和訳有． [KT] は最近出た本で，現代的な記述がされている． [I] は個人的にお勧めする本で，記述がやさしい．入門には適正． [S] は実装中心に書かれていて，理論より実装という人向け．和訳有． KT は最近和訳が進んでるって話もあるけど，きっとだいぶ先． 332 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 11:32:21 ] 日経ソフトウェア買えばええやん 333 名前：デフォルトの名無しさん [2008/03/07(金) 07:20:53 ] アルゴリズムＣや珠玉のプログラミングはどう？ 334 名前：デフォルトの名無しさん mailto:sage [2008/03/07(金) 07:24:48 ] >>333 [S] R. Sedgewick, Algorithms in C, Addison-Wesley やん このあわてんぼさん。 335 名前：デフォルトの名無しさん [2008/03/07(金) 18:40:37 ] 「アルゴリズムC・新版」と「アルゴリズムC」って何が新版なの？ 336 名前： ◆JvckrUgJWM mailto:sage [2008/03/07(金) 18:43:11 ] >>327 つ ttp://d.hatena.ne.jp/yaneurao/20050522 337 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 02:31:13 ] 任意の26までの数値nが与えられたときに、Aからn番目のアルファベットまでを使ったN文字 の順列をぜーんぶ列挙するのになにかよい方法ってありますか？ つまりは任意の配列から総当りするためのネタ作りをしたい訳なのですが。。。 338 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 02:37:18 ] 順列？同じものの重複利用は禁止？ 339 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 08:06:36 ] permutation でぐぐれ いっぱいサンプルプログラムが転がってる 340 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 09:33:12 ] >>338 はい。2が入力だったAB,BA見たいな感じのものが生成されるような。。。 >>339 ありがとうございます。見てみますね。 341 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 22:47:15 ] アルゴリズムスレで言うのもなんだけど C++ だったら STL にある next_permutation 使うと割と簡単に書けると思う。 342 名前：337 mailto:sage [2008/03/11(火) 23:54:54 ] まだ詳細は調べ切れていないのですが、こういうのって自分で手書きするなら・・・・ 並べ替えたいN個の要素のリストから一つ取っては、N-1人の自分にN-1個になったリストと自分の ポインタをそれぞれ丸投げし、N-k番目の子はk番目の要素を一つとってさらに子に・・・取るものが ラスト一個になったら、自分の親の取った要素をつなげて表示する。 みたいな実装イメージになるんでありましょうか。 343 名前：デフォルトの名無しさん mailto:sage [2008/03/12(水) 23:07:29 ] 書き方なんていくらでもあるだろうが、俺だったらリストにせずに配列を使って再帰的には書くと思う。 っちゅーかそれこそ調べればいいんじゃないの？と言いつつ安易に書いてみる。 後、26! = 403291461126605635584000000 なんで全部回してるとやってられないと思う。 #include <iostream> int result[26]; void permutation_imp(int n, int m) {   if(m == n) {     for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(result[j] == i) std::cout << ' ' << static_cast<char>('A' + j);     std::cout << std::endl;   } else {     for(int i=0;i<n;++i) if(result[i] == -1) { result[i] = m; permutation_imp(n, m+1); result[i] = -1; }   } } void permutation(int n) {   for(int i=0;i<n;++i) result[i] = -1;   permutation_imp(n, 0); } int main(void) {   permutation(3);   return 0; } 出力結果：  A B C  A C B  B A C  B C A  C A B  C B A 344 名前：デフォルトの名無しさん mailto:sage [2008/03/13(木) 21:43:11 ] 参加してみた #include<stdio.h> #include<string.h> void swap(char *a, char *b){ char c; c=*a;*a=*b;*b=c; } void func_internal(char *buf, int bufsize, int left){ int i; if(left<=0) printf("%.*s\n", bufsize, &buf[-bufsize]); // 気持ち悪いかな？ for(i=0;i<left;i++){ swap(&buf[0], &buf[i]); func_internal(buf+1, bufsize, left-1); swap(&buf[0], &buf[i]); } } void func(char *buf, int bufsize){ func_internal(buf, bufsize, bufsize); } int main(void){ char buf[]="abcde"; func(buf, strlen(buf)); return 0; } 345 名前：337 mailto:sage [2008/03/14(金) 03:01:52 ] >>333-334 これまた短いですね。。。なんでこんなのが思いつくのかが不思議です。 自分の思った方法でも無理ではないんだろうなとは思うのですが、擬似コードの段階で だらだらしたものになってますからね。。。 再帰ですらすら考えられる人ってあたまよさそうです。 346 名前：337 mailto:sage [2008/03/14(金) 03:02:36 ] >>345 アンカーミス。。。 >>343-34 でした。 347 名前：デフォルトの名無しさん mailto:sage [2008/03/14(金) 09:00:14 ] 多くのアルゴリズムは定番とか定石がある。特に基礎的なものは。 このスレのタイトルの本もそういうものだわな 348 名前：デフォルトの名無しさん mailto:sage [2008/03/17(月) 18:49:55 ] A/D変換データをソフト的な処理で安定させるやり方 として移動平均以外に何かありますか？ 移動平均は平均回数をおおくとると、反応 が遅く（変化が鈍く）なるので、なるべくそうならな い方法を探しています。 349 名前：デフォルトの名無しさん mailto:sage [2008/03/17(月) 22:10:48 ] >>348 Ａ／Ｄ、Ｄ／Ａ半導体 science6.2ch.net/test/read.cgi/denki/1120158621/ 350 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 02:11:43 ] >>348 高次曲線近似とかベジェ曲線近似はどうかな？ 351 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 09:17:19 ] 移動平均はFIRフィルタ　LPFの一種だから係数をキチンと設計すれば応答性と安定性を両立出来る。 計算量の面では２次の IIRフィルタにすれば、応答性と安定性と計算量も両立出来る。 352 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 10:01:45 ] >>350 初めてききました。なんだかC言語で書くと難しそうですね。 >>351 係数って平均回数のことですよね？ 353 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 11:45:53 ] 平均回数じゃなくて、 FIRフィルタでするという場合は、それぞれに重みを付けて計算するわけ だから、移動平均に比べて計算コストは非常に大きい 例えば、サンプリング間隔の1/5以上で変動するようなノイズを取りたいという時に 16個の移動平均をしても ノイズは1/16までしか減らないけど 0, 0.015270303 1, 0.048044002 2, 0.098545986 3, 0.151768713 4, 0.186370997 5, 0.186370997 6, 0.151768713 7, 0.098545986 8, 0.048044002 9, 0.015270303 と１０個の係数かけて累積すれば、サンプリング間隔の1/5以上の成分は1/200以下に減る 354 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 15:30:03 ] 例えば １０、１５、２０、１０ っていう４つのデータがある場合 10*0.4 + 15*0.2 + 20*0.2 + 10*0.2みたいに するっていうことですか？ この重みの決め方がまた大変そうですね。 ちなみに353の例だとなんで1/200になるんですか？ なんかアルゴリズムとは関係なさげな話になって 申し訳ないです。 355 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 20:34:43 ] たとえば、　sin(i*1.3)*100+200 みたいな信号が入力されたとする。 入力　移動平均　>>353の方式それぞれの結果は 200.0 12.5 3.1 296.4 31.0 14.1 251.6 46.7 37.8 131.2 54.9 73.6 111.7 61.9 115.1 221.5 75.8 152.4 299.9 94.5 178.6 231.9 109.0 192.7 117.2 116.3 198.4 123.8 124.1 200.0　 <--　10個目から >>353 の方式はほぼ200に安定 242.0 139.2 200.0 298.7 157.9 200.1 210.8 171.0 200.0 107.1 177.7 199.9 139.5 186.4 200.0 260.6 202.7 200.1 <-- 移動平均は16個目以後でも±8程度変動する 292.9 208.5 200.0 189.1 201.8 200.0 101.3 192.4 199.9　ただしsin(i*w) のwの係数が　 2*PI/5=1.25 以上の時に >>353 は効く 158.1 194.1 200.0 276.3 204.4 200.1 356 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 22:37:03 ] ちょっと考えてる問題があるので意見を聞かせてください。 例えば300個の積み木があるとして、これらは様々な重さ・大きさがあり、5種の色のいずれかが ついてたとします。 これらを山に積み上げて行くときに、なるべく重さのピークが高い山がたくさん欲しいけれど、以下 の条件を満たさないといけないとします。 １．大きいものほど下にある ２．一山は積み木は10個が限度だけど、赤い積み木が三つ含まれていたら8個が限度になる。 ３．一山には2色しか存在してはいけないし、異なる色の境界は1箇所だけ(赤青赤はだめで、赤赤青は良いみたいな) ものすごく簡略化してしまいましたが、ナップザック問題に条件が加わったようなものになるのかと 思います。 細々とした条件・・・特に色の条件のせいで欲張り法が使えない気がするのですが、こういったものを常識的 時間で解く方法を調べたいので、キーワード程度でも教えてもらえませんか？厳密、近似は問いません。 357 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:31:07 ] >>356 「重さのピークが高い」って言葉の意味が分からない． あと，複数の山があったときにどう評価するかも分からない． 具体例をいくつか出してくれないかしら． 358 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:40:00 ] >>357 重さのピークについてですが、例えば価値＝重さが 1 2 2 3 4 5 6 7 8 9 のような9個があったとして、ここから>>356より少ないですが、2段まで積んでいいこととするならば 98 76 54 32 21 のような山できてほしくて、 19 82 27 36 45 のようにはできて欲しくないのです。 できた山の価値の標準偏差が一番でかい組み合わせになるんでしょうか・・・ 書いてて思いつきましたが、>>356をさらにいうならば、300個から最大で10個（特例を除く）で構成される山 を例えば15個作るとき、最も15山の価値の合計が高くなる組み合わせ。 これだとまた全く別の問題になってしまうのでしょうか。 359 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:40:37 ] ＞のような9個があったとして 10個でした。 360 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:46:06 ] まず問題を誰にでもわかるように定義することからはじめようか。 361 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:53:53 ] >>357 問題を考えるときは，それを数式で書けるくらいまで整理しないと， アルゴリズムなんて出せるはずがない． きっとなんか解きたい問題があって，あなたはその要点のみを 取り出したつもりだと思うんだけど，取り出し方が悪くて全然分からないよ． 362 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:10:42 ] 解きたい問題は実は特になくて、この手の雑学の本を読みながら考えていたら、これは欲張り法で できるのかな？と思ったのです。 で、もうちょっと整理してみました。 ナップサックが10個、取れる品物は300個あるとしてこれらはランダムに5色のいずれかの色がついている １．品物の価値が高いものを先に詰めねばならない ２．品物の色は、一袋には2色までしか混載できない ３．さらに一袋を詰め終わる過程で、色の切り替わる回数は一回のみ ４．ナップサック一つには10個まで入るが、赤い色の品物を3個入れていたら8個までになる 以上の満たして10個のナップサックをつくり、10袋の価値和を最大にする ２、３は、「赤赤赤赤青青青青青青」はいいが、「赤赤赤赤青青青青赤赤」だめ ４は「赤赤緑緑緑緑緑緑緑緑」で一袋、「赤赤赤緑緑緑緑緑」で一袋になるという感じ これですっきりしたよーに思いますがどうでしょう？ 色がついているのと、4みたいな条件のせいで、欲張れないんじゃないかと思うのです。 363 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:10:52 ] Σ((山の重さ)^2) を最大化するの？ 364 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:27:01 ] >>362 「袋の価値」は、中身の総和でいいのかな？ あと、その問題は、前の問題とはかなり違うように見えるんだけど。 重さのピークってのは忘れていいのかな？ 365 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:51:46 ] >>364 「袋の価値」＝中身の価値の総和です。 ピークはですね。。。上手く表現できないので省いてしまってかまいません。 が、、、いいたかったことは 10袋の価値の総和が等しいケースが2ケースあった場合、満遍なく10個そろったやつよりも ばらついてる方を解としたいというような・・・・ 仮に100円なら、「10円のうまい棒10本」よりは「40円のよっちゃんイカ1つと4本のうまい棒と4円のﾅﾆｶおかし5個」 の方を解としたいというような感じだったのです('A`) 366 名前：デフォルトの名無しさん mailto:sage [2008/04/16(水) 21:11:48 ] とりあえず赤色がなければ、価値の高いものから順に100個取ってくればいいんだよね？ 367 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 00:22:15 ] データをDRBDみたいな 再同期を含む同期を実行する種の アルゴリズムってどの分野に区分 されるの？ 全然文献なくて困る 368 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 03:14:15 ] >>366 おそらくそうなると思います。 赤があるから制限が8個になるからって、8個でも10個詰めたときより価値が高くなることも あるし、それは調べてみないとわからないよなぁと思うのです。 369 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 06:58:34 ] suffix arrayで正規表現検索ってできるんすか？ なんかsuffix trieにしないとできないみたいなんですが… 370 名前：デフォルトの名無しさん mailto:sage [2008/04/26(土) 10:14:29 ] できる．理論上 suffix tree/trie で書けるアルゴリズムは suffix array を用いて全く同じ計算量で実行できる． 371 名前：デフォルトの名無しさん [2008/04/28(月) 22:01:30 ] なぁなぁ、教えてくれよ。 有向グラフっての？　巡回サラリーマンっての？　ダイクストラ法っての？　なんかそんなの。よくわからないけど。 平面上に有限の座標群がある。まぁA〜Zとしよう。 いくつかの座標間には経路がある。A-Bには経路があるが、B-Cには経路がないって感じ。 で、与えられた二点間を結ぶ全ての経路を算出するんだが、最短とか最長とかを考慮する必要はない。 とにかく、全ての経路を表示する。 座標情報はRDBに入力され、常に変動するので、計算するたびに違う結果になることもある。 乗り換え案内みたいなソフトウェアを作ろうと思ってるんだけど。 こういうのってどう考えればいいの？ 372 名前：デフォルトの名無しさん [2008/04/28(月) 22:18:32 ] バルブソート の検索結果 約 693,000 件中 1 - 10 件目 多すぎだろ。 373 名前：デフォルトの名無しさん [2008/04/28(月) 22:20:53 ] バブルソート の検索結果 約 267,000 件中 1 - 10 件目 いったいどういうことだよ。 おれがおかしいのか？ 374 名前：デフォルトの名無しさん mailto:sage [2008/04/28(月) 22:38:38 ] >>371 東大かどっかの研究レポートがwebにのってたよ 375 名前：デフォルトの名無しさん mailto:sage [2008/04/29(火) 02:26:12 ] >>373 ウェブ "バルブソート" に一致する日本語のページ 10 件中 1 - 10 件目 (0.14 秒) ダブルコーテーションで括らないと曖昧検索される 376 名前：デフォルトの名無しさん mailto:sage [2008/04/29(火) 03:52:36 ] >>372 アホ。 377 名前：デフォルトの名無しさん [2008/04/29(火) 04:32:38 ] >>375 KY 378 名前：デフォルトの名無しさん mailto:sage [2008/04/29(火) 12:42:32 ] >>371 条件の確認なんだけど，「二点間の経路」で列挙したいのは 同じ頂点を複数回通らないような経路でよい？ あと，経路の数は半端なく多くなることがあるけど 出力順は問わないの？ 379 名前：デフォルトの名無しさん [2008/04/30(水) 01:09:48 ] >>378 おー、レスサンクス！ 例えば、下図のパターンで考えると、 ┌B─D┐ A｜ ｜ F └C─E┘ ABDF、ACEF、ACBDF、ABCEF、ABCDEF、ACBDEF、ACDEF、ABDEFだっけ？ 全体が重複してさえいなければ同じ頂点、同じパスを辿ってもかまわない。 今は、とりあえず経路の算出方法で頭をひねってる。 次の段階として、各パスにはコストを持たせ、出力する際には、パスが少ない順・多い順、総コストの多い順・少ない順、パスがnになる場合のみ出力、 ノードBが利用不能になった場合の代替経路は… とかってのを考えてるよ。 380 名前：デフォルトの名無しさん mailto:sage [2008/04/30(水) 01:21:35 ] >>379 ということは ABDECBDF ABDECBDECBDF ABDECBDECBDECBDF ABDECBDECBDECBDECBDF ABDECBDECBDECBDECBDECBDF ABDECBDECBDECBDECBDECBDECBDF ABDECBDECBDECBDECBDECBDECBDECBDF ABDECBDECBDECBDECBDECBDECBDECBDECBDF ABDECBDECBDECBDECBDECBDECBDECBDECBDECBDF ABDECBDECBDECBDECBDECBDECBDECBDECBDECBDECBD........ECBDECBDECBDECBDECBDF でもOK？ 381 名前：デフォルトの名無しさん mailto:sage [2008/04/30(水) 09:37:50 ] >>379 重複アリだと >>380 みたいになって，経路が無限個になって「列挙」できなくなるのよ． この場合方針としては ・経路が無限個にならないように問題を変更する ・経路総数は無限個でもよいから、適当な順序で（上から有限個）出力する のどっちか．さあどうしよう？ あと，そろそろ用語を正しておくと経路やパスってのは全体のことで， 隣り合ってるところは辺や枝と呼ぶのが普通ね． 382 名前：デフォルトの名無しさん [2008/04/30(水) 10:50:28 ] >>381 用語サンキュ。じゃ、座標を「節」、隣り合っている経路を「辺」、始点から終点を「経路」とすればいいかな。 それと、何となく頭の中に次みたいな考え方が頭にあったから380の指摘は頭になかったな〜。 1.まずAをピックアップ。Aには除外マークを付ける 2.Aに隣り合う節B、Cの中からまずBをピックアップしBに除外マーク。 3.Bに隣り合う節A、C、Dの内、除外マークがないC、DからまずCをピックアップ 4.Cに隣り合う節A、B、Eの内、除外マークがないEをピックアップしEに除外マーク 5.Eに隣り合う節D、Fのうち除外マークがないD、F、そのうちDをピックアップ 6.〜略〜で、除外マークがないFをピックアップし、Fは終点なのでABCDEFの経路が一つ完成 7.5でDに行かずFに至って、ABCDFが一つ完成 8.2でCをピックアップし、以下ループ ということは、378の指摘どおりだったのか。...スマソ。 383 名前：デフォルトの名無しさん [2008/04/30(水) 11:31:00 ] 各節間の距離がわかっているなら終点との距離と比較するだけでだいぶ正解に近づきそう。 384 名前：デフォルトの名無しさん [2008/04/30(水) 11:38:53 ] 乗換案内で同じ区間を2度とおる意味ってあまりなさそうなんだけど。 385 名前：デフォルトの名無しさん mailto:sage [2008/04/30(水) 19:53:08 ] 赤黒木とはなんぞや。 386 名前：デフォルトの名無しさん mailto:sage [2008/04/30(水) 20:29:01 ] 2-3-4木と等価な構造を持つ木を二分木で作るためのデータ構造。 387 名前：デフォルトの名無しさん mailto:sage [2008/05/03(土) 08:34:47 ] 「動的計画法（dynamic programming）」で名前最悪だな。 変な名前のせいで、この手法のポイントが要するにどこにあるのか なかなか理解できなかった。 「部分問題解展開法」とかそんな名前にすれば良かったと思う。 388 名前：デフォルトの名無しさん mailto:sage [2008/05/03(土) 08:35:36 ] ×「動的計画法（dynamic programming）」で名前最悪だな。 ○「動的計画法（dynamic programming）」って名前最悪だな。 389 名前：デフォルトの名無しさん mailto:sage [2008/05/03(土) 08:47:58 ] "dynamic programming"はもはやFOLDOCには載ってない。 "programming"は「コンピューター・プログラミング」ではなく、「計画」のこと。 overlapping subproblems, optimal substructure, memoizationする手法のこと。 390 名前：デフォルトの名無しさん mailto:sage [2008/05/03(土) 09:55:42 ] FOLDOCに載ってないことはあまり指標にはならないんじゃないかな。 たとえば "greedy algorithm" や "divide and conquer" も載ってないしね。 ネーミングの由来は、部分問題を解いて、それを元に新たな計画問題を作る感じが、 動的に計画問題を解いているっぽいから、だそうな。 391 名前：デフォルトの名無しさん [2008/05/10(土) 19:34:49 ] 挿入ソートの計算量ってどうやって求めるの？ いろいろ調べてみたけど式にΣが出てきたからわけわからなくなった。 そんな馬鹿な俺でも理解できるようにだれか説明してくれないかな。 392 名前：デフォルトの名無しさん mailto:sage [2008/05/10(土) 20:20:42 ] >>391 「挿入ソート」にもマイナーバージョンがいくつもあるので， もう少し詳しいアルゴリズムを述べてくれないと厳密には解析できない． まあ大雑把には，挿入ソートは ・空リストから初めて，要素を一つづつ "INSERT" する ・INSERT は，ソート済みのリストに要素を順序を壊さないように追加する というアルゴリズムなので，これを解析する． 計算量を要素の比較回数で評価することにする． 長さ m のリストに対して INSERT するときの比較の回数を T(m) と書くと， 全体での比較の回数は Σ[m=0..n-1] T(m) になる． T(m) は実装にもよるが，順番に比較していって挿入できる場所を探すと 最大 m 回の比較が発生しうる．つまり T(m) ≦ m． よって全体の比較回数は Σ[m=0,n-1] T(m) ≦ Σ[m=0,n-1] m = n(n-1)/2 = O(n^2) 多分上の説明だと分からないところがあると思うので，ここが分からんとか聞いとくれ． 393 名前：デフォルトの名無しさん [2008/05/11(日) 12:58:18 ] コメントありがとうございます。 参考にさせていただきました。 webやテキストの説明でもそれぞれ異なった説明の仕方をしていましたので多少混乱していたようです。 なんとか理解することができました。ありがとうございます。 394 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 16:30:27 ] コムソートってこれでOKだよね？ void sort(int[] data) { 　　for (int h = data.length * 10 / 13; h >= 1; h = h * 10 / 13) { 　　　　for (int i = h; i < data.length; i++) 　　　　　　if (data[i-h] < data[i]) { 　　　　　　　　int w = data[i-h]; 　　　　　　　　data[i-h] = data[i]; 　　　　　　　　data[i] = w; 　　　　　　} 　　} } 普通にクイックソート並みに速いけど。どうなんでしょう？ クイックソートと違って欠点が無いように思う。 クイックソートの方が速いって反論よろしく。 395 名前：デフォルトの名無しさん mailto:age [2008/05/30(金) 18:38:56 ] 反論ないなら最速ソートアルゴリズムの座を奪いますよ〜 396 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 19:02:59 ] 今、標準ライブラリと勝負したら負けたわ。 アルゴリズムはもちろん、クイックソート。ただし、工夫されているとのこと。 自作のクイックソートがダメなだけだった。 なので反論は遠慮しとく。 397 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 19:07:41 ] >>394 やってみたけどstd::sort()の1/2程度の速度しか出ないじゃん 398 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 22:02:40 ] >>394 速度以前に正しくないんでは？ [1,6,3,4,3,1,6] → [6,4,6,3,3,1,1]　となったけども。 399 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 11:16:46 ] クイックソートはきちんとチューニングしてきちんとコーディングしてこそのもの。 岩波ソフトウェア科学シリーズの『アルゴリズムとデータ構造』のクイックソート の項目は読むべき。 400 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 15:30:24 ] >>398 comb sortについてよく調べると、ギャップが1になったら普通にバブルソートにするようです。 しかも、その時に整列済みか確認しないといけないようです。 ギャップがある程度(16ぐらい)に小さくなったら、挿入ソートに切り替えってのを試したら、意外と速いです。 ただのシェルソートっていう突っ込みは（ｒｙ 401 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 09:25:07 ] >>400 > ギャップがある程度(16ぐらい)に小さくなったら、 > 挿入ソートに切り替えってのを試したら、意外と速いです。 これはquick sortもそう。 特にintとかチンケなものをsortしているときは。 402 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 11:13:39 ] >>401 いかにもオリジナル的な書き方になったのはすみませんが、それは知っていました。 ついでにちょっと改良したやつを。 コムソートの部分をシェーカーソート風にすると、より良いです。(オリジナルではないです) シェーカーソートはバブルソートを双方向から行います。 シンプルさが売りなのにちょっとゴチャついてるので、本当はシェーカーソートは外したいんですけどね。(つづく) void sort(int[] data) { 　　for (int h = data.length * 10 / 13; h >= 17; h = h * 10 / 13) { 　　　　for (int i = h; i < data.length; i++) 　　　　　　if (data[i-h] < data[i]) 　　　　　　　　swap(data, i-h, i); 　　　　h = h * 10 / 13; 　　　　if (h < 17) break; 　　　　for (int i = data.length - 1; i >= h; i--) 　　　　　　if (data[i-h] < data[i]) 　　　　　　　　swap(data, i-h, i); 　　} 　　for (int i = 1; i < data.length; i++) { 　　　　int w = data[i], j = i; 　　　　for (j = i; j > 0 && data[j-1] < w; j--) 　　　　　　data[j] = data[j-1]; 　　　　data[j] = w; 　　} } void swap(int[] a, int i, int j) { 　　int w = a[i]; 　　a[i] = a[j]; 　　a[j] = w; } 403 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 11:21:56 ] 欠点は挿入ソートの欠点がそのままになっていて、データ数が多いときに少ないときに比べて遅くなります。 解決策として、２分挿入ソートが良さそうです。 ただ、さっきも書いたとおり、コムソート(バブルソートの改良)と挿入ソートの組み合わせという 単純なアルゴリズムで結構速し、特に欠点なしという所をアピールしたいので、まぁそのままで。 Javaの標準ライブラリとは同じぐらいの速さですが、興味があれば勝負させて見てください。でわ。 404 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 11:23:25 ] 「他の言語でも」が抜けてました。 405 名前：デフォルトの名無しさん mailto:sage [2008/06/04(水) 13:01:44 ] 純粋なアルゴリズムの話じゃないけど、 今なら分散処理できるようなデータ構造やアルゴリズムの方が良いかもな。マルチコアだから。 406 名前：デフォルトの名無しさん mailto:sage [2008/06/05(木) 00:41:48 ] >>403 たった1000000個くらいのランダムデータに対しても std::sort() の1/2未満の性能しか出ないよ。 ソーティングの世界では一瞬でも遅いのは大きな欠点。 407 名前：デフォルトの名無しさん mailto:sage [2008/06/05(木) 09:11:39 ] >>406 その通りで。 あれから、VC++をダウンロードしてちょこっと試してみたんですが std::sort()の前にまずはCの標準のqsort()でやったところ qsort()の方が全然速かったです。qsort()の方がstd::sort()よりも速いのかもしれませんが 試す前にやめました。(C++をあまり知らないということもあって) 408 名前：デフォルトの名無しさん mailto:sage [2008/06/05(木) 23:21:04 ] たいていはstd::sortの方が早いんだけどね。 409 名前：デフォルトの名無しさん mailto:sage [2008/06/06(金) 00:23:30 ] STLPort使えよ 410 名前：デフォルトの名無しさん mailto:sage [2008/06/07(土) 17:13:13 ] 比較処理がインライン化される可能性のある std::sort の方が 確実にインライン化されない qsort よりも一般に速い。 411 名前：デフォルトの名無しさん mailto:sage [2008/06/21(土) 23:56:21 ] b+-treeに関する詳しい解説があまり見つからないんだけど、 要はb-treeとなにが違うの？ 突然の話題で申し訳ない。 412 名前：デフォルトの名無しさん mailto:sage [2008/06/22(日) 09:25:03 ] ttp://en.wikipedia.org/wiki/B%2B_tree 413 名前：デフォルトの名無しさん mailto:sage [2008/06/23(月) 00:55:46 ] >>411 葉にデータを集めたり、葉同士をリンクリストで繋げるなど、積め方を 工夫して末端の葉へのアクセスを単純にできるようにしたのがB+木。 (B木でもイテレーションは再帰やスタックでできるが) B+木のノードの追加削除は複雑で、手間の割にうまく実装しても速度は 素のB-Treeに劣る。空間効率は良くなるので外部記憶で使うとか、 構造上範囲検索で有利に働くので、それを多用するなら意味がある。 B木でもキャッシュやファイルマッピングが使える状況だと空間効率を除き 差はほとんどない。 414 名前：デフォルトの名無しさん mailto:sage [2008/07/03(木) 16:37:27 ] red-black-treeにおけるinsertやdeleteはいろいろなサイトに掲載されているのですが、 木の分割についてのアルゴリズムがどこを探しても見当たりません。 バランスを保ちながら木を2つに分割するアルゴリズムは存在しないのでしょうか? 415 名前：デフォルトの名無しさん mailto:sage [2008/07/04(金) 07:19:15 ] insertやdeleteを組み合わせればできるんでは 416 名前：デフォルトの名無しさん mailto:sage [2008/07/04(金) 22:53:42 ] て言うか分割って何？ 417 名前：414 mailto:sage [2008/07/04(金) 23:48:17 ] >>415 ありがとうございます。一応insertとdeleteの組み合わせではできたのですが もっと早い方法が無いのかと思って書き込みました。 もう少し考えてみます。 >>416 木をある値を境にして二つの木に分けたい、という意味です。 一つ一つのノードを木からdeleteして新しい木にinsertしなおせばできるのですが、 もっと単純にやる方法がないかと探しています。 418 名前：デフォルトの名無しさん mailto:sage [2008/07/05(土) 00:55:24 ] >>417 > 木をある値を境にして二つの木に分けたい 任意の値と言うこと？ なんかいい方法ありそうなが気がするが、俺の頭では無理だ...。 419 名前：415 mailto:sage [2008/07/05(土) 13:40:03 ] 順序はできてるんだから、適当に並べ替えるだけかと。 420 名前：デフォルトの名無しさん mailto:sage [2008/07/05(土) 14:48:09 ] その並べ替えるコストを問題にしてるんだが。 421 名前：414 mailto:sage [2008/07/06(日) 00:40:59 ] >>418 そうです、任意の値を境にして二つのred-black-treeに分割したい、という意味です。 >>419 なるべくo(logn)の係数を抑えてやりたいのです。。。 >>420 そうなんです＞＜ いろいろ考えてみてはいるんですが。。。どうしてもバランスがとれなくて 困っています。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef