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

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 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 回転が確定しなくていいなら、相対測位とかいうキーワードでぐぐれ。

---

---

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

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