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

＜集大成＞アルゴリズ ..

357:デフォルトの名無しさん
08/04/13 23:31:07
>>356
「重さのピークが高い」って言葉の意味が分からない．
あと，複数の山があったときにどう評価するかも分からない．
具体例をいくつか出してくれないかしら．

358:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/13 23:40:37
＞のような9個があったとして
10個でした。

360:デフォルトの名無しさん
08/04/13 23:46:06
まず問題を誰にでもわかるように定義することからはじめようか。

361:デフォルトの名無しさん
08/04/13 23:53:53
>>357
問題を考えるときは，それを数式で書けるくらいまで整理しないと，
アルゴリズムなんて出せるはずがない．

きっとなんか解きたい問題があって，あなたはその要点のみを
取り出したつもりだと思うんだけど，取り出し方が悪くて全然分からないよ．

362:デフォルトの名無しさん
08/04/14 00:10:42
解きたい問題は実は特になくて、この手の雑学の本を読みながら考えていたら、これは欲張り法で
できるのかな？と思ったのです。
で、もうちょっと整理してみました。

ナップサックが10個、取れる品物は300個あるとしてこれらはランダムに5色のいずれかの色がついている

１．品物の価値が高いものを先に詰めねばならない
２．品物の色は、一袋には2色までしか混載できない
３．さらに一袋を詰め終わる過程で、色の切り替わる回数は一回のみ
４．ナップサック一つには10個まで入るが、赤い色の品物を3個入れていたら8個までになる
以上の満たして10個のナップサックをつくり、10袋の価値和を最大にする

２、３は、「赤赤赤赤青青青青青青」はいいが、「赤赤赤赤青青青青赤赤」だめ
４は「赤赤緑緑緑緑緑緑緑緑」で一袋、「赤赤赤緑緑緑緑緑」で一袋になるという感じ

これですっきりしたよーに思いますがどうでしょう？
色がついているのと、4みたいな条件のせいで、欲張れないんじゃないかと思うのです。

363:デフォルトの名無しさん
08/04/14 00:10:52
Σ((山の重さ)^2)
を最大化するの？

364:デフォルトの名無しさん
08/04/14 00:27:01
>>362
「袋の価値」は、中身の総和でいいのかな？

あと、その問題は、前の問題とはかなり違うように見えるんだけど。
重さのピークってのは忘れていいのかな？

365:デフォルトの名無しさん
08/04/14 00:51:46
>>364
「袋の価値」＝中身の価値の総和です。
ピークはですね。。。上手く表現できないので省いてしまってかまいません。

が、、、いいたかったことは
10袋の価値の総和が等しいケースが2ケースあった場合、満遍なく10個そろったやつよりも
ばらついてる方を解としたいというような・・・・

