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に乗ろうとする奴っているよね。
495:デフォルトの名無しさん
09/03/03 06:57:31
>>493
>それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
互換性が要らないならバイナリでダンプしてもいいし、サイズを優先してバイナリで
writeしてもいい。互換性を重視するならテキストでwriteするといい。
速度を優先するならseekしたほうがいい。言語によってはシリアライズ機構がある。
よく分かっただろう？
496:デフォルトの名無しさん
09/03/03 08:09:55
>>493
自分で実装したC#のソースなら持ってるけど
497:デフォルトの名無しさん
09/03/04 18:34:35
そのseekってなんのこと？
498:デフォルトの名無しさん
09/03/05 06:32:12
速いライブラリを自分で探せってこった。
499:デフォルトの名無しさん
09/03/20 20:01:14
499
500:デフォルトの名無しさん
09/03/20 20:56:21
500
501:デフォルトの名無しさん
09/03/20 21:16:26
>>493
ISAM
502:デフォルトの名無しさん
09/03/20 23:09:41
URLﾘﾝｸ(page4.auctions.yahoo.co.jp)
503:デフォルトの名無しさん
09/04/01 00:32:52
多角形の頂点の座標が配列で与えられている時に
その図形の重心を求めるアルゴリズムを教えてください。
頂点の数は３以上。
全ての辺について、他の辺と交差することは無い。
一つの角の大きさは0～360度。
504:デフォルトの名無しさん
09/04/01 00:43:45
三角形の場合なら公式かなんかあったんだっけ？重心って。
多角形の場合は、三角形に分割して、
それぞれの重心に対して、面積で重み付けして相加平均かな。
505:デフォルトの名無しさん
09/04/01 00:58:49
504で十分だけど、以下も参考になるかもしれない。
URLﾘﾝｸ(oshiete1.goo.ne.jp)
506:デフォルトの名無しさん
09/04/01 01:09:53
>>504-505
これで先に進めそうです。
ありがとうございました。
507:デフォルトの名無しさん
09/04/08 10:28:33
ははは
508:デフォルトの名無しさん
09/06/21 20:30:51
漏れはアルゴリズム考えてると頭痛がしてくるからブルートフォースでいいやと思ってたけど
百万個を20ステップでバイナリサーチするlog nの威力を前にしてあっさり宗旨替えしたｗ
509:デフォルトの名無しさん
09/06/21 21:06:10
バルバロイもそうやって教化されていくんだな
510:（ナワバリ付き）グループ内問題なら処理を軽くする法
09/06/21 21:48:11
>>468 見てとっさに「過密ストレス指標」と
「指標が高い奴は低い奴に八つ当たりOK」
っていう移動対象絞り込み方が浮かんだ…
特定対象ばかりが連続移動を避けたい時？
実際には、完全独立自由主義でなければ
ご近所さんグループで扱う方がいいかな
グループ内成員どうしが比較的接近してて
他のグループの成員とは離れている場合
「外」への移動を好ませればいいのかな
平面なら上が第一候補、ダメなら右など
優先でダメなら時計回りに選択肢変更
一通り計算後グループ内を一斉移動
明確なグループがなければ初期座標で分類
以降はそれに従う（大きな変動がなければ）
通信などによって掛かる時間が移動させる
対象の個数そのものならこんな感じかな？
均等に散らばってれば走査線が一番？
研究・ライブラリ等充実してるようだし
(「MMORPGのアイテムやPCの移動じゃないんだから…w」
※身内や同画面内の都合なら移動もガマンしてくれる等
511:デフォルトの名無しさん
09/06/22 23:33:24
そうは言うけど、ソートしとかないと駄目じゃん。
ソートのステップ数も入れて考えられた？
512:デフォルトの名無しさん
09/07/27 18:33:04
あげ
513:デフォルトの名無しさん
09/07/27 21:07:38
COSS age。今年は東工大でやってるわけだが、参加してる人はいるかい。
514:デフォルトの名無しさん
09/07/29 07:01:46
素数をぷりぷり生成し続けるアルゴリズムを教えて下さい
515:デフォルトの名無しさん
09/07/29 07:07:20
つ[エラトステネスの篩]
516:デフォルトの名無しさん
09/07/29 07:15:13
2 3 5 7 9 11 13 ..ってプリプリ垂れるんですよ
だとしてもエラトスに帰着されるのですか？
517:デフォルトの名無しさん
09/07/29 09:05:55
>>516
「ぷりぷり生成」の意味が曖昧。
518:デフォルトの名無しさん
09/07/29 09:17:27
URLﾘﾝｸ(www.nicovideo.jp)
519:デフォルトの名無しさん
09/07/29 12:23:11
一般的に次の素数を求める方法、というのは存在しない。
したがって、（最初の2を別として）奇数を順に生成して、それを
ふるいにかけるという方法しかない。
520:デフォルトの名無しさん
09/07/29 12:42:47
>>519
> 一般的に次の素数を求める方法、というのは存在しない。
マジ？詳しく教えて
521:デフォルトの名無しさん
09/07/29 13:25:07
>>517
2 からスタートして永遠に次に大きい素数を吐き出し続ける事とします
522:デフォルトの名無しさん
09/07/29 14:38:46
>>521
メモリは無限にあるとしてよいならば試し割りなり篩なりで十分。
高々有限ならば、不可能。
523:デフォルトの名無しさん
09/07/29 15:18:33
>>522
無理しなくていいよ
たまには素直になろうね
524:デフォルトの名無しさん
09/07/29 16:11:26
なに上のレス？おつむおかしい人？
>>516のように2,3,5,7,9,11,13とぷりぷりたれるだけなら、
a[0]=2,a[1]=3,a[n+1]=a[n]+2で十分だろ
9を素数だと思ってんだしさ
このテの人はどうせめちゃくちゃ大きい素数なんて出力させないんだし、
試し割りでも採用してればいいだろｗ
525:デフォルトの名無しさん
09/07/29 16:19:43
これは酷い
526:デフォルトの名無しさん
09/07/29 16:39:48
馬鹿にしないで下さい＞＜
527:デフォルトの名無しさん
09/07/29 17:28:28
long a[100000],al=0;for(long i=2;i<200;i++)for(long j=0;(j<al && a[j]*a[j]<=i)?i%a[j++]!=0:0==printf("%d : %d\n",al,a[al++]=i););
これで200個ぷりぷりでます
これ以上圧縮してかけなかったｗ
528:デフォルトの名無しさん
09/07/29 18:34:01
ぐぐったもの。動作確認はしていない。
x[1<<15],w=1200,p,r;main(s){for(;++s<w;)for(x[p+=r==1]=r=s;s%--r;);}
529:デフォルトの名無しさん
09/07/29 19:31:03
毎回エラトスするよりも
素数はメモライズしていった方が速いわけですね
でもこのやり方はメモリも無尽蔵に使うということですかね
530:デフォルトの名無しさん
09/07/29 19:59:53
FOR N=1 TO 12251:PRINT PRM(N):NEXT
531:デフォルトの名無しさん
09/07/29 20:46:49
そういえば、一つ前の素数を返すアルゴリズムはみつかってたような気がするな
確かwikiで見たが、思い出せん
532:デフォルトの名無しさん
09/07/29 20:54:28
一つ前の素数じゃなかったし、まだ証明されてなかった(フォーチュン予想)
これとは別に、wikiに解が素数となる式が載ってるね
常人には理解不能だわ
wz + h + j ? q = 0
(gk + 2g + k + 1)(h + j) + h ? z = 0
(16k + 1)3(k + 2)(n + 1)2 + 1 ? f2 = 0
2n + p + q + z ? e = 0
e3(e + 2)(a + 1)2 + 1 ? o2 = 0
(a2 ? 1)y2 + 1 ? x2 = 0
16r2y4(a2 ? 1) + 1 ? u2 = 0
n + l + v ? y = 0
(a2 ? 1)l2 + 1 ? m2 = 0
ai + k + 1 ? l ? i = 0
((a + u2(u2 ? a))2 ? 1)(n + 4dy)2 + 1 ? (x + cu)2 = 0
p + l(a ? n ? 1) + b(2an + 2a ? n2 ? 2n ? 2) ? m = 0
q + y(a ? p ? 1) + s(2ap + 2p ? p2 ? 2p ? 2) ? x = 0
z + pl(a ? p) + t(2ap ? p2 ? 1) ? pm = 0
533:デフォルトの名無しさん
09/07/29 22:48:35
>>532
どこのwikiに載ってたの？
534:デフォルトの名無しさん
09/07/30 07:13:02
Wikipediaをwikiって略すなー、な所だな
535:デフォルトの名無しさん
09/07/30 12:13:47
ところでウィキペディアにフォーチュンの予想はない件
536:デフォルトの名無しさん
09/07/30 12:42:35
フォーチュンってどれくらい偉い人？
声優で喩えて
537:デフォルトの名無しさん
09/07/30 13:38:19
石丸博也くらい
538:デフォルトの名無しさん
09/07/30 15:11:05
そんなに偉い人だったのか 僕もヌンデマス
539:デフォルトの名無しさん
09/07/30 17:33:34
>>535
google books で、ウェルズのプライムナンバーズの訳本が読めるぞ。
該当箇所は、P122だけど、ちょうどそこは読める範囲にある。
興味があればどうぞ。
540:デフォルトの名無しさん
09/07/31 02:19:19
フォーチュンってサモアのデマで有名なマーガレット・ミードの旦那かよ
541:tor.rootkit.de
09/08/17 17:57:46
自動焼人 ★ ＝ 自動保守 ◆KAWORUKOFI ＝ 自動保守#K9K?_D[L
名言集 その１
『アパッチ砲はワシが作った』
URLﾘﾝｸ(jbbs.livedoor.jp)
自分の管理するしたらばで借りた掲示板にて
> 5062 ：自動保守 ◆AOIMAD.NZM [] ：2009/08/16(日) 00:46:29 ID:nQYgq9jg0
> そもそも、アパッチ砲っていうのは、私が指揮官になった時代に私の先輩たちが導入して
> 先輩たちが命名したもの、っていうかまぁ、そういう砲は今まで存在してないから
> 名前つけなくちゃいけないしｗ
>
> ってことで、使っているうちに広まった名前なので、それが正式名称になるんじゃないかと。
>
> URLﾘﾝｸ(www.paradisearmy.com)（俺の先輩が命名）
> URLﾘﾝｸ(www.paradisearmy.com)（俺が命名？）
※注 「アパッチ砲」の正式名称は「Apache Jmeter」で、もちろん自動焼人の先輩が作ったものではありません
----------------------------------------------
この自動焼人 ★メールマガジンの配信停止をご希望される方は
ｽﾚﾘﾝｸ(sec2chd板)
にて自動焼人 ★までご連絡ください
542:デフォルトの名無しさん
09/11/09 05:02:04
平方根を求めるアルゴリズム下さい
小数点演算を使用せず整数のまま演算し、
実数の平方根を超えない最大の整数を返すものとします
543:デフォルトの名無しさん
09/11/09 06:29:51
isqrt.c でググれ
544:デフォルトの名無しさん
09/11/09 08:42:18
つ 「ニュートン法」
545:デフォルトの名無しさん
09/11/09 12:09:28
１から元の値の間で二分法が簡単かな
546:デフォルトの名無しさん
09/11/09 20:55:55
int sqr(int n){int i=0;for(;i*i<=n;i++);return i-1;}
547:デフォルトの名無しさん
09/11/11 09:09:02
f(x)=x^2-n
f'(x)=2x
2a(x-a)+(a^2-n)=0
x=(n+a^2)/2a
>>> def x(n, a):
... b = (n+a*a)/(2.0*a)
... if b - a > -0.000000001 and b - a < 0.000000001:
... print b
... else:
... x(n, b)
...
>>> x(2, 1)
1.41421356237
548:デフォルトの名無しさん
09/11/11 09:43:10
小数使うなって書かれた上に、>>546 がそれ用の答え書いてくれてるのに
なんでニュートン方の実装例出してるの？
549:デフォルトの名無しさん
09/11/11 10:39:58
>>546 を「答え」とか
550:デフォルトの名無しさん
09/11/11 10:49:46
>>548
2の平方根が1とかって意味あんのか？
551:デフォルトの名無しさん
09/11/12 01:38:30
以下のような多次元項の因数分解を近似的に行うプログラムを書きたいのですが…、
最小自乗などなら解けるかなと思ったのですが…、どなたかご教授願います。
問題：
ΣCkX^k→Σ(AkXk-Bk)^k+e
すべて実数スカラ値。kの範囲は0<k<n。eは誤差値。^kはk乗の意。
左辺が与えられた時に、eを最小にするAnとBnを求める。
552:551
09/11/12 01:58:02
訂正です
ΣCkX^k→Σ(AkXk-Bk)^k+e
ではなくて
Σ(CkX^k)→Π(AkXk-Bk)^k+e
でした
553:デフォルトの名無しさん
09/11/12 12:50:07
Σ(CkX^k)→Π(AkX-Bk)^k+e
でなく？
554:551
09/11/12 13:38:17
Σ(CkX^k)→Π(AkX-Bk)^k+e です
555:デフォルトの名無しさん
09/11/13 10:02:20
>>546
それバグってルし
556:デフォルトの名無しさん
09/11/13 12:28:15
小数使うなって書かれた上に、>>546 がそれ用の答え書いてくれてるのに
なんでニュートン方の実装例出してるの？
557:デフォルトの名無しさん
09/11/13 12:42:55
>>556
2の平方根が1とかって意味あんのか？
558:デフォルトの名無しさん
09/11/14 23:12:53
>>557
なんで無いと思うんだ？
559:デフォルトの名無しさん
09/11/15 09:52:32
>>558
>>548-550
>>556-557
560:デフォルトの名無しさん
09/11/15 10:20:04
>>557
いや、そういう仕様だし。
これを平方根だというから誤解が生じるんであって、
「(int)floor(sqrt(x)) の値を float 介さず求める関数を作れ」でしょ。
561:デフォルトの名無しさん
09/11/16 23:15:10
単に開平法をさせたいだけじゃないの？
562:デフォルトの名無しさん
09/11/16 23:33:04
いやいや、ちゃんと >>542 読めよ。
「実数の平方根を超えない最大の整数を返すものとします」
563:デフォルトの名無しさん
09/11/17 23:52:09
高速 sqrt 整数 でググったらおもしろいの見つけた
整数なら各ビット毎に収束させる事で必要ビット数の半分のループ（32bitなら16)で解がでるのね
564:デフォルトの名無しさん
09/11/18 02:02:43
>>563
事実上>>545の亜種のような気がするが…
565:デフォルトの名無しさん
09/11/18 12:28:24
亜種と言うかまんま
566:デフォルトの名無しさん
09/11/18 12:43:06
unsigned int isqrt(unsigned int x)
{
unsigned int s, t;
if (x == 0) return 0;
s = 1; t = x;
while (s < t) { s <<= 1; t >>= 1; }
do {
t = s;
s = (x / s + s) >> 1;
} while (s < t);
return t;
}