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に乗ろうとする奴っているよね。