仮に100円なら、「10円のうまい棒10本」よりは「40円のよっちゃんイカ1つと4本のうまい棒と4円のﾅﾆｶおかし5個」
の方を解としたいというような感じだったのです('A`)

366:デフォルトの名無しさん
08/04/16 21:11:48
とりあえず赤色がなければ、価値の高いものから順に100個取ってくればいいんだよね？

367:デフォルトの名無しさん
08/04/17 00:22:15
データをDRBDみたいな
再同期を含む同期を実行する種の
アルゴリズムってどの分野に区分
されるの？

全然文献なくて困る

368:デフォルトの名無しさん
08/04/17 03:14:15
>>366
おそらくそうなると思います。
赤があるから制限が8個になるからって、8個でも10個詰めたときより価値が高くなることも
あるし、それは調べてみないとわからないよなぁと思うのです。

369:デフォルトの名無しさん
08/04/25 06:58:34
suffix arrayで正規表現検索ってできるんすか？
なんかsuffix trieにしないとできないみたいなんですが…

370:デフォルトの名無しさん
08/04/26 10:14:29
できる．理論上 suffix tree/trie で書けるアルゴリズムは
suffix array を用いて全く同じ計算量で実行できる．

371:デフォルトの名無しさん
08/04/28 22:01:30
なぁなぁ、教えてくれよ。
有向グラフっての？　巡回サラリーマンっての？　ダイクストラ法っての？　なんかそんなの。よくわからないけど。

平面上に有限の座標群がある。まぁA～Zとしよう。
いくつかの座標間には経路がある。A-Bには経路があるが、B-Cには経路がないって感じ。

で、与えられた二点間を結ぶ全ての経路を算出するんだが、最短とか最長とかを考慮する必要はない。
とにかく、全ての経路を表示する。

座標情報はRDBに入力され、常に変動するので、計算するたびに違う結果になることもある。

乗り換え案内みたいなソフトウェアを作ろうと思ってるんだけど。
こういうのってどう考えればいいの？

372:デフォルトの名無しさん
08/04/28 22:18:32
バルブソートの検索結果約 693,000 件中 1 - 10 件目

多すぎだろ。

373:デフォルトの名無しさん
08/04/28 22:20:53
バブルソートの検索結果約 267,000 件中 1 - 10 件目

いったいどういうことだよ。
おれがおかしいのか？

374:デフォルトの名無しさん
08/04/28 22:38:38
>>371
東大かどっかの研究レポートがwebにのってたよ

375:デフォルトの名無しさん
08/04/29 02:26:12
>>373
ウェブ "バルブソート" に一致する日本語のページ 10 件中 1 - 10 件目 (0.14 秒)
ダブルコーテーションで括らないと曖昧検索される

376:デフォルトの名無しさん
08/04/29 03:52:36
>>372
アホ。

377:デフォルトの名無しさん
08/04/29 04:32:38
>>375
KY

378:デフォルトの名無しさん
08/04/29 12:42:32
>>371
条件の確認なんだけど，「二点間の経路」で列挙したいのは
同じ頂点を複数回通らないような経路でよい？

あと，経路の数は半端なく多くなることがあるけど
出力順は問わないの？

379:デフォルトの名無しさん
08/04/30 01:09:48
>>378
おー、レスサンクス！

例えば、下図のパターンで考えると、

┌B─D┐
A｜｜ F
└C─E┘

ABDF、ACEF、ACBDF、ABCEF、ABCDEF、ACBDEF、ACDEF、ABDEFだっけ？
全体が重複してさえいなければ同じ頂点、同じパスを辿ってもかまわない。
今は、とりあえず経路の算出方法で頭をひねってる。

次の段階として、各パスにはコストを持たせ、出力する際には、パスが少ない順・多い順、総コストの多い順・少ない順、パスがnになる場合のみ出力、
ノードBが利用不能になった場合の代替経路は…

とかってのを考えてるよ。

380:デフォルトの名無しさん
08/04/30 01:21:35
>>379
ということは
ABDECBDF
ABDECBDECBDF
ABDECBDECBDECBDF
ABDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDECBDECBDECBD........ECBDECBDECBDECBDECBDF
でもOK？

381:デフォルトの名無しさん
08/04/30 09:37:50
>>379
重複アリだと >>380 みたいになって，経路が無限個になって「列挙」できなくなるのよ．
この場合方針としては
・経路が無限個にならないように問題を変更する
・経路総数は無限個でもよいから、適当な順序で（上から有限個）出力する
のどっちか．さあどうしよう？

あと，そろそろ用語を正しておくと経路やパスってのは全体のことで，
隣り合ってるところは辺や枝と呼ぶのが普通ね．

382:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/04/30 11:31:00
各節間の距離がわかっているなら終点との距離と比較するだけでだいぶ正解に近づきそう。

384:デフォルトの名無しさん
08/04/30 11:38:53
乗換案内で同じ区間を2度とおる意味ってあまりなさそうなんだけど。

385:デフォルトの名無しさん
08/04/30 19:53:08
赤黒木とはなんぞや。

386:デフォルトの名無しさん
08/04/30 20:29:01
2-3-4木と等価な構造を持つ木を二分木で作るためのデータ構造。

387:デフォルトの名無しさん
08/05/03 08:34:47
「動的計画法（dynamic programming）」で名前最悪だな。
変な名前のせいで、この手法のポイントが要するにどこにあるのか
なかなか理解できなかった。
「部分問題解展開法」とかそんな名前にすれば良かったと思う。

388:デフォルトの名無しさん
08/05/03 08:35:36
×「動的計画法（dynamic programming）」で名前最悪だな。
○「動的計画法（dynamic programming）」って名前最悪だな。

389:デフォルトの名無しさん
08/05/03 08:47:58
"dynamic programming"はもはやFOLDOCには載ってない。
"programming"は「コンピューター・プログラミング」ではなく、「計画」のこと。
overlapping subproblems, optimal substructure, memoizationする手法のこと。

390:デフォルトの名無しさん
08/05/03 09:55:42
FOLDOCに載ってないことはあまり指標にはならないんじゃないかな。
たとえば "greedy algorithm" や "divide and conquer" も載ってないしね。

ネーミングの由来は、部分問題を解いて、それを元に新たな計画問題を作る感じが、
動的に計画問題を解いているっぽいから、だそうな。

391:デフォルトの名無しさん
08/05/10 19:34:49
挿入ソートの計算量ってどうやって求めるの？
いろいろ調べてみたけど式にΣが出てきたからわけわからなくなった。
そんな馬鹿な俺でも理解できるようにだれか説明してくれないかな。

392:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/05/11 12:58:18
コメントありがとうございます。
参考にさせていただきました。
webやテキストの説明でもそれぞれ異なった説明の仕方をしていましたので多少混乱していたようです。
なんとか理解することができました。ありがとうございます。

394:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/05/30 18:38:56
反論ないなら最速ソートアルゴリズムの座を奪いますよ～

396:デフォルトの名無しさん
08/05/30 19:02:59
今、標準ライブラリと勝負したら負けたわ。
アルゴリズムはもちろん、クイックソート。ただし、工夫されているとのこと。
自作のクイックソートがダメなだけだった。

なので反論は遠慮しとく。

397:デフォルトの名無しさん
08/05/30 19:07:41
>>394
やってみたけどstd::sort()の1/2程度の速度しか出ないじゃん

398:デフォルトの名無しさん
08/05/30 22:02:40
>>394
速度以前に正しくないんでは？
[1,6,3,4,3,1,6] → [6,4,6,3,3,1,1]　となったけども。

399:デフォルトの名無しさん
08/05/31 11:16:46
クイックソートはきちんとチューニングしてきちんとコーディングしてこそのもの。
岩波ソフトウェア科学シリーズの『アルゴリズムとデータ構造』のクイックソート
の項目は読むべき。

400:デフォルトの名無しさん
08/05/31 15:30:24
>>398
comb sortについてよく調べると、ギャップが1になったら普通にバブルソートにするようです。
しかも、その時に整列済みか確認しないといけないようです。

ギャップがある程度(16ぐらい)に小さくなったら、挿入ソートに切り替えってのを試したら、意外と速いです。
ただのシェルソートっていう突っ込みは（ｒｙ

401:デフォルトの名無しさん
08/06/04 09:25:07
>>400
> ギャップがある程度(16ぐらい)に小さくなったら、
> 挿入ソートに切り替えってのを試したら、意外と速いです。

これはquick sortもそう。
特にintとかチンケなものをsortしているときは。

402:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/06/04 11:21:56
欠点は挿入ソートの欠点がそのままになっていて、データ数が多いときに少ないときに比べて遅くなります。
解決策として、２分挿入ソートが良さそうです。

ただ、さっきも書いたとおり、コムソート(バブルソートの改良)と挿入ソートの組み合わせという
単純なアルゴリズムで結構速し、特に欠点なしという所をアピールしたいので、まぁそのままで。

Javaの標準ライブラリとは同じぐらいの速さですが、興味があれば勝負させて見てください。でわ。

404:デフォルトの名無しさん
08/06/04 11:23:25
「他の言語でも」が抜けてました。

405:デフォルトの名無しさん
08/06/04 13:01:44
純粋なアルゴリズムの話じゃないけど、
今なら分散処理できるようなデータ構造やアルゴリズムの方が良いかもな。マルチコアだから。

406:デフォルトの名無しさん
08/06/05 00:41:48
>>403
たった1000000個くらいのランダムデータに対しても
std::sort() の1/2未満の性能しか出ないよ。
ソーティングの世界では一瞬でも遅いのは大きな欠点。

407:デフォルトの名無しさん
08/06/05 09:11:39
>>406
その通りで。

あれから、VC++をダウンロードしてちょこっと試してみたんですが
std::sort()の前にまずはCの標準のqsort()でやったところ
qsort()の方が全然速かったです。qsort()の方がstd::sort()よりも速いのかもしれませんが
試す前にやめました。(C++をあまり知らないということもあって)

408:デフォルトの名無しさん
08/06/05 23:21:04
たいていはstd::sortの方が早いんだけどね。

409:デフォルトの名無しさん
08/06/06 00:23:30
STLPort使えよ

410:デフォルトの名無しさん
08/06/07 17:13:13
比較処理がインライン化される可能性のある std::sort の方が
確実にインライン化されない qsort よりも一般に速い。

411:デフォルトの名無しさん
08/06/21 23:56:21
b+-treeに関する詳しい解説があまり見つからないんだけど、
要はb-treeとなにが違うの？
突然の話題で申し訳ない。

412:デフォルトの名無しさん
08/06/22 09:25:03
URLﾘﾝｸ(en.wikipedia.org)

413:デフォルトの名無しさん
08/06/23 00:55:46
>>411
葉にデータを集めたり、葉同士をリンクリストで繋げるなど、積め方を
工夫して末端の葉へのアクセスを単純にできるようにしたのがB+木。
(B木でもイテレーションは再帰やスタックでできるが)
B+木のノードの追加削除は複雑で、手間の割にうまく実装しても速度は
素のB-Treeに劣る。空間効率は良くなるので外部記憶で使うとか、
構造上範囲検索で有利に働くので、それを多用するなら意味がある。
B木でもキャッシュやファイルマッピングが使える状況だと空間効率を除き
差はほとんどない。

414:デフォルトの名無しさん
08/07/03 16:37:27
red-black-treeにおけるinsertやdeleteはいろいろなサイトに掲載されているのですが、
木の分割についてのアルゴリズムがどこを探しても見当たりません。
バランスを保ちながら木を2つに分割するアルゴリズムは存在しないのでしょうか?

415:デフォルトの名無しさん
08/07/04 07:19:15
insertやdeleteを組み合わせればできるんでは

416:デフォルトの名無しさん
08/07/04 22:53:42
て言うか分割って何？

417:414
08/07/04 23:48:17
>>415
ありがとうございます。一応insertとdeleteの組み合わせではできたのですが
もっと早い方法が無いのかと思って書き込みました。
もう少し考えてみます。

>>416
木をある値を境にして二つの木に分けたい、という意味です。
一つ一つのノードを木からdeleteして新しい木にinsertしなおせばできるのですが、
もっと単純にやる方法がないかと探しています。

418:デフォルトの名無しさん
08/07/05 00:55:24
>>417
> 木をある値を境にして二つの木に分けたい

任意の値と言うこと？

なんかいい方法ありそうなが気がするが、俺の頭では無理だ...。

419:415
08/07/05 13:40:03
順序はできてるんだから、適当に並べ替えるだけかと。

420:デフォルトの名無しさん
08/07/05 14:48:09
その並べ替えるコストを問題にしてるんだが。

421:414
08/07/06 00:40:59
>>418
そうです、任意の値を境にして二つのred-black-treeに分割したい、という意味です。

>>419
なるべくo(logn)の係数を抑えてやりたいのです。。。

>>420
そうなんです＞＜
いろいろ考えてみてはいるんですが。。。どうしてもバランスがとれなくて
困っています。

422:415
08/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:デフォルトの名無しさん
08/07/06 07:16:54
なんでわざわざ分割操作を赤黒木でやろうとしてるの？

探索木で分割自体が O(log n) でいくようなものもたくさんあるでしょや。

424:デフォルトの名無しさん
08/07/07 23:28:29
>>421
平衡木を適当にぶった切ったら、もうそれは平衡木ではない。
バランス取れなくて当前。
比較は必要ないが、結局双方の木でdeleteやinsert相当の
回転操作をやる必要がある。

425:デフォルトの名無しさん
08/07/24 14:46:34
ドラえもんがポケットから目的の物を見つける時、どんな探索アルゴリズムを使ってるんだろう。

426:デフォルトの名無しさん
08/07/24 18:47:51
O(1)が基本だろうが語彙が特定しない場合は自己組織化探索も入ってるな

427:デフォルトの名無しさん
08/07/24 19:08:03
確かのび太がスペアポケットで、しらみつぶしに探してた気はするｗ

428:デフォルトの名無しさん
08/07/24 19:29:59
ソートキーは名前以外の可能性が高いな
価格か商品番号か購入順か

オレは購入順を推しておこう

429:デフォルトの名無しさん
08/07/24 20:01:37
緊急時に限っていらないものが出てくるから購入順ではなさそうだが。
物の名前の一部などであいまい検索で引っかかったのを片っ端から探るとか。
あわててるとクエリの生成が適当になる。

430:デフォルトの名無しさん
08/07/25 00:09:11
コミックスを見比べたわけじゃないが
緊急時に出る道具ってある程度固定されてる気がする。
夢確かめ機みたいなろくでもないのは毎回出てくるだろ？

ポケットの中身はおそらく、ろくでもない順（＝Fに愛されてる順）にソートされてる。

431:425
08/07/25 04:18:33
おまえらバカじゃねえの

432:デフォルトの名無しさん
08/07/25 09:26:30
425さんの賢いところを見せてください

433:デフォルトの名無しさん
08/07/25 10:33:52
>>429
たしかドラポケットは「思ったものが出てくる」仕組みなので、慌ててる
ときにいらんもんが出てくるのは、そもそもの探索キー(思考)がgdgdなん
だと思われ。

434:425
08/07/25 13:31:18
>>431
お前誰だよｗ

435:424
08/07/25 15:24:52
>>434
オレオレ、オレだよ

436:デフォルトの名無しさん
08/07/25 15:41:23
名無しだよ

437:デフォルトの名無しさん
08/08/08 02:49:00
チャットプログラムを考え中なのですけど、軽く自信がないところがあるので質問させてください。

ブラウザで前回の更新時以降に追加されたログのみを受け取り、
ログ出力に反映させる。という部分を作っているのですが、
サーバのデータを受信する時の形式をどんなふうにしようか少し悩んでいます。
今のところは
(受信成功確認用の文字)<>時間<>発言者<>発言<>文字色・・・・以降受信が必要な分だけ時間から文字色のデータをループで渡す。
のようなことを考えているのですが、
何となくデータに若干の抜けがあったら結果が変なことになりそうな気がしてるのですが、
問題は無いでしょうか？

438:デフォルトの名無しさん
08/08/08 05:37:58
go webprog

439:デフォルトの名無しさん
08/08/08 07:50:26
アルゴリズムではないな。

440:デフォルトの名無しさん
08/08/08 08:53:59
<> と発言したらどうなるか見てみたい

441:デフォルトの名無しさん
08/08/08 17:59:54
<>

442:デフォルトの名無しさん
08/08/09 08:06:54
>>441
やりはじめはその手の処理忘れるよな

443:デフォルトの名無しさん
08/08/29 05:02:14
うまい方法が思いつかないので知恵を分けてください。

一定の半径を持つ円の中に点(座標)をランダムに打ちたい。
条件は、中心から一定距離までは打たない、円周になるほど高頻度で打ちたい
使える物は、精度(分解能)のよくないSin(Cos)テーブル

高級ではない言語と低レベルな頭脳なので、できれば数学系ライブラリとかを使わずに
計算や乱数などで済ませたいです。
具体例ではなく考え方でも構いません。

444:デフォルトの名無しさん
08/08/29 06:28:21
>>443
こんな感じ？
URLﾘﾝｸ(www.dotup.org)

445:443
08/08/29 07:05:54
>>444
まさに理想形です。
可能な範囲で助言をいただけると嬉しいです。

今更かもしれませんが、補足
中心から方向Xに距離Rで配置すると中心の密度が上がってしまうので困ってます。

446:デフォルトの名無しさん
08/08/29 07:29:24
>>445
方向X、円周からの距離Rの片側正規分布で一定以上は切ればいい希ガス。

447:デフォルトの名無しさん
08/08/29 08:51:36
偏角は一様分布で出して、
中心からの距離を、
一様分布に対して 1/r かけたもので作れば r に比例した分布になる。
1/r^2 とかかけとけば 442 みたいな分布になると思う。

448:デフォルトの名無しさん
08/08/29 10:02:34
>>443
x=乱数;
y=乱数;
if(x*x+y*y<r*r) 点を打つ;

449:443
08/08/29 11:38:57
みなさんありがとうございます。
乱数は一様乱数しか知らなかったので、正規乱数を使う事で解決しました。
ありがとうございました。

450:デフォルトの名無しさん
08/08/30 07:10:18
piece tableのサンプルコード等ありませんでしょうか

451:デフォルトの名無しさん
08/09/02 14:25:43
データベース等に詳しい方教えてください。
B+木を実装する際に、ページに複数のエントリを入れる場合、
ページにできるだけたくさんエントリを入れようとすると、
空間効率は上がるが、木がバランスされなくなると思うのですが、
実際はどのような実装するのが普通なのでしょうか？
ページに入れるエントリ数を固定するのでしょうか？
（その場合は、エントリのサイズが小さい場合は、空間効率が悪くなるし、
大きい場合は、１ページに入らないといった問題がおきて、
実装がややこしくなりそうと思っています。）

452:デフォルトの名無しさん
08/09/02 14:32:31
451です。
一般的には、
次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる
ということは理解していますが、
エントリのサイズが可変の場合は、最大2d個のエントリをどう格納するのかが
よくわかっていません。

* ページサイズを可変にする
* ページサイズは固定で、入りきらない場合は複数のページを使う

この辺があると思っています。

453:デフォルトの名無しさん
08/09/03 20:16:03
ページに入るエントリ数は固定。
バランスされなくなるって、ノードの兄弟を見ながら
2dに収まるように分割してくんだよ。
ほとんど理解できてないみたいだから
より単純なB木から学んだ方がいい。

454:デフォルトの名無しさん
08/09/16 18:38:15
４つの都市A、B、C、Dのそれぞれの距離がわかっている状態で、
xy平面上に正しくA、B、C、Dを配置したいのですが考え方がわかりません。
アドバイスをいただけないでしょうか？

455:デフォルトの名無しさん
08/09/16 19:12:08
回転どうすんだ

456:デフォルトの名無しさん
08/09/16 21:57:19
>>454
三角関数

457:デフォルトの名無しさん
08/09/16 22:07:09
>>454
回転が確定しなくていいなら、相対測位とかいうキーワードでぐぐれ。

458:454
08/09/17 16:07:09
455様、456様、457様返信ありがとうございます。
余弦定理を用いて半径ACと半径BCの円の交点を考えC点を導いたのですが
次のD点を考えるときに半径AD・BD・CDの円が（当たり前かもしれませんが）１点で交わらないので求められませんでした。
455様と457様が言っている「回転」が必要だなと思い、
B点をA点のまわりで距離ABを保ちつつグルグル回るようにしたのですが、どうも違うみたいで困ってしまいました。
回転についての詳しい説明を教えていただけないでしょうか？

今は下のような状態になっています。
URLﾘﾝｸ(www.dotup.org)
赤・青の円は半径AC・BCの円でC点（黄緑）を求めました。
薄い赤・青・緑の円は半径AD・BD・CDの円でとりあえず円AD・BDの交点から仮のD（紫)を導いたところです。

