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

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 2 名前：デフォルトの名無しさん [04/06/03 23:18] ( ´∇｀)y-~~~ ﾍｪ... 3 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:20] 2GETTER用のプログラム作ってみました。要りますか？ 4 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:20] いるいる 5 名前：デフォルトの名無しさん [04/06/03 23:23] www2.famille.ne.jp/~akio1998/l_x115.html 6 名前：デフォルトの名無しさん [04/06/03 23:27] ↑↑概論↑↑ 7 名前：デフォルトの名無しさん [04/06/03 23:37] pc5鯖を潰すｱﾙｺﾞﾘｽﾞﾑ募集してます 8 名前：デフォルトの名無しさん mailto:sage [04/06/04 01:19] 奥村先生のアルゴリズム事典はぼろぼろになるまで読んでたな。 9 名前：デフォルトの名無しさん [04/06/04 19:33] >>8 僕のは、まだ新品同然です。 この本の内容を、あらかた覚えるにはどれくらいの月日がかかったのでしょうか？ 10 名前：デフォルトの名無しさん mailto:sage [04/06/04 20:04] アルゴリズムといえばコーマン 11 名前：デフォルトの名無しさん mailto:sage [04/06/04 21:24] >>9 あの本は事典ですよ？ 12 名前：デフォルトの名無しさん [04/06/05 11:48] ｱﾙｺﾞﾘｽﾞﾑって何ですか？ 13 名前：デフォルトの名無しさん mailto:sage [04/06/05 13:40] >>12 ゴリズム氏が考え出したとある手法の一つです。 14 名前：デフォルトの名無しさん mailto:sage [04/06/05 14:15] >>13 ちがうよ。 １６世紀、オーストリアのディマン＝アルゴが提唱した基礎的な音楽のリズムだよ。 15 名前：デフォルトの名無しさん [04/06/05 14:36] 違うよ、ギタリスト　アル・ディメオラの弟ゴリズムが生み出した新しいリズムだよ、 16 名前：デフォルトの名無しさん mailto:sage [04/06/05 15:08] (#ﾟДﾟ) ムズリ、ｺﾞﾙｧ!!! .←ムズリ（タンザニア出身） 17 名前：デフォルトの名無しさん [04/06/05 19:40] >>11 事典として使うものですか。。。 どうりでいっぱいある訳だ 18 名前：デフォルトの名無しさん mailto:sage [04/06/05 23:38] >>8 あれのJava版についてはどう思うよ？ アルゴリズムが増えて改良されてなかなかのもんだと思うが。 しかしあの本のソースコード書いた香具師は クラス継承の合理的な使い方を分かってない感じだな。 19 名前：デフォルトの名無しさん mailto:sage [04/06/05 23:51] いや、アルゴリズムとは アル　ゴア元副大統領の異名のことだよ　 20 名前：デフォルトの名無しさん mailto:sage [04/06/06 00:05] ある御リズム 21 名前：デフォルトの名無しさん mailto:sage [04/06/06 00:12] アルゴリ＝ズム＝ダイクン 22 名前：デフォルトの名無しさん mailto:sage [04/06/06 02:04] >>18 Java版出てるの知らんかったよ。今度買ってみる。 23 名前：デフォルトの名無しさん mailto:sage [04/06/06 03:49] くぬーすセンセが新刊だされるのが遅すぎるのでmitので我慢してね♪ 24 名前：デフォルトの名無しさん [04/06/06 18:30] いまだにバブルソートをバルブソートと言い間違えてる奴大杉 25 名前：デフォルトの名無しさん mailto:sage [04/06/06 19:18] どんなソートだ 26 名前：デフォルトの名無しさん mailto:sage [04/06/06 19:22] イング兵衛のバンドに昔いた奴か 27 名前：デフォルトの名無しさん mailto:sage [04/06/06 19:49] www.google.co.jp/search?sourceid=navclient&hl=ja&ie=UTF-8&oe=UTF-8&q=%E3%83%90%E3%83%AB%E3%83%96%E3%82%BD%E3%83%BC%E3%83%88 そんなに多くないよ 28 名前：デフォルトの名無しさん mailto:sage [04/06/06 20:40] 奇特なひとだねぇ 29 名前：デフォルトの名無しさん mailto:sage [04/06/06 23:20] >>1 そんなに暇ならコードの一つぐらい覚えろ 他力本願野郎がｗ 30 名前：デフォルトの名無しさん mailto:sage [04/06/06 23:35] なんてねｗ 31 名前：デフォルトの名無しさん mailto:sage [04/06/19 11:05] >>25 ブルーベレーちゃんが手作業で並べ替えてくれまつ。 valve.kubota.co.jp/main.html 32 名前：デフォルトの名無しさん [04/07/06 13:04] 強固なスレだね。 33 名前：デフォルトの名無しさん [04/07/06 13:10] ビリーフプロパゲーション（Belief Propagation） 計算確率アルゴリズムについて、知っている人、または 説明があるサイトをご存知の方は教えてください お願いします。 34 名前：デフォルトの名無しさん [04/07/06 14:21] ファイルをパースして読みこむプログラムを教えてください 35 名前：デフォルトの名無しさん mailto:sage 「パース」だけで話が通じると思ったら大間違いだぼけ [04/07/07 17:22] >>34 どうやってファイルに遠近感を付けるというのだ！ 36 名前：デフォルトの名無しさん mailto:sage [04/07/07 17:30] 言いたいことはメール欄に書けばいいと思ったら大間違いだぼけ と言ってみるﾃｽﾄ 37 名前：デフォルトの名無しさん mailto:sage [04/07/07 17:47] parse 38 名前：デフォルトの名無しさん mailto:age [04/07/08 23:04] あの本は聖典なんだけど、それが何か？ 39 名前：デフォルトの名無しさん mailto:age [04/07/08 23:05] アルゴリズムを使って、　まそこん　を造りたいのですが 40 名前：デフォルトの名無しさん mailto:age [04/07/08 23:15] 何がひつようでしか？ΛΛ 　　　　　　　　　・　・ 　　　　　　　　　　△ 　　　　　　　　　　ЦЦ　　 41 名前：デフォルトの名無しさん [04/07/09 22:21] 多次元配列をソートするのに、いいアルゴリズムはないですか？ 42 名前：デフォルトの名無しさん mailto:age [04/07/09 22:25] 多次元だろうが1次元だろうがソートアルゴリズムは殆ど一緒だろ。 それともキーが多次元でランダムなのか？ 43 名前：ケンや mailto:happy-days1989@zpost.plala.or.jp [04/07/09 22:39] 俺にウィルスちょうだい。 パソコン買い換えるので何とか壊してください。 happy-days1989@zpost.plala.or.jp 44 名前：デフォルトの名無しさん [04/07/24 16:07] □□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□ □□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□ □□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□ □■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□ □□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□ □□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□ □□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□ □□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□ □■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□ □□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□ □□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□ □□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□ □■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□ □■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□ □□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□ □□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□ 45 名前：デフォルトの名無しさん mailto:sage [04/07/24 18:54] >44 46 名前：1 [04/07/25 11:06] pc5.2ch.net/test/read.cgi/tech/1090227743/1 ついに強固なスレが現れました 47 名前：1 [04/07/25 11:08] □□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□ □□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□ □□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□ □■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□ □□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□ □□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□ □□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□ □□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□ □■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□ □□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□ □□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□ □□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□ □■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□ □■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□ □□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□ □□□□■□□□□□□□□■■□□□□□□■■■■□□□□です。 48 名前：デフォルトの名無しさん [04/10/01 11:12:36] バブルソートってどんなときに使うの？ 49 名前：デフォルトの名無しさん mailto:sage [04/10/01 12:08:21] >>48 教育用？ クレオソートってどんなときに使うの？ 50 名前：デフォルトの名無しさん mailto:sage [04/10/01 12:58:46] >>49 > クレオソートってどんなときに使うの？ 下痢止めの薬を作るとき、かな。 51 名前：デフォルトの名無しさん mailto:sage [04/11/08 22:59:22] >>48 使うときほぼないけど、学習用によく使われるみたい。 52 名前：1 mailto:sage [04/11/08 23:05:17] おいっ！おまいら！大変です！ バルブソートでググったら、なんとこのスレが２番目にあったよ 53 名前：デフォルトの名無しさん mailto:sage [04/11/09 17:05:25] #include <algorithm> 54 名前：デフォルトの名無しさん [05/01/30 17:56:48 ] age 55 名前：デフォルトの名無しさん [05/03/08 22:07:30 ] 自前で簡単なオーディオミキサを作りたいのですが、どんなアルゴリズムにすれば良いのでしょうか。 サンプリングレートは8000。 チャンネルは1つ(モノラル)。 ビット数は16。 音声データは160バイト(20[ms])に細かく切られている。 これが複数の音源からやって来ます。 複数の音源の同期は取りません。取り敢えずタイミングは無視してミックスします。 同期よりも遅延の方を問題に思っていますので。 こんな感じで良いのでしょうか？ for( int i = 0; i != 160; i++ ) 　　if( buffer_1[i] < buffer_2[i] ) 　　　　buffer_o[i] = buffer_2; 　　else 　　　　buffer_o[i] = buffer_1; その後でDirectXでストリーミング再生します。 56 名前：55: 訂正 [05/03/08 22:08:24 ] for( int i = 0; i != 160; i++ ) 　　if( buffer_1[i] < buffer_2[i] ) 　　　　buffer_o[i] = buffer_2[i]; 　　else 　　　　buffer_o[i] = buffer_1[i]; 57 名前：デフォルトの名無しさん mailto:sage [05/03/09 00:07:52 ] アルゴリズムと言うよりも、スレッドとかノンブロッキングとかデバイスの扱いでは？ DirectXとかよくわからんけど 58 名前：55 [05/03/09 00:37:21 ] すみません。要点がはっきりしてませんでした。 ポイントは、音源Aと音源Bのデータをミックスする時にどの様にすべきかです。 例えば以下の様な事が単純に思い付きます。 1.AとBの平均を取る。 out=(A+B)/2 2.AとBを単純に足す。最大値を越えた場合(65535<(A+B))は最大値(==65535)とする。 out=max(65535, A+B) 3.AとBを比較して、大きい方の値とする。(>>56の内容に等しい) out=max(A, B) 良く分かりませんが、他にもっとインテリジェンスなやり方が有ったら教えて頂きたいなあと思った次第です。 59 名前：デフォルトの名無しさん mailto:sage [05/03/09 00:51:31 ] out=a*A+b*Bでいいんじゃないの？ (a, bは入力レベル。通常は1でいいと思うけど、音割れするようだったら絞ればいい) 60 名前：55 [05/03/09 01:03:55 ] ありがとうございました。 実はRTPもどきを使って3人以上で会話するってプログラムを作ってました。 会話の場合は、1人が喋っていても他の2人は無音の場合が多く、>>59のやり 方で問題無いと思います。 61 名前：デフォルトの名無しさん mailto:sage [2005/04/04(月) 15:57:46 ] ええとね。 サウンドプログラミング2 pc8.2ch.net/test/read.cgi/tech/1091054082/ で聞いてくれれば良かったかもな。 問題は、複数の音源の場合、サンプリングレートが微妙に違う点にあると思うよ。 まあ、無音の間に適当に入れたり出したりして誤魔化すんだろうけど 62 名前：デフォルトの名無しさん mailto:sage [2005/04/04(月) 16:01:51 ] で、そいう場合は out = r*(A+B); if( abs(out)>=0x7fFF) r = r*0.95 else r=min(1.0, r+1/8000); こんな感じで、合成音がクリッピングしたら、出力を絞るような方式がいいと思うよ。 63 名前：デフォルトの名無しさん [2005/04/30(土) 22:21:53 ] よく、テキストの機能とかにある無限アンドゥってどんなアルゴリズムなんでしょうか？教えてください 64 名前：デフォルトの名無しさん mailto:sage [2005/04/30(土) 22:25:14 ] ユーザーが入力した内容のログを全部取っておくだけの事。 65 名前：デフォルトの名無しさん mailto:sage [2005/04/30(土) 22:37:29 ] 安藤がきたら、挿入なら削除というようにログの逆を辿る。 Redoはログからもう一度ユーザーの内容を再現していく。 うまく動くと面白いし、何かを編集するアプリなら必須機能の１つ。 がんばって作ってくれ。 66 名前：デフォルトの名無しさん mailto:sage [2005/04/30(土) 22:56:45 ] クリックやキー入力のイベントが起こったとき 現在の状態を全部ファイルにバックアップする 67 名前：63 mailto:sage [2005/04/30(土) 23:00:56 ] とりあえず処理の検討はつきました。どうもです 68 名前：デフォルトの名無しさん mailto:sage [2005/05/01(日) 12:54:00 ] クヌース先生のアルゴリズムのバイブルを買うと馬鹿にされますか？ 69 名前：デフォルトの名無しさん mailto:sage [2005/05/01(日) 13:11:04 ] >>64,66 70 名前：デフォルトの名無しさん mailto:sage [2005/05/01(日) 13:15:15 ] 保管するだけでも場所とって大変だから、 図書館から借りてくることをオススメする 71 名前：デフォルトの名無しさん [2005/05/02(月) 01:03:58 ] >>68 されません 72 名前：デフォルトの名無しさん [2005/05/02(月) 19:34:01 ] マインスイーパーで裏返したセルが0だったときのアルゴリズムおせーて 73 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 19:47:56 ] >>72 m_buttonHogeを用意しといて if(stCell == 0) 　　m_buttonHoge(FALSE); else 　　m_buttonHoge(TRUE); ってな感じでは？ 74 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 19:49:54 ] ﾌﾟ(AA略 75 名前：デフォルトの名無しさん [2005/05/02(月) 19:53:44 ] マインスイーパーって裏返したのが0だったら周りの0も連鎖して裏返るんだよね そこが難しいんです 76 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 19:56:24 ] >>73 m_buttonHogeを用意しといて if(stCell[x][y] == 0) 　　m_buttonHoge.ShowWindow(FALSE); else 　　m_buttonHoge.ShowWindow(TRUE); のまちがいだろ 77 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 20:03:22 ] BOOL reverse(int x, int y) { 　　if(stCell[x-1][y-1] 　　　　m_buttonHoge[x-1][y-1].ShowWindow(FALSE); 　　else 　　　　m_buttonHoge[x-1][y-1].ShowWindow(TURE); 　　if(stCell[x][y-1] 　　　　m_buttonHoge[x][y-1].ShowWindow(FALSE); 　　else 　　　　m_buttonHoge[x][y-1].ShowWindow(TURE); 　　if(stCell[x][y-1] 　　　　m_buttonHoge[x][y-1].ShowWindow(FALSE); 　　else 　　　　m_buttonHoge[x][y-1].ShowWindow(TURE); 　　if(stCell[x+1][y-1] 　　　　m_buttonHoge[x+1][y-1].ShowWindow(FALSE); 　　else 　　　　m_buttonHoge[x+1][y-1].ShowWindow(TURE); 以下略 　　return TRUE; } 78 名前：デフォルトの名無しさん [2005/05/02(月) 20:09:35 ] 裏返す ↓ ０だ ↓ 周りを探す ↓ また０だ ↓ 周りを探す ↓ ・・・・・・元の場所わかんねぇ('A`) 79 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 20:18:10 ] >>77 reverse(0, 0); は大丈夫なのかな？ 80 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 20:25:38 ] 77ですが >>79 TRY CATCHでくくって例外は処理しないようにすれば？ 81 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 20:32:24 ] >>80 TUREって何よ？ 82 名前：デフォルトの名無しさん [2005/05/02(月) 20:33:16 ] >>81 つまんねーレスすんなよ。 83 名前：デフォルトの名無しさん [2005/05/02(月) 20:41:59 ] http://から始まる文字列があった場合に<a href="hoge">hoge</a>に痴漢するアルゴリズム教えてください。 アドレスと文字列の区別は・・・どうするのが一般的？ 2バイト文字にぶち当たったらとかかな。 84 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 20:44:22 ] >>81 "つれ"た、ってことなんじゃ？ 85 名前：デフォルトの名無しさん [2005/05/02(月) 22:39:55 ] >>83 sedでよければｗ 86 名前：デフォルトの名無しさん mailto:sage [2005/05/02(月) 22:47:57 ] >>・・・・・・元の場所わかんねぇ('A`)  そこで再帰関数ですよ。 こんな感じだったけなぁー。 なんせ3年前位に作ったやつだから忘れちゃってる。 間違ってる可能性大 int hoge(int x,int y){     int b=0;     if(table[x][y] == BOME){          return BOME;      }      for(int i=0;i<9;i++){        if(table[pos[i].x+x][pos[i].y+y]==BOME){           b++;         }       }       if(b==0){          for(int i=0;i<9;i++){            hoge(pos[i].x+x,pos[i].y+y)          }       }       return 0; } 87 名前：デフォルトの名無しさん [2005/05/04(水) 21:48:03 ] コムソートってどんなソートなのでしょうか？ ググってもでてきません。よろしくお願いします。 88 名前：デフォルトの名無しさん mailto:sage [2005/05/04(水) 21:50:41 ] >>87 検索が下手。 www.google.co.jp/search?hl=ja&q=%E8%99%9A%E7%84%A1%E5%83%A7%E3%81%A8&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=lang_ja 89 名前：デフォルトの名無しさん mailto:sage [2005/05/04(水) 23:06:09 ] >>87 ttp://www.ffortune.net/comp/develop/sort/gaikan.htm 90 名前：デフォルトの名無しさん [2005/05/04(水) 23:52:38 ] >>89 ありがとうございます。 でもできたら参考文献とかあったらうれしいな、なんて 91 名前：デフォルトの名無しさん mailto:sage [2005/05/05(木) 00:02:29 ] 参考文献などない！ 92 名前：デフォルトの名無しさん mailto:sage [2005/05/05(木) 00:12:42 ] コムソートの利点はリソース消費しないってとこだね。 Comb sort algorithm www.google.co.jp/search?hl=ja&q=Comb+sort+algorithm&lr= 93 名前：デフォルトの名無しさん mailto:sage [2005/05/05(木) 04:30:23 ] 学生の宿題を手伝うスレｗ 94 名前：デフォルトの名無しさん [2005/05/07(土) 20:38:46 ] 数値を格納した二つの配列があり、 その二つの配列に共通する数値のみを選び出す効率的なアルゴリズムって何かありますか？ 95 名前：デフォルトの名無しさん mailto:age [2005/05/07(土) 21:17:43 ] >二つの配列に共通する数値 a.格納位置も一緒 b.格納位置が違っていてもＯＫ b.だとすると数値がダブっている場合どう考えるんだ？ 96 名前：デフォルトの名無しさん mailto:sage [2005/05/08(日) 05:15:32 ] ハッシュテーブルかな 衝突がなければO(1) 97 名前：デフォルトの名無しさん mailto:sage [2005/05/08(日) 07:11:44 ] >>96 でいいとおもうけど、別案 片方で分布数えソートの前段階（分布だけ調べる）まで行い、 もう片方をスキャンすれば、重複する値がわかる 98 名前：デフォルトの名無しさん mailto:sage [2005/05/08(日) 12:50:16 ] >>96 配列に格納されている数値が何かのハッシュだったら、どうするの？ 99 名前：デフォルトの名無しさん mailto:sage [2005/05/08(日) 15:42:48 ] >>98 内容がなんであっても、ハッシュで問題ないと思うがどうだろう？ 100 名前：デフォルトの名無しさん mailto:sage [2005/05/13(金) 13:47:35 ] ユーザーがマウスを用いてフリーハンドで引いた線を、 複数のベジェ曲線へと変換するアルゴリズムって何かありますか？ www.simdesign.nl/bezier.html 上記のような有料のライブラリは見つかったのですが・・・。 101 名前：デフォルトの名無しさん mailto:sage [2005/05/13(金) 15:56:51 ] >>100 そのサンプリング点を端点に、 端点の微分が一致するという条件で解いたらどう？ 102 名前：デフォルトの名無しさん mailto:sage [2005/05/13(金) 16:00:58 ] >>100 ttp://www.tensyo.com/urame/prog/linealgo.htm ここの 折れ線から滑らかな曲線に という所に、点を与えながら処理する方法が 103 名前：デフォルトの名無しさん [2005/05/15(日) 19:46:06 ] コンドーム 104 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 09:09:03 ] www.tensyo.com/urame/prog/linealgo.htm ここの　折れ線から滑らかな曲線に　以外に 複数のベジェ曲線へと変換するアルゴリズムって何かありますか？ 105 名前：デフォルトの名無しさん mailto:sage [2005/05/17(火) 23:45:00 ] 手書き 106 名前：デフォルトの名無しさん mailto:sage [2005/05/18(水) 07:29:50 ] >>104 それ以外にと聞かれるならば １、３次スプライン補間法 で解いてからベジェに変換する ２、混合スプライン、ベーススプライン等で解いてからベジェに変換する という方法が考えられます 107 名前：デフォルトの名無しさん mailto:sage [2005/05/20(金) 09:14:39 ] ベジェ曲線を描くときにマウスが拾ったすべての点において ベジェ曲線を描くのではなく、点を間引いて描きたいのですが、 どのように点を間引いたらいいかがわかりません。 何か良いアイデアはありませんか？ 108 名前：デフォルトの名無しさん mailto:sage [2005/05/20(金) 23:32:01 ] 3点支持 109 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 08:38:54 ] どのように間引くかと聞かれても、　どうしたいのか判らないので困ってしまう たとえば、直線的に引いた通過点を間引きたいならそうすればいい 　前２点の延長線からの誤差が一定いないなら、その前の点を除くとかさ 110 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 19:06:48 ] XMLデータの検索プログラムを作ろうと思っているのですが、 単純な検索はBtree*を用いて作成しましたが、XMLのある部分が合致するような 検索をする場合どのような手法があるのでしょうか？ 111 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 19:44:10 ] 基本的には文字列の検索と同じ方法になるだろうけど、それでは満足出来ないんだろうね。 となると、その部分をB木の検索キーに入れておくしかないかもな 112 名前：デフォルトの名無しさん mailto:sage [2005/05/21(土) 20:40:13 ] そっかぁBtreeかRTreeで何とかするしかないようだな。どもです。 後差分を取る方法って今主流な方法でどのような方法があるのでしょうか？ XMLデータの差分を取ってみたいと思うのですがそっち方面は何もわかりません。 113 名前：デフォルトの名無しさん [2005/06/15(水) 08:29:58 ] 立っているビットの位置を調べるアルゴリズムで以下の物より高速な物はあるでしょうか？ int i=1;調べるビット列 bits; while(i<sizeof(調べるビット列)*8+1){ if(bits%2){ cout << i << ","; } bits >> 1; i++; } cout << endl; 114 名前：デフォルトの名無しさん mailto:sage [2005/06/15(水) 11:51:50 ] >>113 while(bits!=0) { 　　if(bits&1!=0) 　　{ 　　　　cout << i << ","; 　　} 　　i++; 　　bits=bits>>1; } cout << endl; 上位がゼロになればそれ以上調べなくてもよい。 ビットが1つしか立ってないなら、二分探索が使えるが。 115 名前：デフォルトの名無しさん mailto:sage [2005/06/15(水) 15:49:29 ] MSBだけ知りたい場合でもバイナリ検索が使えるよ 116 名前：デフォルトの名無しさん mailto:sage [2005/06/15(水) 22:55:01 ] こういう小手先テクはトリッキースレにあった気がする 117 名前：デフォルトの名無しさん mailto:sage [2005/06/16(木) 07:05:10 ] テーブル検索という方法もあるね。 118 名前：デフォルトの名無しさん mailto:sage [2005/06/16(木) 09:34:53 ] >>110 XMLを一旦Prologの項に変換してassertして、 Prologの述語呼び出しや、述語定義の参照述語を使って 部分構造の検索をする。 119 名前：デフォルトの名無しさん mailto:sage [2005/06/24(金) 07:20:01 ] m/123 * 100/101 < x1 < m/123 * 100/99 m/456 * 100/101 < x2 < m/456 * 100/99 m/789 * 100/101 < x3 < m/789 * 100/99 x1, x2, x3 に正の整数が含まれるm > 0の条件は？ 120 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 20:48:02 ] >>110 全文検索系のアルゴリズムが参考になるんじゃない？ suffix tree とか suffix array とか。 ってもう一月以上前か。 121 名前：デフォルトの名無しさん [2005/08/26(金) 11:16:09 ] ここでいいのかな。 パトリシアトライ木とハッシュテーブルを比較したら、 ハッシュの方が速い事が多いんですが、 こんなものでしょうか？（特に検索はハッシュが倍以上速い） なんかパトリシアは苦労して作ったのにこれではちょっと納得いかなかったので。 パトリシアの枝を平衡木にすればマシになるのかな？ 122 名前：デフォルトの名無しさん mailto:sage [2005/08/26(金) 13:38:29 ] なんていうか、苦労と成果は単純に比例する物ではないと思いますハイ。 123 名前：デフォルトの名無しさん [2005/08/26(金) 22:16:26 ] 参考までにベンチ結果を載せておきます。 msは挿入、検索で、検索の速い順に並んでます。 データの種類にもよるでしょうが、自分が対象とするデータはほぼこの順位です。 検索ではTernary Search Trieが健闘してます。 でもtstとtrieはメモリ食います。 >tst (Ternary Search Trie) 55040 件辞書に登録しました。 1268ms 81ms >hash 55040 件辞書に登録しました。 1224ms 82ms >pat (Patricia) 55040 件辞書に登録しました。 1444ms 158ms >trie (Trie) 55040 件辞書に登録しました。 1285ms 224ms 124 名前：デフォルトの名無しさん mailto:sage [2005/08/26(金) 22:25:10 ] >>1 かまいたちの夜２のネタバレｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !! 125 名前：デフォルトの名無しさん [2005/08/27(土) 03:16:43 ] 二次元座標に三点を直線状にならないようにとった。それらがなす三角形が、鈍角か鋭角かを座標情報を使って計算により判定する手続きを述べよ。 126 名前：デフォルトの名無しさん mailto:sage [2005/08/27(土) 03:58:42 ] >>121 patriciaは辞書データ構造に使うんだよ 圧縮が効くしインクリメンタルサーチもできるという特性がある hashはキーがまるごと必要でしょ 127 名前：デフォルトの名無しさん mailto:sage [2005/08/27(土) 04:05:02 ] >>125 中学生か？ 128 名前：デフォルトの名無しさん [2005/08/27(土) 04:28:18 ] >>127 条件分岐は一回以下とする。 129 名前：デフォルトの名無しさん mailto:sage [2005/08/27(土) 06:49:06 ] >>128 普通のパターンだと、条件分岐1回では直角三角形を分離できない（はずだ）けどいいの？ トリッキーにすれば、条件分岐を使わずにできるけど 130 名前：デフォルトの名無しさん mailto:sage [2005/08/27(土) 07:26:28 ] >>125 は宿題の丸投げか？ 自分で考えろよ 131 名前：デフォルトの名無しさん mailto:sage [2005/08/27(土) 10:06:02 ] >>125 こんなものも自分ひとりで解決できないようじゃ先が思いやられるな 132 名前：デフォルトの名無しさん [2005/08/27(土) 10:41:25 ] わかったー cosA・cosB・cosC ＜ 0 なら鈍角だー 133 名前：121 mailto:sage [2005/08/28(日) 06:19:01 ] コード見直しでそれぞれ多少縮まりました。 tstがこれぐらい差が付くとhashの３倍はメモリ食っても使ってみたくなる。 >tst 57260 件辞書に登録しました。 1275ms 63ms >hash 57260 件辞書に登録しました。 1284ms 78ms >pat 57260 件辞書に登録しました。 1450ms 106ms 134 名前：デフォルトの名無しさん mailto:sage [2005/08/28(日) 07:01:14 ] >>129 ピーキーなのきぼん 135 名前：デフォルトの名無しさん [2005/09/16(金) 09:46:27 ] 簡単なプログラムだと思うんですが、 なかなかいい方法が浮かばないんで、何かいい方法があれば 教えてください。 二次元配列のデータ dat[i][j] という200x200くらいのデータ（モノクロ画像データ）があります。 そのデータに対して、i,j面でスムージングをして、new_dat[i][j] を作りたいのですが、どうするのが簡単で良い方法でしょうか？ 簡単にスムージング（もどき）が出来るアルゴリズムをご存知の方が 居られれば教えてください。 136 名前：デフォルトの名無しさん mailto:sage [2005/09/16(金) 10:01:42 ] スムージングって、ローパスとかノイズ除去する奴よね？ 線形のローパスフィルタかけるか、中央値フィルタかけたら？ 137 名前：デフォルトの名無しさん mailto:sage [2005/09/16(金) 10:09:32 ] a00 = 4 a01 = 1 a11 = 1 {lon w 　w = a00*dat[i][j]; 　w+= a01*dat[i][j+1]+a01*dat[i][j-1]; 　w+= a10*dat[i+1][j]+a01*dat[i-1][j]; new_data[i][j] =w /(a00+2*a01+2*a10); }; ってな所から始めたら? 138 名前：デフォルトの名無しさん mailto:sage [2005/10/22(土) 08:57:26 ] アルゴリズムを勉強するのにいい本があったら教えてください 139 名前：デフォルトの名無しさん mailto:sage [2005/10/22(土) 10:44:17 ] xって値を決める時に if (x < 0) x = 0; と x = max(x, 0); はどっちが優れてるの？ 140 名前：デフォルトの名無しさん mailto:sage [2005/10/22(土) 18:50:57 ] >>139 コンパイラによるだろmax関数の解釈とかは、 とりあえずアセンブラの出力を比べてみては。 141 名前：デフォルトの名無しさん mailto:sage [2005/10/22(土) 19:23:39 ] >>139 最上位ビットを0にするのがいいんじゃないの？ 142 名前：デフォルトの名無しさん mailto:sage [2005/10/22(土) 19:45:38 ] >>139 if (x < 0) x = 0; 143 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 14:00:30 ] >140 アセンブラ読めない、頑張ってみた ---if(x<0) x=0; +++x=max(x,0) 　　movl $1, -4(%ebp) - cmpl $0, -4(%ebp) - jns L2 - movl $0, -4(%ebp) -L2: + movl $0, 4(%esp) + movl -4(%ebp), %eax + movl %eax, (%esp) + call _max + movl %eax, -4(%ebp) 　　movl $0, %eax 左の列が言わんとしてる事はわかるんですが、他は字に見えません movlとjnsとcmplとcallがどれだけの奴か知らないので臨場感が伝わってきませんでした。 >142 おすすめのポイントはcallの有無？ >141 おー！と思ったけどビット演算は自分の脳に負荷がかかりました とりあえず右の列 グーグルと一緒にとっつかまえてくる 144 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 20:02:39 ] >>143 max()自体が最適化されてcallがなくなる処理系もある。 >>142 は記述形式がアセンブラに一番近い、つまり 最適化の有無に因らず、どのような処理系でも 「一番速いコード」が生成される「はず」 が根拠だ。 145 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 20:54:55 ] 計ってみればいいんじゃない 146 名前：デフォルトの名無しさん mailto:sage [2005/10/27(木) 07:56:09 ] if (x < 0) x = 0; つまり、ｘが負数ならゼロにするという事は、　２の補数表現であれば xの最上位ビットが１の時に、xを0にすればいい。 よって x := x and (not (x asr 31) ) という計算と等価となる 　・符号拡張命令 　・バレルシフタ 　のどちらかを持っているCPU（x86は両方持ってる）なら 　符号拡張 　NOT 　AND の３ステップで実現出来る 147 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 03:24:19 ] >>146 計算マンセーの前時代的思考方法だな。 xが整数型であると、どこに書いてある？ という、無駄な突っ込みは別として、その手の置き換えは 「必ず計算が実行される」と言う面から考えると、速くも、 また、美しくもない。 if (x < 0) x = 0; は、しなくとも良い計算や代入は発生しない。 そう言った意味で x := x and (not (x asr 31) ) は、問題外。 148 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 06:29:38 ] 浮動小数点型でも符号ビットは最初にあるから同じ方式でいけるぞ。 だからもし突っ込むなら、　２の補数の方だろう 149 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 07:31:16 ] ２の補数表現でも１の補数でも　if (x < 0) x = 0; という演算なら問題ない。 つまり >>147の前半の突っ込みは無駄ではなくて、無知なツッコミ。 後半もちょっと変 if (x < 0) x = 0; 　は表現であって、実際に分岐を指示しているわけではない。 この計算は賢いコンパイラなら 最近のX86に対応しているなら 条件付代入命令に変換される可能性が高い CMP CMOVS となる。 ちなみに、浮動小数点命令にも条件付代入命令はある さて、分岐と演算命令のどちらが高速という話なら、 分岐命令は並列演算の妨げとなるが 演算命令は並列化可能な部分は並列化される故に 命令数が多少多くても現在でも分岐より演算が速く、将来はもっと高速になる可能性が大 並列処理のことを言わず、一昔前のCPUや現在のH8やSHでは 分岐命令は演算命令２〜４つ分のコストを支払わされるのが普通 なお、この部分　x := x and (not (x asr 31) )　も　条件代入も並列化出来ないが その次に同じような演算があれば先読み実行される可能性があるという事 150 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 16:21:10 ] どちらにしろ、ｘが32bitだという前提がないと成立しない x := x and (not (x asr 31) ) は、問題外ということでよろしかったですか？ 151 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:14:49 ] >>150 それがそのまま通る言語がそもそもないだろう。　あほか？ 152 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:23:32 ] もともと>>139のような比較自体に意味がないし、 (x and (not (x asr 31))) が格別優れているわけでもなかろが、 >>150 ええと、>>147はまったく意味の無い記述とされてるし、 32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、 ようするにalgorithmなり記述を評価する能力無し、という告白でよろしいか? 153 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:30:27 ] まあ、少なくとも x := x and (not (x asr 31) ) は、アルゴリズムじゃなくて「技」だしなあ。 154 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:38:39 ] x := x and (not (x asr　sizeof(x) ) 155 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:48:12 ] という事で、C言語なら3項演算子を使え。　バカなコンパイラならインラインでCMOVを使えと 156 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 17:50:29 ] ABS　マクロなんかは、論理演算に変換されるね 覚えてないけど、符号拡張＋XORだったかな？ 157 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:41:28 ] >>152 ＞ 32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、 さすがに、そんなコンパイラは使いもんにならないと思う。 31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する となると、マジヤバイ。 >>154 えーと、１年生ですか？w 158 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:54:11 ] >>157 >31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する !!!? バカ、マジヤバス。低脳乙www 終了。 159 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:54:21 ] x := x and (not (x asr BitSizeOf(x) ) 160 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:55:31 ] x := x and (not (x asr log2(INT_MAX) ) 161 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 18:56:51 ] x := x and (not (x asr ∞ ) ) 162 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 19:14:01 ] x =( abs(x) + x ) /2 163 名前：デフォルトの名無しさん mailto:sage [2005/10/28(金) 23:28:42 ] >>158 えーと、幼稚園ですか？w 164 名前：デフォルトの名無しさん mailto:sage [2005/10/29(土) 00:12:48 ] >>157,163 おまえがなwww 165 名前：デフォルトの名無しさん [2005/11/03(木) 23:15:11 ] ( ´∇｀)y-~~~ へぇ 166 名前：デフォルトの名無しさん [2005/11/08(火) 00:13:18 ] B-Treeを自分で書いて理解したいのですが、難しくてよくわからん。 アホ向けに解説してあるサイトか書籍ないでしょうか。 167 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 00:33:13 ] >>166 ttp://unit.aist.go.jp/itri/knoppix/ 168 名前：デフォルトの名無しさん [2005/11/08(火) 01:55:08 ] >>167 クノッピでBtreeが理解できるの? 169 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 05:05:57 ] >>164あたりまで ともかくそんな高度な話題を論じれる貴方達を尊敬する。 俺にはついていけないよ。 170 名前：デフォルトの名無しさん mailto:sage [2005/11/09(水) 00:00:21 ] >>166 読み辛いのなら、デバッガを使って変数の値を追っていくといい 171 名前：デフォルトの名無しさん [2005/11/10(木) 01:14:30 ] すいません、「Universal hashing」について教えてくだせぇ。 lecture-wiki.ecc.u-tokyo.ac.jp/index.php?uonoue%2FJSR%2F11 このページにもその部分だけ書かれてなくて困ってます。 「平方採中法」とは違うものなんでしょうか？ 172 名前：171 [2005/11/10(木) 04:11:50 ] 自己解決しました 173 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 19:12:43 ] 平衡木のAVL木において，バランスが崩れた場合に，単一回転と二重回転 によってバランスを保つことを勉強しました． 単一回転と二重回転の選択の判断ってどうしてるんですか? 174 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 20:25:30 ] >>173 その勉強した内容は、隅から隅まで読んでみたのかな？ たとえば次のページみたいに、普通は書いてあるよ。 ttp://lecture.ecc.u-tokyo.ac.jp/~yamaguch/pub/cp2-8/what-is-search-avl.html 175 名前：& ◆i.twkzJbf. mailto:sage [2005/11/13(日) 21:41:13 ] >>174 大変，ありがとうございます! 図書館にあるアルゴリズムの本をあさり，「こういうパターン の時は単一回転」という図は掲載されていたのですが，明確に 文章で書かかれているものが，無かったんです． 上記のURL には明確に文章で記載されていたので，理解できました． ありがとうございました． 176 名前：デフォルトの名無しさん mailto:sage [2006/02/05(日) 09:40:09 ] 2 177 名前：デフォルトの名無しさん [2006/02/05(日) 09:41:09 ] 今春、情報処理試験受けてきます 178 名前：デフォルトの名無しさん mailto:sage [2006/02/15(水) 22:05:35 ] 誰かイージスシステムのアルゴリズムうｐしてよ。 できればCASL2形式のソースコードで頼む。 179 名前：デフォルトの名無しさん mailto:sage [2006/03/06(月) 23:50:20 ] GDIのArcToってどういうアルゴリズムで実装されているかご存知の方いませんか？ また、ArcToを実装する場合、Google等でそのアルゴリズムの名前を検索するとヒット するようなメジャーなアルゴリズムってあるのでしょうか？ 今、DirectXを使用してVRAMに直接弧を描画する関数を作っています。 楕円描画のアルゴリズムを使用して、弧を描く関数自体はできたのですが、問題点として、 �@　条件分岐が多くスパゲッチーなコードになる �A　○○のアルゴリズム、とかの名前で、世間一般に知られているかが分からず、 　　　スパゲッチーなコードでも、その内容を見た人が調べて把握できるかが不安。 今後の保守性に不安があるので、弧の描画に用いられている一般的な アルゴリズムがあるなら、そちらに揃えたいです。 ないなら、多少速度を犠牲にしてもGDIのArcToを使ってしまおうかと悩みちゅうです。 180 名前：デフォルトの名無しさん mailto:sage [2006/03/08(水) 11:31:54 ] DDA を使ってるなら、Bresenham　アルゴリズム とでも書いておけば判るだろう 181 名前：デフォルトの名無しさん [2006/04/05(水) 02:28:16 ] ヒープを使えば最小値（もしくは最大値）を迅速に取り出すことができます。 しかし、ある条件を満たしている間は最小値を、 そうでない場合は最大値を取り出すとなると、効率のいい方法が思いつきません。 線形探索で最大値を探し出すことになってしまいます。 （ソースコードは以下のURL） ttp://anotherred.hp.infoseek.co.jp/cgi-bin/src/up1346.txt なにかいい方法は無いものなのでしょうか。 182 名前：デフォルトの名無しさん [2006/04/05(水) 02:32:24 ] (181の続き） 某ソフトのある部分と流れがそっくりですが・・・ そっくりそのままコピペしたわけではないので、 そこらへんは目をつぶっていただけるとありがたいです。 183 名前：デフォルトの名無しさん mailto:sage [2006/04/05(水) 05:54:32 ] >>181 ようするに、最大値と最小値の両方を高速に取り出せるデータ構造か。 両方 O(1) で出来るものはしらんが、両方 O(log n) でできるものならB木の類。 184 名前：デフォルトの名無しさん mailto:sage [2006/04/05(水) 12:56:41 ] あとは、データを最初にソートしておくか。 185 名前：デフォルトの名無しさん [2006/04/05(水) 13:19:15 ] >>183 木構造ですか・・・ たしか、木構造を使用したデーターベース関連のソースがあるので、 速度のことさえ気にしなければいけそうですね。 ちょっとベンチマークを取ってることにします。 わざわざ答えてくださりありがとうございました。 >184 二分ソートを使うとなると、かえって遅くなりそう・・・ 適切な位置を探すのにO(log n) データの移動に最悪でO(n) 平均はいくらぐらいか知らないけど。 186 名前：デフォルトの名無しさん [2006/04/23(日) 23:18:33 ] 質問です。 0<= x < N までの値を巡回する式を作りたいのです。 用途としては、選択肢を指すカーソルが一番下まで行った時、さらに下ボタンを押すと一番上を指すように。 一番上まで行った時にさらに上ボタンを押すと、一番下を指すように。 という使い方です。 x = (x + N) % N; でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。 Nが2の乗数なら、マスクをとるという方法も思いつくのですが…。 何か定型的な方法はありますでしょうか？ x = ((x % N) + N) % N; でもとりあえず良いのですが、かなり冗長に見えます。 187 名前：デフォルトの名無しさん mailto:sage [2006/04/23(日) 23:39:39 ] >>186 > でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。 つか、xが-N未満になりうる時点でバグってると思うが？ 0<= x < N なんでしょ？ 188 名前：デフォルトの名無しさん mailto:sage [2006/04/23(日) 23:51:29 ] もう面倒だから素直に分岐つかえば x % n + (x < 0 ? n : 0) 189 名前：デフォルトの名無しさん [2006/04/24(月) 00:08:33 ] >>187 説明が下手ですいません。 xになにかしらの数が代入され、それをうまく 0<=x<N に丸め込みたいのです。 int hoge(int x) { while(x < 0) x += N; x %= N; return x; } とお考えください。 >>188 その式だと、ちょっとやりたいこととは違うようです。 whileやifを使わずに綺麗にやる式があれば…と思っているのですが 190 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 00:46:26 ] >>188 それ負のとき0が5になる 191 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 00:50:35 ] 188のもあってるが、 ＞x = ((x % N) + N) % N; のほうが分岐無いだけ速くねーか 192 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 06:33:35 ] xは負数としてもそんな極端な負数にはならないんでしょ？ NM=INT_MAX/N; として x = (x + NM) % N; でいいんじゃないの？ 193 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 16:25:32 ] いまいちやりたいことがわからんが、 UIなら計算量をケチる必要性はないので多少冗長でもかまわないのでは。 xの初期値として x = (x + N) % N; が計算できて、xは以降、0<=y<N、という値が足されたり引かれたりするだけという状況を仮定すると、 (>>186だとそういう状況ですよね。xに乗除算は入ってこない) x-yを行うときはx<yならばNを足してからyを引くでいいんでないかい。 除算よりも比較の方が圧倒的に速いから。 194 名前：デフォルトの名無しさん mailto:sage [2006/04/24(月) 16:36:30 ] いや、それなら基本的に　 xが-N未満になど、普通はなりようがないのだ。 x <-Nになる事はないのだから 用途的には x = (x + N) % N; で何の問題もない。 過剰仕様といえよう。 もし、xがEPROMとかに保存されてる間にゴミと化しても変な事にならないようにという事なら x を　符号無数とすればいい 195 名前：デフォルトの名無しさん mailto:sage [2006/04/25(火) 00:18:10 ] 360度 0〜4095の値をとる円の時に、この問題に悩むな。 -500000とか入れられたときに、0〜4095に直すとどうなるか。みたいな。 DWORDにする手もあるんだが、Javaだと符号intしかないからなぁ・・ 196 名前：デフォルトの名無しさん mailto:sage [2006/04/25(火) 06:36:53 ] 0〜4095なら　4095とのand でいいんだから、悩まないぞ 197 名前：デフォルトの名無しさん mailto:sage [2006/05/16(火) 22:52:10 ] テキストの類似度を判定するアルゴリズムって、なんかいいのないかな。 leveshteinとかsimilar_textだと、"abcdefgh"と"hgfedcba"の類似性を かなり低く見積もってくれたりするんだけど、人間の直感にマッチするような アルゴリズムってないもんですかね。 198 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 10:17:58 ] 人の直感がそれぞれだからねぇ 199 名前：デフォルトの名無しさん mailto:sage [2006/05/17(水) 16:01:49 ] >>197 俺の直感だと、その2つは似てない 200 名前：デフォルトの名無しさん mailto:sage [2006/05/20(土) 21:35:30 ] Oliver [1993] とか。 similar_text ttp://jp2.php.net/manual/ja/function.similar-text.php 201 名前：デフォルトの名無しさん mailto:sage [2006/05/23(火) 17:06:12 ] SoundEx　とかはどうなの？ 202 名前：デフォルトの名無しさん [2006/05/30(火) 16:49:01 ] 複数の候補からランダムに選択させたいんですが、 そこに重み付けを導入する場合って、どんなアルゴリズムがあります? 203 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 07:54:15 ] 誰か解答を求む！ C で文字列を比較するのは (*(int *)s1) == (*(int *)s2) これのほうが早い？ 204 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 07:57:42 ] >>203 ここで聞く前に試したほうが早いし確実だと思うのは気のせいでしょうか 205 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 09:25:22 ] 速いっつーか，間違ってねえか？ 206 名前：203 mailto:sage [2006/06/08(木) 09:29:08 ] すいません、ミスです 207 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 10:42:46 ] 切れ目探しで鬱になったけど早い事は早かった 間違ってるの？ 208 名前：207 mailto:sage [2006/06/08(木) 10:47:38 ] ミスｗ 209 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 13:58:46 ] なるほど、疾いよ、strcmpの1/10になれる これどのCPUでもいけるの？ 210 名前：デフォルトの名無しさん mailto:sage [2006/06/08(木) 15:47:53 ] まだ続けるのか？ 211 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 15:26:03 ] 奥村先生は放送大学に出演している。 212 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 15:47:54 ] >>211 ナイス情報サンクス｡ LATEXとＪＡＶＡかー｡ アルゴリズムキボンヌだなぁ｡ 213 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 16:02:00 ] >>212 「JAVAによるアルゴリズム事典」はpLaTeXで書いたとちゃっかり宣伝していた。 214 名前：デフォルトの名無しさん mailto:sage [2006/06/25(日) 00:14:43 ] B+-treeに関して説明してあるお薦めサイトか、 理解しやすいオープンソースプログラムってあります？ 215 名前：デフォルトの名無しさん mailto:sage [2006/07/06(木) 08:08:55 ] B木までは説明してるサイトでもB+やB*は名前がでてくるかどうかって感じだな 216 名前：デフォルトの名無しさん mailto:sage [2006/07/06(木) 15:40:55 ] 奥村先生はJAVAが出て来たとき世界は統一されたと思ったらしい。 217 名前：デフォルトの名無しさん mailto:sage [2006/08/06(日) 13:40:04 ] さすが学者先生だな。 何かで世界統一されることなんてないよ。 218 名前：デフォルトの名無しさん mailto:sage [2006/08/06(日) 17:01:29 ] >>216 ソースは？ 解釈が間違っている可能性がある。 219 名前：デフォルトの名無しさん mailto:sage [2006/08/06(日) 20:40:34 ] >>218 放送大学で言っていた。 220 名前：デフォルトの名無しさん [2006/08/12(土) 09:04:26 ] 遺伝的アルゴリズムは？ 221 名前：デフォルトの名無しさん mailto:sage [2006/09/02(土) 16:52:02 ] 　　 （　・∀・）　　　|　|　ｶﾞｯ 　　と　　　　）　 　 |　| 　　　 Ｙ　/ノ　　　 人 　　　　 /　）　 　 < 　>__Λ∩ 　　 ＿/し'　／／. Ｖ｀Д´）/ 　　（＿フ彡　　　　　 　　/ 222 名前：デフォルトの名無しさん mailto:sage [2006/09/14(木) 01:08:00 ] GA ってこと? 223 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 22:57:32 ] 格子点を、原点からの距離が小さい順に数え上げていくアルゴリズムをしりませんか？ 簡単の為、問題を２次元にします。 この時、 (0,0) (1,0) (0,1) (1,1) (2,0) (2,1) (1,2) (2,2) ・・・・・・・ という配列を得たいのです。 思いついた単純な方法は、 for(i =1; i < N ; i++) for(j = 1 ; j < N; j++){ d = i**2 + j**2 arry.push([i,j],d) } sort arry by d aryy.each { a printt a } という方法ですが、あまりスマートとはいえないし、 同じ距離d (= 1)をもつ点(1,0),(0,1)がこの順で並ぶとは限らないという欠点があります。 （同じ距離を持つ(x,y)なら　x>=yというを満足する点からで並んで欲しい) 224 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:03:57 ] >>223 「安定なソート」でぐぐれ。若しくはC++のstd:stable_:sortで関数オブジェクトに x>=yという条件を含めれば簡単。 225 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:04:27 ] ×std:stable_:sort ○std::stable_sort 226 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:33:51 ] おもしろいな 群論とか使えばいけそうだが。。。 俺の知識では無理ｗ 227 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:42:44 ] #include <iostream> #include <vector> #include <algorithm> #include <utility> struct MyComp { bool operator()(const std::pair<double, double>& p1, const std::pair<double, double>& p2) { double d1 = p1.first * p1.first + p1.second * p1.second; double d2 = p2.first * p2.first + p2.second * p2.second; if (d1 < d2) return true; else if (d1 > d2) return false; else { // d1 == d2 if (p1.first < p1.second && p2.first > p2.second) return false; else return true; } } }; struct MyOut { void operator()(const std::pair<double, double>& p) { std::cout << '(' << p.first << ',' << p.second << ')' << std::endl; } }; 228 名前：デフォルトの名無しさん mailto:sage [2006/09/17(日) 23:43:16 ] int main() { double a[][2] = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {1, 2}, {2, 2}}; std::vector<std::pair<double, double> > dp; for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) dp.push_back(std::make_pair(a[i][0], a[i][1])); std::sort(dp.begin(), dp.end(), MyComp()); std::for_each(dp.begin(), dp.end(), MyOut()); } (1, 0), (0,5, 0) なんてペアがある場合は考慮してない。 229 名前：デフォルトの名無しさん mailto:sage [2006/09/18(月) 00:43:40 ] ヴォースゲー！ 230 名前：デフォルトの名無しさん [2006/09/20(水) 15:41:34 ] 複数の矩形が存在するときに、それぞれの重複を求めるアルゴリズムを考えています。 最終的には、与えられた領域を重複の無い横に細長い形の矩形で表現したいと思っているのですが、 これを表現するための良いアルゴリズムはあるでしょうか？ 231 名前：デフォルトの名無しさん mailto:sage [2006/09/20(水) 22:14:34 ] >>230 スキャンラインコンバージョン？ 232 名前：デフォルトの名無しさん mailto:sage [2006/09/20(水) 23:44:29 ] >>230 おれは力技でやった 233 名前：デフォルトの名無しさん [2006/09/24(日) 15:55:30 ] This is a pen! 234 名前：デフォルトの名無しさん mailto:sage [2006/09/24(日) 17:39:47 ] >>230 平面走査で解ける．計算量は O( n log n + k )， ただし n は矩形の数，k は分割線の個数． 簡単のため，どの矩形の上下の y 座標にも，同じものはないとする． アルゴリズムを述べた後にこの制限は外す． 1. すべての矩形の上側の辺と下側の辺を，    y 座標の昇順に並べられたキュー Q に突っ込む． 2. while Q が空でない: 3.   e = Q.pop() 4.   if e が下辺         then T に対応する矩形を挿入         else T から対応する矩形を削除 5.   T に入っている矩形で，e と交わるものを切断する． ここで T は平面走査構造．x でソートされた平衡二分探索木を用いると 4 が O(log n) で行える．5 は e の左側の点で二分探索し，交わる領域を 線型に探すと O(log n + k') で行える．ただし k' は e と交わる矩形の数． 同じ y 座標を許す場合は，一括に処理できる辺を蓄えておいて， 一度しか切断しないようにすれば対応できる． 235 名前：デフォルトの名無しさん [2006/09/30(土) 15:33:44 ] 斜め楕円の描画 void DrawEllipse(HDC hdc, double dFx1, double dFy1, double dFx2, double dFy2, double dLen ) { double a,b,c,d,A,B,C,L,M,x; int sx,sy;a = dFx1; c = dFx2;L = dLen; A = L*L-(a-c)*(a-c); BOOL bFlg = TRUE; for(int y=0; y<300; y++){ b = y-dFy1;d = y-dFy2; M = L*L-a*a-b*b-c*c-d*d; B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c); C = (a*a+b*b)*(c*c+d*d)-M*M/4; if(B*B-4*A*C>0){ x = (-B+sqrt(B*B-4*A*C))/(2*A); if( bFlg ){ bFlg = FALSE; sx = x;sy = y; MoveToEx(hdc,x,y,NULL); } LineTo(hdc,x,y); } } 236 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 15:34:17 ] 続き for(int y=300; y>0; y--){ b = y-dFy1;d = y-dFy2; M = L*L-a*a-b*b-c*c-d*d; B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c); C = (a*a+b*b)*(c*c+d*d)-M*M/4; if(B*B-4*A*C>0){ x = (-B-sqrt(B*B-4*A*C))/(2*A); LineTo(hdc,x,y); } } if( !bFlg ){ LineTo(hdc,sx,sy); } } あげちまたスマソ 237 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 15:35:42 ] 標準に存在しないからって力技で自作したんだがどうだろう ベジエ勉強したほうが良いのかな 238 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 19:41:45 ] せめて入力変数の意味くらい書いてくれ 239 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:01:13 ] >>237 ベジエ曲線で完全な楕円は表現できない 近似はできるけどな 240 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:20:49 ] >>238 HDCはおいておいて、残りの5つは 焦点の座標（２つ）と長径 >>239 実用に耐えるなら近似で良いんだけどね 241 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:59:26 ] 用途にもよるが、俺ならサンプル点の密度が極端に偏るアルゴリズムは使わないな。 242 名前：デフォルトの名無しさん [2006/10/22(日) 19:47:46 ] 最大遅れ最小スケジューリング (minimization of the maximum lateness) ってあるけど、 この最大遅れの「最大」ってなんなの? 遅れの合計を最大化したものを最小化? 意味がわからん。 エロい人教えて 243 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 19:51:50 ] 最大の遅れを最小にする．たとえば ・最初の仕事で30分遅れてあとの仕事はジャスト．（最大遅れ30分） ・全部10分づつ遅れる．（最大遅れ10分） の二つだったら，後者のほうが良いとするスケジューリング． 244 名前：242 mailto:sage [2006/10/22(日) 19:55:00 ] >>243 なるほど!トンクス 245 名前：デフォルトの名無しさん [2006/10/31(火) 16:55:59 ] $a=array('red','blue','yellow','green'); $b=array('white','blue','yellow','green'); $c=array('green','red','yellow','cian','black'); $a,$b,$cのどれにも存在する要素の'yellow','green'を取得するソースをPHPで。 246 名前：デフォルトの名無しさん [2006/11/02(木) 01:42:06 ] PHPで何？ 247 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 11:51:23 ] >>245 array_uintersect 248 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 19:21:30 ] 二つのソート済みの配列が与えられていて（合計の要素数はN） N個の要素からメディアンを計算量O(LogN)で求めるアルゴリズムを教えてください。 ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf www.cse.ust.hk/faculty/scheng/comp271h/assign/hw2_sol.pdf 検索して出てきたこの二つのPDFにある擬似コードをCで実装してみたんですけど 何度かテストしたらどちらも時々スタックオーバーフローが発生してしまいました。 （正しい結果を返すときもありました） 二つの配列の長さが同じ場合にしか使えないコードでもいいのでお願いします。 249 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 20:57:41 ] >>248 2つのソート済み配列をA,Bとする。 Aの中央値とBの中央値を比較する。 Aの方が大きいとすると、Aの小さいほうの集合とBの大きいほうの集合を残す。 以下これを反復する。1回の反復は配列の要素を指定して比較するだけだから定数オーダー。 反復ごとに要素数が半分になるから反復回数はlog N回 250 名前：248 mailto:sage [2006/11/03(金) 03:05:44 ] >>249 ありがとうございます。こんな感じになりました。 int median_search(const int *A,const int *B, int n){ 　　int m; 　　if(n==1) 　　　　return A[0]>B[0]?A[0]:B[0]; 　　m = n>>1; 　　if(A[m]>B[m]) 　　　　return median_search(A,B+m,m); 　　return median_search(A+m,B,m); } nは配列AとBの長さです。 ソート済みの配列AとBをマージした長さ2nの配列をCとするとこの関数はC[n]を返します。 A[0]>B[0]?A[0]:B[0];の部分を、A[1]<B[1]?A[1]:B[1];にすればC[n+1]を返します。 251 名前：248 mailto:sage [2006/11/03(金) 03:14:48 ] 連続投稿すみません・・。 >>250は配列の長さnが２のべき乗の場合しか使えないようですね・・。 もうちょっと考えてみます・・。 252 名前：デフォルトの名無しさん [2006/11/04(土) 02:07:10 ] バルブソート の検索結果 約 98,900 件中 1 - 10 件目 (0.75 秒) 253 名前：デフォルトの名無しさん mailto:sage [2006/12/01(金) 10:57:06 ] "バルブソート" の検索結果 約 73 件中 1 - 6 件目 (0.04 秒) 最も的確な結果を表示するために、上の6件と似たページは除かれています。 254 名前：デフォルトの名無しさん mailto:sage [2006/12/26(火) 19:17:24 ] バルブソート の検索結果 約 87,100 件中 1 - 10 件目 (0.29 秒) 255 名前：デフォルトの名無しさん mailto:sage [2006/12/27(水) 11:18:50 ] "パブルソート" の検索結果 2 件中 1 - 2 件目 (0.25 秒) 256 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 09:05:20 ] ラストリゾート の検索結果のうち 日本語のページ 約 159,000 件中 1 - 10 件目 (0.14 秒) 257 名前：デフォルトの名無しさん [2006/12/30(土) 16:37:47 ] 桃太郎電鉄の「いけるかな？」の判定アルゴリズム教えてくれ。 258 名前： 【吉】 mailto:sage [2007/01/01(月) 12:18:14 ] ただの幅優先探索じゃね 259 名前：デフォルトの名無しさん mailto:sage [2007/01/05(金) 00:45:08 ] 使える素子に制限がある、ある動作をする組み合わせ回路の探索アルゴリズムって何かの本にかいてますか？ 例えば、NOT2個とAND複数、OR複数個だけで並列な独立した3つのNOT回路と等価な回路を探すアルゴリズム。 「思考する機械コンピュータ」という本に載っていた問題です。(この条件が) この間バックトラックでやったらあっさりできましたが・・・ 260 名前：デフォルトの名無しさん mailto:sage [2007/01/05(金) 07:45:57 ] >>259 加算器ぐらい合成できないと意味はない 261 名前：デフォルトの名無しさん [2007/02/13(火) 08:13:38 ] 総当たりなんじゃ・・・ 262 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 08:54:07 ] >>261 証明 263 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 15:00:13 ] 素子の種類の条件を満たす真理値表を小さい方から総当たりだな。 ちなみに「条件を満たす回路が存在しない」ことの証明は 総当たりで調べても見つからなかったことを言う以外に方法はない。 典型的なNP問題。 264 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 19:51:44 ] >>263 総当りでしか証明できないならNPに入っていないじゃん。 探査空間Pで十分だからPSPACEには入っているけど。 265 名前：デフォルトの名無しさん mailto:sage [2007/02/14(水) 16:25:03 ] ＞総当りでしか証明できないならNPに入っていないじゃん。 ？ 266 名前：デフォルトの名無しさん mailto:sage [2007/02/14(水) 18:10:31 ] >>265 NP=ある多項式長の補助入力が存在してPで解ける 総当り→補助入力は多項式長でないからダメ 補問題であるある場所にいけるかは 道順の例を補助入力として与えればこれは多項式長であり、明らかにPで検証可能。 したがって補問題はNP。 補問題がNPだから、PSPACEよりも狭いco-NPに入る。 267 名前：デフォルトの名無しさん mailto:sage [2007/02/15(木) 03:59:35 ] むずかしいはなしはきらいです 268 名前：263 mailto:sage [2007/02/15(木) 06:14:34 ] 間違った。 等価な回路を探すアルゴリズムがNPで、存在しないことの証明はNPじゃない。 269 名前：259 mailto:sage [2007/02/15(木) 16:03:39 ] もしアレでしたらソースコードUPしますけど・・・ 270 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 00:56:55 ] いらね 271 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 04:04:04 ] いる 272 名前：259 mailto:sage [2007/02/16(金) 04:34:16 ] 見たら吐くかも ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/3659.c 273 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 07:39:57 ] #define NOTA まで読んだ。 274 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 07:40:39 ] なんだよ、ノタって。ふつーNOT_Aだろ。 275 名前：デフォルトの名無しさん mailto:sage [2007/02/18(日) 16:31:13 ] 某板よりコピペ 多数のオブジェクトの衝突判定を並列化する方法 移動後の座標をボクセルに振り分ける。 1つのボクセル内に存在するキャラを総当たりで衝突判定。 処理の順序としては、移動、振り分け、衝突判定、衝突処理。 これで処理を並列化できる。 もう少し詳しく言えば、衝突判定をしやすくするために、 ボクセルに振り分ける時点で座標値などをボクセルごとの一時バッファに複製しておく。 これにより巨大なバッファをLSにロードする必要がなくなる。 衝突の連鎖については次フレームに回す。それで結果的には再帰処理になる。 普通は移動後に振り分けるというより ボクセル内のオブジェクトを管理するバッファを常設しておいて 移動でボクセル外に出たときだけバッファの更新をするでしょ。 276 名前：デフォルトの名無しさん mailto:sage [2007/02/19(月) 01:19:29 ] 類似の手法は物理計算では常識。 ボクセルよりも適当な空間木を用いたほうがよいと思う。 オブジェクトの分布や座標空間にもよるが、計算量の 意味で速度が改善されることも珍しくない。 277 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 03:50:22 ] >>274 ふつーNOT_Aなのは分かる しかし、Shiftを押しながら「ろ」キーを押す手間が面倒なのも分かってしまうんだな 俺はどっちを応援すればいいんだ？ 278 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 06:10:11 ] ふつーSHIFT+- 279 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 16:04:22 ] その点以外の感想が欲しい今日このごろ 280 名前：デフォルトの名無しさん mailto:sage [2007/02/22(木) 07:38:32 ] C言語のソースは読むきしねぇ コメントぐらいかこうね 281 名前：デフォルトの名無しさん [2007/07/03(火) 15:59:46 ] 整数のリストを入力とし整数のリストを出力する関数nayose を、 Minimal を用いて次のように定義する。(ただしプログラム中、A or B 　はA とB のうち少 なくともどちらか一方がtrue のときtrue を返し、それ以外のときはfalse を返す論理演算 である。) 以下の問に答えよ。 fun member x lst = case lst of [] => false | hd::tl => hd=x or (member x tl) end; fun nayose lst = case lst of [] => [] | hd::tl => if (member hd tl) then (nayose tl) else hd::(nayose tl) end; (1) 関数nayose はどのような計算を行う関数か簡潔に答えよ。 (2) 長さがn のリストに関数nayose を適用したときの計算量をO(f(n)) の形で表せ。 (3) あらかじめ整列された整数のリスト（重複があってもよい）を入力とし、関数nayose と 同様の結果を出力する関数で、入力リストの長さがn のときの計算量がO(n) となるよ うな関数nayose2 を、Minimal プログラムで示せ。関数nayose2 がnayose と同様の結 果を出力する理由を簡単に説明すること。 (関数nayose2 は、整列されていない入力についてはnayose と異なる結果を返しても良 い。） 282 名前：デフォルトの名無しさん mailto:sage [2007/07/05(木) 07:23:15 ] 宿題は宿題スレへ 283 名前：デフォルトの名無しさん [2007/09/08(土) 02:49:46 ] age 284 名前：デフォルトの名無しさん mailto:sage [2007/09/10(月) 15:56:14 ] 反駁環境における生成器 % 何も生成しない生成器 repeat. repeat :- repeat. % 類型 リストからの生成 member(A,[A|_]). member(A,[_|R]) :- member(A,R). % 類型 リストの分解 append([],X,X). append([U|X],Y,[U|Z]) :- append(X,Y,Z). 285 名前：デフォルトの名無しさん mailto:sage [2007/09/11(火) 03:52:19 ] % 生成器のつづき % 連続整数の生成器(昇順) for(N,N,E) :- N =< E. for(S,N,E) :- S =< E,S2 is S+1,for(S2,N,E). 286 名前：デフォルトの名無しさん mailto:sage [2007/09/23(日) 09:39:58 ] 他所のHPの書きこみなんだけど > よく知られている問題ですが、一般に、Ｎ個のもののソーティング(順序付け)の > ための必要最少限の比較回数はlog2(Ｎ！) ≦ ｋを満たす最小の整数ｋです。 って本当? ていうか必要だけど充分じゃないっていう意味で言ってるんだろうか. 287 名前：アルゴリズム初心者 [2007/10/13(土) 20:48:56 ] ツリー構造(あるディレクトリ以下のファイル・フォルダ群）同士の差分を取得したいのですが、 そういったアルゴリズムの解説お願いします。 もしくはためになりそうなキーワードやウェブサイトを教えてください。 ３年くらいプログラミングはしているのですが、画面を作るばかりで 頭を使うようなことは一切やったことが無いので詰まってしまいました。。。 288 名前：デフォルトの名無しさん mailto:sage [2007/10/13(土) 21:04:06 ] アルゴリズムも何も、diff -rじゃダメなのか? 289 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 00:14:49 ] >>287 WinMergeをダウンロードしてくるといいよ 290 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 00:39:33 ] WinMergeはサブフォルダごと一気に比較すると、全部一画面で表示するから 見にくくてしょうがない。 DFみたいにフォルダごとに見れるようにしてくれよ。 291 名前：アルゴリズム初心者 [2007/10/14(日) 07:53:31 ] プログラムの中で使いたいのでこのすれにきています。そういうライブラリがあれば教えてください。 292 名前：アルゴリズム初心者 [2007/10/14(日) 07:59:15 ] ちなみにJavaです。 293 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 08:56:05 ] diff のソース読めばいいんじゃないか？ 294 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 09:55:04 ] >287 さすがに手作業で同じ事はできるよな？ じゃ、まずは簡単な例で手作業でやってみよう。 次に、どういう手順で行ったか書き下してみる。 で、人間なら分かるけど計算機には分からないといった about なところを詳細化する。 最後にコードに落としてやれば OK だ。 この程度で、アルゴリズムだとかライブラリだとか情報源とか探してるようだと いつまでたってもそのレベルから抜け出せないよ？ 295 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 10:34:59 ] >>291 system("diff -r dir1 dir2") 296 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 10:39:33 ] ある範囲内のユニークな乱数列を作る方法を教えてください 297 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 12:55:17 ] >>296 どういう範囲内でユニーク？ ユニークなことを確実に保障するのって難しいよ。 298 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 13:21:17 ] >>297 範囲というか、DBの正規化レコードのテストに使うので1〜1000万ぐらいで。 乱数をハッシュテーブルに登録してユニークな乱数列を作れないかと 思ったんですが、目的レコード件数分まわしても、重複で抜け番号が 出てくるので、一気に全部埋まる方法ないかなと。 299 名前：296 mailto:sage [2007/10/14(日) 13:24:14 ] 逆に、整列されたスカラ値の配列やリストを、 ランダムに混ぜる方法でもいいです。 300 名前：296 mailto:sage [2007/10/14(日) 13:28:03 ] あと、再現性が必要なのでシード値を取れる方法が好ましいです。 301 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 13:50:17 ] ユニークである必然性あるのかな？ 全数チェックしたらｗ 302 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 16:24:11 ] >296 多分、ユニークな乱数列、の意味が人によって違っているような気がする。 「乱数列」がユニークであることを望んでいるのではなくて、乱数列中に表れる数値がユニーク(重複しない) ってことなんだよね？ C++ で良ければ(アルゴリズムの説明にならないけど)、>299 で random_shuffle() 使うのが一番簡単かと。 あるいは、random(N) を 0〜N-1 の整数を発生する(シード値をとれる)疑似乱数生成関数として、a[0]〜a[N-1] にたいして、 for(i=0;i<N;++i) {     idx = random(N);     tmp = a[i];     a[i] = a[idx];     a[idx] = tmp; } で、いいんじゃない？ 303 名前：296 mailto:sage [2007/10/14(日) 20:45:00 ] あー その通りです。 ありがとうございました。 304 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 20:49:40 ] >>302 そのコードだと均等に混ざらない（すなわち、全ての可能なケースが等確率で出ない）。 正しくはこんな感じ for(i=0;i<N;++i) { 　　idx = random(N-i) + i; 　　swap(a[i], a[idx]); } 305 名前：デフォルトの名無しさん mailto:sage [2007/11/13(火) 01:55:34 ] URIの一致箇所検出に 最適なアルゴリズムってどれですかね？ 306 名前：デフォルトの名無しさん [2007/11/20(火) 17:17:18 ] >>305 質問の意味がよくわからない 最長共通文字列？ ところで、良いアルゴリズムというかロジックが思い浮かばないんだけど何か良いの無いかな。 配列をPivotとの大小関係で三つに区切る。 C++っぽい擬似コードで書くとこんな感じ under = partition( Begin End < Pivot ) partition( under End == Pivot ) これより計算量係数を下げたいんだけど。 307 名前：デフォルトの名無しさん mailto:sage [2007/11/23(金) 08:28:25 ] >>306 係数を議論するなら計算モデルを出さないと普通不可能だし， その擬似コードの partition の実装もわからないからなんともいえない． 308 名前：デフォルトの名無しさん [2007/11/24(土) 19:00:09 ] 306 携帯からでカンマが改行になってしまいました。 >>307 具体的に計算する必要はありません。 何か他の実装が partitionの実装が分からなければSTLのソースでも見てください。 309 名前：デフォルトの名無しさん mailto:sage [2007/11/24(土) 19:52:52 ] >>308 ちと文章が切れてるので何を言いたいか察しかねるが、 計算量係数ってことは O(n) で隠れてる定数部分を 評価したいんでしょ？ そのためには、たとえば 　・対象はどう表現されているか（リスト，配列 etc） 　・n として何を数えるか（比較，イテレータの移動，スワップ etc） 　・それぞれどれくらいの計算コストの差があるか なんか決まらないと、とても評価できない。 「実用上早い」ってのは知られてるけど、計算量の係数が 実際にどんくらい小さいかってのは不明。 あと、306 のコードは「C++ 風の擬似コード」じゃなかったの？ それで「実装は STL を見ろ」というのではあなたの言うところの 擬似コードの意味がよくわからないんだけれど。 それに STL の partition はアルゴリズムは全く決めてないから 例えば「gcc のどのバージョンの STL の実装」とか言わないと。 310 名前：デフォルトの名無しさん mailto:sage [2007/11/24(土) 23:27:09 ] 何がやりたいのかわからんので、 エスパーで問題を考えて回答しよう。 入力 *X;(1,2,4,4,4,5,6,7);//ソート済み配列,長さO(n) Pivot=4;//比較する値 Begin=0;//探索範囲？ End==7;// 出力 (2,5);//(1,2),(4,4,4),(5,6,7)と分けたときの4と5のインデックス アルゴリズム B=Begin;E=End; while(E-B&g;1) if(X[(B+E)/2]>Pivot) 　　E=(B+E)/2; else if(X[(B+E)/2]<Pivot) 　　B=(B+E)/2; else {　　N=(B+E)/2; break; } 以降はBとN間、NとE間の境界を通常の二分探索で見つける。 比較回数の最悪は明らかに1回目の比較でbreakして全体の1/2のサイズの二分探索を二回行わなければならないときで、 1+2(logn-1)=2logn-1回 311 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 02:31:58 ] >>310 それはエスパー失敗 ソートされていない配列をピボットよりも 「小さい・同じ・大きい」に分ける」のが問題でしょう。 312 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 16:45:03 ] >>311 そんなの順番に見ていくブルートフォースアルゴリズムが自明で最速ではないか。古典では。 313 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 17:58:59 ] >>312 ブルートフォースという意味がよくわからないけれど、 先頭から順に見ていき、ピボットとの小中大によって 対応するリストにコピーする、というアルゴリズムのこと？ もしそうであれば、普通の計算コストの設定では最速ではない。 なぜならば、そのアルゴリズムは、「要素のコピー」 が 必ず n 回発生するが、普通はコピーは比較より数倍重い。 314 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 21:55:16 ] >>313 そのアルゴリズムが最速ではないというなら最速なアルゴリズムを記述してくれ。 コピーが重いならコピーせずにポインタで参照すればいいのでは。 二段参照になるからリストの性能は落ちるだろうが。 315 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 22:09:04 ] >>314 「最速」かどうかは知らないが次の論文を参照。 Jon Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", Eighth Annual ACM-SIAM Symposium on Discrete Algorithms New Orleans, January 1997 316 名前：315 mailto:sage [2007/11/25(日) 22:12:19 ] 補足。 コピーが重いというのは、別にオブジェクトが重いとかそんなものではなく、 int の値のコピーと int の値の比較でもコピーのほうが数倍遅い。 本当に膨大なデータを処理しようと思ったときは、この定数倍が響くことがある。 （それに、上のアルゴリズムは余計な空間を使うのも痛い） 317 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 22:52:24 ] >>316 おｋ理解した。 swapで必要なところだけ入れ替えると。 swapでコピーが2重に発生するから 最悪上の単純なアルゴリズムの2倍かかってしまうが、 平均的には速いと。 クイックソートは最悪時間はバブルソートと同じになるが、 平均的にはマージソートよりも速いみたいなものと。 318 名前：315 mailto:sage [2007/11/25(日) 23:30:21 ] >>317 ちょっと理解できていないように見えるんだけどな。 計算コストをきちんと設定しないといけないと言っていて、例えば 　・スワップはコピーを2回実行する 　・どこへのコピーも同じ単位時間で行える みたいなモデルを考えればあなたの言ってることはほぼ正しい （というか「平均的」（何の平均かわからんが）にも単純アルゴリズムが早くなる）。 しかし、現実の CPU ではそんなことは全然無くて、実際は 　・値のスワップはコピー2回よりも若干高速に実行される 　・同一作業領域中でのスワップは、別領域へのコピーよりもはるかに高速 ということになっているから、「2倍かかる」という算定は全く間違い。 x86 あたりを前提に算定すると「10倍以上早い」という結論でも不思議じゃない。 このあたりはオーダにしちゃうと完全に隠れる部分だから クイックソートを例に出すのは不適当だと思う。 319 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 23:54:19 ] 具体例を見せてくれないかな。 320 名前：315 mailto:sage [2007/11/26(月) 00:33:18 ] >>319 何の具体例だい？「10倍以上遅くなる」ような実装の具体例？ そんなのは、Bentley-Sedgewick の論文からコードを引っ張ってきて、 手元で適当にコードを書けば簡単に具体例になるよ。 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 そうなんです＞＜ いろいろ考えてみてはいるんですが。。。どうしてもバランスがとれなくて 困っています。 422 名前：415 mailto:sage [2008/07/06(日) 01:32:25 ] 平衡2分木は1 2 4 8 16・・と、2のべき乗でノードが増加するのが 判ってるから、分割した要素の総数から大雑把に見積もった 空のツリーを作成しておいて、データの穴埋めをしていけば 線形時間で済むでしょ。 例えば1から10までの要素で平衡木を作るなら1+2+4+8の 15に収まる4階層の平衡木が確定する。 あとは右端からトラバースして埋めていくだけ。 　　　　　　　　7 　　　 4　　　　　　　 9 　2　　　　6　　　　8　　　10 1　 3　　5 423 名前：デフォルトの名無しさん mailto:sage [2008/07/06(日) 07:16:54 ] なんでわざわざ分割操作を赤黒木でやろうとしてるの？ 探索木で分割自体が O(log n) でいくようなものもたくさんあるでしょや。 424 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 23:28:29 ] >>421 平衡木を適当にぶった切ったら、もうそれは平衡木ではない。 バランス取れなくて当前。 比較は必要ないが、結局双方の木でdeleteやinsert相当の 回転操作をやる必要がある。 425 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 14:46:34 ] ドラえもんがポケットから目的の物を見つける時、どんな探索アルゴリズムを使ってるんだろう。 426 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 18:47:51 ] O(1)が基本だろうが語彙が特定しない場合は自己組織化探索も入ってるな 427 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 19:08:03 ] 確かのび太がスペアポケットで、しらみつぶしに探してた気はするｗ 428 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 19:29:59 ] ソートキーは名前以外の可能性が高いな 価格か商品番号か購入順か オレは購入順を推しておこう 429 名前：デフォルトの名無しさん mailto:sage [2008/07/24(木) 20:01:37 ] 緊急時に限っていらないものが出てくるから購入順ではなさそうだが。 物の名前の一部などであいまい検索で引っかかったのを片っ端から探るとか。 あわててるとクエリの生成が適当になる。 430 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 00:09:11 ] コミックスを見比べたわけじゃないが 緊急時に出る道具ってある程度固定されてる気がする。 夢確かめ機みたいなろくでもないのは毎回出てくるだろ？ ポケットの中身はおそらく、ろくでもない順（＝Fに愛されてる順）にソートされてる。 431 名前：425 mailto:sage [2008/07/25(金) 04:18:33 ] おまえらバカじゃねえの 432 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 09:26:30 ] 425さんの賢いところを見せてください 433 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 10:33:52 ] >>429 たしかドラポケットは「思ったものが出てくる」仕組みなので、慌ててる ときにいらんもんが出てくるのは、そもそもの探索キー(思考)がgdgdなん だと思われ。 434 名前：425 mailto:sage [2008/07/25(金) 13:31:18 ] >>431 お前誰だよｗ 435 名前：424 mailto:sage [2008/07/25(金) 15:24:52 ] >>434 オレオレ、オレだよ 436 名前：デフォルトの名無しさん mailto:sage [2008/07/25(金) 15:41:23 ] 名無しだよ 437 名前：デフォルトの名無しさん [2008/08/08(金) 02:49:00 ] チャットプログラムを考え中なのですけど、軽く自信がないところがあるので質問させてください。 ブラウザで前回の更新時以降に追加されたログのみを受け取り、 ログ出力に反映させる。という部分を作っているのですが、 サーバのデータを受信する時の形式をどんなふうにしようか少し悩んでいます。 今のところは (受信成功確認用の文字)<>時間<>発言者<>発言<>文字色 ・・・・以降受信が必要な分だけ時間から文字色のデータをループで渡す。 のようなことを考えているのですが、 何となくデータに若干の抜けがあったら結果が変なことになりそうな気がしてるのですが、 問題は無いでしょうか？ 438 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 05:37:58 ] go webprog 439 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 07:50:26 ] アルゴリズムではないな。 440 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 08:53:59 ] <> と発言したらどうなるか見てみたい 441 名前：デフォルトの名無しさん mailto:sage [2008/08/08(金) 17:59:54 ] &lt;&gt; 442 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 08:06:54 ] >>441 やりはじめはその手の処理忘れるよな 443 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 05:02:14 ] うまい方法が思いつかないので知恵を分けてください。 一定の半径を持つ円の中に点(座標)をランダムに打ちたい。 条件は、中心から一定距離までは打たない、円周になるほど高頻度で打ちたい 使える物は、精度(分解能)のよくないSin(Cos)テーブル 高級ではない言語と低レベルな頭脳なので、できれば数学系ライブラリとかを使わずに 計算や乱数などで済ませたいです。 具体例ではなく考え方でも構いません。 444 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 06:28:21 ] >>443 こんな感じ？ www.dotup.org/uploda/www.dotup.org0569.png 445 名前：443 mailto:sage [2008/08/29(金) 07:05:54 ] >>444 まさに理想形です。 可能な範囲で助言をいただけると嬉しいです。 今更かもしれませんが、補足 中心から方向Xに距離Rで配置すると中心の密度が上がってしまうので困ってます。 446 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 07:29:24 ] >>445 方向X、円周からの距離Rの片側正規分布で一定以上は切ればいい希ガス。 447 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 08:51:36 ] 偏角は一様分布で出して、 中心からの距離を、 一様分布に対して 1/r かけたもので作れば r に比例した分布になる。 1/r^2 とかかけとけば 442 みたいな分布になると思う。 448 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 10:02:34 ] >>443 x=乱数; y=乱数; if(x*x+y*y<r*r) 点を打つ; 449 名前：443 mailto:sage [2008/08/29(金) 11:38:57 ] みなさんありがとうございます。 乱数は一様乱数しか知らなかったので、正規乱数を使う事で解決しました。 ありがとうございました。 450 名前：デフォルトの名無しさん mailto:sage [2008/08/30(土) 07:10:18 ] piece tableのサンプルコード等ありませんでしょうか 451 名前：デフォルトの名無しさん [2008/09/02(火) 14:25:43 ] データベース等に詳しい方教えてください。 B+木を実装する際に、ページに複数のエントリを入れる場合、 ページにできるだけたくさんエントリを入れようとすると、 空間効率は上がるが、木がバランスされなくなると思うのですが、 実際はどのような実装するのが普通なのでしょうか？ ページに入れるエントリ数を固定するのでしょうか？ （その場合は、エントリのサイズが小さい場合は、空間効率が悪くなるし、 大きい場合は、１ページに入らないといった問題がおきて、 実装がややこしくなりそうと思っています。） 452 名前：デフォルトの名無しさん [2008/09/02(火) 14:32:31 ] 451です。 一般的には、 次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる ということは理解していますが、 エントリのサイズが可変の場合は、最大2d個のエントリをどう格納するのかが よくわかっていません。 * ページサイズを可変にする * ページサイズは固定で、入りきらない場合は複数のページを使う この辺があると思っています。 453 名前：デフォルトの名無しさん mailto:sage [2008/09/03(水) 20:16:03 ] ページに入るエントリ数は固定。 バランスされなくなるって、ノードの兄弟を見ながら 2dに収まるように分割してくんだよ。 ほとんど理解できてないみたいだから より単純なB木から学んだ方がいい。 454 名前：デフォルトの名無しさん [2008/09/16(火) 18:38:15 ] ４つの都市A、B、C、Dのそれぞれの距離がわかっている状態で、 xy平面上に正しくA、B、C、Dを配置したいのですが考え方がわかりません。 アドバイスをいただけないでしょうか？ 455 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 19:12:08 ] 回転どうすんだ 456 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 21:57:19 ] >>454 三角関数 457 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 22:07:09 ] >>454 回転が確定しなくていいなら、相対測位とかいうキーワードでぐぐれ。 458 名前：454 [2008/09/17(水) 16:07:09 ] 455様、456様、457様返信ありがとうございます。 余弦定理を用いて半径ACと半径BCの円の交点を考えC点を導いたのですが 次のD点を考えるときに半径AD・BD・CDの円が（当たり前かもしれませんが）１点で交わらないので求められませんでした。 455様と457様が言っている「回転」が必要だなと思い、 B点をA点のまわりで距離ABを保ちつつグルグル回るようにしたのですが、どうも違うみたいで困ってしまいました。 回転についての詳しい説明を教えていただけないでしょうか？ 今は下のような状態になっています。 ttp://www.dotup.org/uploda/www.dotup.org0494.png 赤・青の円は半径AC・BCの円でC点（黄緑）を求めました。 薄い赤・青・緑の円は半径AD・BD・CDの円でとりあえず円AD・BDの交点から仮のD（紫)を導いたところです。 よろしくお願いします。 459 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 17:00:27 ] ４点が平面上にないだけじゃないの？ 分かりやすい座標で１回やってみた方がよさげ。 460 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 22:38:41 ] 3点の位置が決まって距離もわかってて4点目が交わらないってあるのかな？ 各点間の距離データはあってるんだよね？？ 461 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 00:59:48 ] 現実の都市間の距離だったりして・・・ とはいえその場合でも、対称を同一視すれば一意に求まるはず。 462 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 02:23:10 ] >>459,461 そ れ だ。 現実の都市間の距離で、球面上には矛盾無く配置できるけど平面上では矛盾無く配置できないとかな。 とりあえず454はそれぞれの距離を提示するべき。 463 名前：454 [2008/09/18(木) 14:11:16 ] 459様、460様、461様、462様返信ありがとうございます。 まず都市ABCDが現実に存在する都市かどうかですが、この世に存在しない都市を仮定しています。 そのため距離は毎回乱数で定まっています。 最初に断わっておくべきでした申し訳ないです。 4点が同一平面上にない場合があることは考えていませんでした。 今回の考え方を元に、単語同士の非関連度を距離に置き換えてそれぞれを配置するプログラムを作ろうかと思っていたのですが、 平面上のみで考えるのは無理があるのでしょうか。 464 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 14:40:44 ] 4点をa,b,c,d、それらの間の距離6つをab,ac,ad,bc,bd,cdと書くことにする。 距離を何の制約も無しに乱数で作ると、それは4点間の距離と言えないものもできてしまう。 a,b,cで三角形になるのだから、ab+bc>acなどの制約が必要。 a,b,c、a,b,d、a,c,d、b,c,dの各組が三角形になる制約を満たすなら、 4つの点a,b,c,dは4面体を作る。 465 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 17:25:13 ] 何点あっても、二点間の間での距離だけを定義すればうまくいくんじゃね？ 完全ランダムでは無理条件ができるけど 466 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 20:06:30 ] >>465 > 二点間の間での距離だけを定義する という意味がわからないけれど， 『任意の二点間で三角不等式が成立するならば実現可能」 という主張なら，4点で反例が構成できる： d(12) = 1, d(13) = √5, d(14) = √2, d(23) = 2, d(24) = 1, d(34) = 1 467 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 20:25:51 ] これは非常に有名な問題（グラフ実現可能問題）． 以下の事実が知られている． 定義： n×n 行列 D = (d_ij) が EDM であるとは， ある点 p_1, ..., p_n ∈ R^k が存在して， d_ij = |p_i - p_j|^2 が成立することをいう． k を D の埋め込み次元という． I を単位行列，J をすべての成分が 1 の行列とする． 定理(Schoenberg, Young-Householder)： 対称かつ対角成分がゼロの非負行列 D が EDM であることと， G := -V D V / 2 が半正定値であることが同値． ただし V = I - J/n である． また，G = X X^T を コレスキー分解としたとき， X の列ベクトルは D の実現となる． なので，与えられたデータから行列 D を構成して G を計算してコレスキー分解すれば埋め込みが決定できる． もし rank G > 2 だったら平面には埋め込めない． 詳しくはEuclidean Distance Matrixなどで検索してくれ． 468 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 00:48:36 ] 質問させて頂きます。 XY平面上に、その座標データを保持するオブジェクトが複数個あり、 それらの座標はそれぞれランダムだったとします。 それぞれのオブジェクト間の距離が一定以下の場合は、 一定距離の間隔を置けるように引き離し、 さらにオブジェクトの距離の一番近いオブジェクトを探す というようなことをしたいのです。 この処理はリアルタイムループ内で実行するので、 引き離しは1距離だけ離れるだけで十分であるとします。 一応は下記のようなプログラムで実装は出来ているのですが、 オブジェクトの数が増えた場合に処理が急激に重くなります。 この処理の計算量がn^2であるので、 オブジェクトの数が100、200と増えていった場合には とてもリアルタイムループでは遅すぎる速度になってしまうのです。 何とかしてこの計算量を減らす方法はないものでしょうか？ 469 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 00:50:56 ] >>468 簡略 #define n 200 struct Object { 　　double x, y; 　　int near; } op[n]; double dx, dy, dr, drmin; for(int i = 0; i < n; i++) { 　　drmin = 1000000; //とりあえず大きい数 　　for(int j = 0; j < n; j++) { 　　　　dx = op[i].x - op[j].x; 　　　　dy = op[i].y - op[j].y; 　　　　dr = sqrt(dx * dx + dy * dy); 　　　　//一番近いオブジェクトを探す 　　　　if (dr <= drmin) { 　　　　　　 op[i].near = j; 　　　　　　 drmin = dr; 　　　　} 　　　　//一定距離以内の場合は引き離す 　　　　if (dr <= 400) { 　　　　　　op[i].x += dx / dr; 　　　　　　op[i].y += dy / dr; 　　　　　　op[j].x -= dx / dr; 　　　　　　op[j].y -= dy / dr; 　　　　} 　　} } 470 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 01:27:09 ] >>468 動的ボロノイ図を使えば，一反復が O(n + k log n) でできる． ただし k は引き離す必要のあるペアの数． ただ，これは実装が結構しんどいので，現実的には x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て 枝刈りするのが有力だと思う （x 座標が一定距離を超えたら，距離が一定距離以下にはならない等） 計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず． なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると 多少の効率化ができる． 471 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 19:43:55 ] >>470 動的ボロノイ図は調べてみましたがサッパリ理解できませんでした（汗 なので後者のソートして近いところから探す方法を試してみたところ、 オブジェクト800個くらいまでは実用レベルの速度で動くようになりました。 但しやはり位置関係によっては重くなることもあり、 必ずしも安定しているとは言えませんが、 総当りに比べれば桁違いの速度になりました。 ありがとうございました。 472 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 23:01:01 ] 「一定距離」の間隔でマス目に区切って、マス目毎にデータをコレクションで持ち、 引き離し処理をするときには、データとその周囲の9マス分の範囲だけ調べるとか。 □□□□□ □■■■□ □■▲■□ ←▲のところが自分の属すマス □■■■□ □□□□□ データの散らばってる範囲が狭過ぎると密集して役に立たないし、 逆に広過ぎるとマス目の管理を工夫する必要があるけど。 あと、「一定距離」以上でも最も近い点を取得する必要があるなら、これじゃだめかも。 473 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 23:06:33 ] ヒューリスティックだけど、自己組織化で適当に動かしてみるとか。 474 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 11:26:32 ] すまん、図形描画アプリみたいなものを作ってるんだが･･･ 次のようなもので悩んでます。 １．複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか? 場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。 総当たり以外でエレガントな方法というとどんなんざんしょ? ２．同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。 教えてエロイ人･･･ 475 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 12:15:00 ] メモリが許せば、思い切って座標にオブジェクトを持たせるとか。 476 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 12:15:42 ] >>475は>>468にです。 477 名前：468 mailto:sage [2008/09/20(土) 18:05:06 ] お返事ありがとうございます。 >>472 空間分割とかいうやつですかね？ しかしこれは「最も近い点を取得する」という場合に やはりお察しのように問題がありまして、 結局こちらの方法は諦めたのであります。 一応この最も近い点を探す距離も制限されてはいるのですが、 結構範囲が広いのでその表現は省かせていただきました。 >>475 これはその空間分割の究極ですね・・・ しかしこれはまた違う方向で膨大な判定量になりそうな気がします。 478 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 19:00:54 ] >>477 472の亜種だと思うけどＸ，Ｙ軸上でソートして、各軸上の分布をクラスタとして扱うっていうのがGameProgrammingGEMに載っていた。 479 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 21:40:57 ] >>474 問題が明確じゃないのだけれど， (1) 『描画する』条件は，単に『別の矩形に包含されないこと』でよい？ それとも，矩形間に上下関係（例: Windowsのウインドウ）がある？ (2) 『描画する』条件は (1) と共通ということでよい？ それと，曲線はどのような形で与えられる？（例：ベジエ曲線） 何にせよ平面走査型のアルゴリズムが有力に動くと思う． 480 名前：デフォルトの名無しさん mailto:sage [2008/09/21(日) 11:23:34 ] ナップサック問題とは、価値と重量があるものを、入れられる重量に制限がある箱に 一番価値が高くなるように効率よくいれるにはどういれたらよいかの手順を考える問 題ですよね。 これに、価値が高くなることに加えて、入れる順番も重さがあるものから入れる、あるいは 軽い順に入れるなどの制限が加わった場合にどのようにすればよいかという解法は 存在しますか？ 481 名前：デフォルトの名無しさん mailto:sage [2008/09/21(日) 11:59:36 ] >>480 入れるものを決めた後で重量でソートすればいい 482 名前：474 mailto:sage [2008/09/21(日) 12:35:56 ] >>479 不明確ですいません･･･orz 1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。 ２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。 平面走査型ちょっくらぐぐってきます。 483 名前：デフォルトの名無しさん mailto:sage [2008/09/22(月) 00:32:18 ] >>481 書くべき事がたりませんでした。。。 では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？ 484 名前：デフォルトの名無しさん mailto:sage [2008/09/22(月) 02:43:01 ] DP使うしかないんじゃない？ 485 名前：デフォルトの名無しさん mailto:sage [2008/09/23(火) 09:49:23 ] >>480 状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ． 重さが自然数であれば，品数を n，重さの最大値を W としたとき 普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば O(n^2 W) のアルゴリズムが簡単に作れる． 重さが実数であれば，基本的には枝刈り探索しかないのだから， 上の三つ組みを持って適当に探索する． 本気を出すなら，品数や重さなどによって適切な探索法が変わるけど そこまでがんばるかい？ 486 名前：デフォルトの名無しさん mailto:sage [2008/09/23(火) 11:07:05 ] >>482 もうググって見つけたかもしれないけれど， 1 に関しては平面走査型アルゴリズム（plane sweeping）が考えられる： ・y 軸に平行な直線を考える（走査線と呼ぶ） ・走査線を x = -∞ → +∞ に移動させていく． ・走査線に新たな矩形が乗ったら走査線上の矩形とだけ描画判定を行う． 走査線は y 座標でソートされた二分探索木を用いると， 描画判定を行うべき矩形を O(log n + k) 程度で列挙できる． 二分探索木を管理するのが面倒ならリストで持ってもよいが， これだと列挙に O(n) かかる． （矩形がそれなりに散らばっていれば，現実的には相当改善する） こういうのは「線分交差列挙」などで調べると参考になると思う． ちなみに矩形が動的に増えたり減ったりするような状況設定なら， 空間分割木などの幾何データ構造を使うことになる． 2 に関しては，描画の段階でなくて，データの段階でどうなるかが問題． もしデータの段階で「連続した線分の集まり」と思ってよいなら， 1 の平面操作型アルゴリズムに走査線に線分が交わったら云々を追加するだけ． それがダメなら，扱う曲線のデータ構造が分からないと，どうしようもない． たとえば『曲線の方程式 (x(t), y(t)) が与えられる』くらいだと， 曲線と矩形の交差を全チェックするしかない． 487 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 01:27:20 ] ポリオミノ自動生成アルゴリズムって、起点を中心にどんどん成長させていって、 それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。 488 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 19:54:18 ] 自動生成って何？ 指定したサイズのもの全てとか、小さい順とかで列挙すること？ それとも、条件を満たすもののサンプリング？ 489 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 21:02:22 ] nの数を与えて、その全パターンを出すアルゴリズムです。 n=7なら、108通り全部とか。 490 名前：デフォルトの名無しさん [2008/10/19(日) 01:32:31 ] あげ 491 名前：デフォルトの名無しさん [2009/01/18(日) 20:54:29 ] age 492 名前：デフォルトの名無しさん [2009/01/19(月) 19:28:43 ] 良スレの予感 493 名前：デフォルトの名無しさん [2009/01/19(月) 23:10:09 ] DBMについて興味があり、最近書籍やウェブなどをあたっていました。 B-Treeなどのアルゴリズムについてなんとなく理解したのですが、 それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。 C言語で実装されているソースの解説などどこかにあるでしょうか。 もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、 ちょっと敷居が高いです。 494 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 01:02:00 ] いきなりF1に乗ろうとする奴っているよね。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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