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

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 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; 　　　　} 　　} }

---

---

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

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