よろしくお願いします。

459:デフォルトの名無しさん
08/09/17 17:00:27
４点が平面上にないだけじゃないの？
分かりやすい座標で１回やってみた方がよさげ。

460:デフォルトの名無しさん
08/09/17 22:38:41
3点の位置が決まって距離もわかってて4点目が交わらないってあるのかな？
各点間の距離データはあってるんだよね？？

461:デフォルトの名無しさん
08/09/18 00:59:48
現実の都市間の距離だったりして・・・

とはいえその場合でも、対称を同一視すれば一意に求まるはず。

462:デフォルトの名無しさん
08/09/18 02:23:10
>>459,461
それだ。
現実の都市間の距離で、球面上には矛盾無く配置できるけど平面上では矛盾無く配置できないとかな。

とりあえず454はそれぞれの距離を提示するべき。

463:454
08/09/18 14:11:16
459様、460様、461様、462様返信ありがとうございます。
まず都市ABCDが現実に存在する都市かどうかですが、この世に存在しない都市を仮定しています。
そのため距離は毎回乱数で定まっています。
最初に断わっておくべきでした申し訳ないです。

4点が同一平面上にない場合があることは考えていませんでした。
今回の考え方を元に、単語同士の非関連度を距離に置き換えてそれぞれを配置するプログラムを作ろうかと思っていたのですが、
平面上のみで考えるのは無理があるのでしょうか。

464:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/09/18 17:25:13
何点あっても、二点間の間での距離だけを定義すればうまくいくんじゃね？
完全ランダムでは無理条件ができるけど

466:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/09/19 00:48:36
質問させて頂きます。

XY平面上に、その座標データを保持するオブジェクトが複数個あり、
それらの座標はそれぞれランダムだったとします。

それぞれのオブジェクト間の距離が一定以下の場合は、
一定距離の間隔を置けるように引き離し、
さらにオブジェクトの距離の一番近いオブジェクトを探す
というようなことをしたいのです。

この処理はリアルタイムループ内で実行するので、
引き離しは1距離だけ離れるだけで十分であるとします。
一応は下記のようなプログラムで実装は出来ているのですが、
オブジェクトの数が増えた場合に処理が急激に重くなります。

この処理の計算量がn^2であるので、
オブジェクトの数が100、200と増えていった場合には
とてもリアルタイムループでは遅すぎる速度になってしまうのです。

何とかしてこの計算量を減らす方法はないものでしょうか？

469:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/09/19 01:27:09
>>468
動的ボロノイ図を使えば，一反復が O(n + k log n) でできる．
ただし k は引き離す必要のあるペアの数．

ただ，これは実装が結構しんどいので，現実的には
x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て
枝刈りするのが有力だと思う
（x 座標が一定距離を超えたら，距離が一定距離以下にはならない等）
計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず．

なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると
多少の効率化ができる．

471:デフォルトの名無しさん
08/09/19 19:43:55
>>470
動的ボロノイ図は調べてみましたがサッパリ理解できませんでした（汗

なので後者のソートして近いところから探す方法を試してみたところ、
オブジェクト800個くらいまでは実用レベルの速度で動くようになりました。
但しやはり位置関係によっては重くなることもあり、
必ずしも安定しているとは言えませんが、
総当りに比べれば桁違いの速度になりました。

ありがとうございました。

472:デフォルトの名無しさん
08/09/19 23:01:01
「一定距離」の間隔でマス目に区切って、マス目毎にデータをコレクションで持ち、
引き離し処理をするときには、データとその周囲の9マス分の範囲だけ調べるとか。
□□□□□
□■■■□
□■▲■□ ←▲のところが自分の属すマス
□■■■□
□□□□□
データの散らばってる範囲が狭過ぎると密集して役に立たないし、
逆に広過ぎるとマス目の管理を工夫する必要があるけど。
あと、「一定距離」以上でも最も近い点を取得する必要があるなら、これじゃだめかも。

473:デフォルトの名無しさん
08/09/19 23:06:33
ヒューリスティックだけど、自己組織化で適当に動かしてみるとか。

474:デフォルトの名無しさん
08/09/20 11:26:32
すまん、図形描画アプリみたいなものを作ってるんだが･･･
次のようなもので悩んでます。
１．複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか?
場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。
総当たり以外でエレガントな方法というとどんなんざんしょ?
２．同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。

教えてエロイ人･･･

475:デフォルトの名無しさん
08/09/20 12:15:00
メモリが許せば、思い切って座標にオブジェクトを持たせるとか。

476:デフォルトの名無しさん
08/09/20 12:15:42
>>475は>>468にです。

477:468
08/09/20 18:05:06
お返事ありがとうございます。

>>472
空間分割とかいうやつですかね？
しかしこれは「最も近い点を取得する」という場合に
やはりお察しのように問題がありまして、
結局こちらの方法は諦めたのであります。
一応この最も近い点を探す距離も制限されてはいるのですが、
結構範囲が広いのでその表現は省かせていただきました。

>>475
これはその空間分割の究極ですね・・・
しかしこれはまた違う方向で膨大な判定量になりそうな気がします。

478:デフォルトの名無しさん
08/09/20 19:00:54
>>477
472の亜種だと思うけどＸ，Ｙ軸上でソートして、各軸上の分布をクラスタとして扱うっていうのがGameProgrammingGEMに載っていた。

479:デフォルトの名無しさん
08/09/20 21:40:57
>>474
問題が明確じゃないのだけれど，

(1)
『描画する』条件は，単に『別の矩形に包含されないこと』でよい？
それとも，矩形間に上下関係（例: Windowsのウインドウ）がある？

(2)
『描画する』条件は (1) と共通ということでよい？
それと，曲線はどのような形で与えられる？（例：ベジエ曲線）

何にせよ平面走査型のアルゴリズムが有力に動くと思う．

480:デフォルトの名無しさん
08/09/21 11:23:34
ナップサック問題とは、価値と重量があるものを、入れられる重量に制限がある箱に
一番価値が高くなるように効率よくいれるにはどういれたらよいかの手順を考える問
題ですよね。

これに、価値が高くなることに加えて、入れる順番も重さがあるものから入れる、あるいは
軽い順に入れるなどの制限が加わった場合にどのようにすればよいかという解法は
存在しますか？

481:デフォルトの名無しさん
08/09/21 11:59:36
>>480
入れるものを決めた後で重量でソートすればいい

482:474
08/09/21 12:35:56
>>479
不明確ですいません･･･orz
1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。
２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。

平面走査型ちょっくらぐぐってきます。

483:デフォルトの名無しさん
08/09/22 00:32:18
>>481
書くべき事がたりませんでした。。。
では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない
というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？

484:デフォルトの名無しさん
08/09/22 02:43:01
DP使うしかないんじゃない？

485:デフォルトの名無しさん
08/09/23 09:49:23
>>480
状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ．

重さが自然数であれば，品数を n，重さの最大値を W としたとき
普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば
O(n^2 W) のアルゴリズムが簡単に作れる．

重さが実数であれば，基本的には枝刈り探索しかないのだから，
上の三つ組みを持って適当に探索する．
本気を出すなら，品数や重さなどによって適切な探索法が変わるけど
そこまでがんばるかい？

486:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/09/25 01:27:20
ポリオミノ自動生成アルゴリズムって、起点を中心にどんどん成長させていって、
それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。

488:デフォルトの名無しさん
08/09/25 19:54:18
自動生成って何？

指定したサイズのもの全てとか、小さい順とかで列挙すること？
それとも、条件を満たすもののサンプリング？

489:デフォルトの名無しさん
08/09/25 21:02:22
nの数を与えて、その全パターンを出すアルゴリズムです。
n=7なら、108通り全部とか。

490:デフォルトの名無しさん
08/10/19 01:32:31
あげ

491:デフォルトの名無しさん
09/01/18 20:54:29
age

492:デフォルトの名無しさん
09/01/19 19:28:43
良スレの予感

493:デフォルトの名無しさん
09/01/19 23:10:09
DBMについて興味があり、最近書籍やウェブなどをあたっていました。
B-Treeなどのアルゴリズムについてなんとなく理解したのですが、
それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
C言語で実装されているソースの解説などどこかにあるでしょうか。
もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、
ちょっと敷居が高いです。

494:デフォルトの名無しさん
09/01/20 01:02:00
いきなりF1に乗ろうとする奴っているよね。