- 1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ]
- データ構造とアルゴリズムに関する総合スレ。
【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
toro.2ch.net/test/read.cgi/tech/1217773415/
- 367 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 01:03:18.89 ]
- 半開きハッシュと名付けた
- 368 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 01:38:15.37 ]
- こないだから宿題貼り付ける奴がちらほらいるが
そのどれも分からなかった俺は才能が無さ過ぎた
- 369 名前：デフォルトの名無しさん [2012/07/27(金) 08:00:24.64 ]
- >>361
黙れバカw
空気読んで答えやがれ
- 370 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 08:13:45.67 ]
- ↑お前が馬鹿
- 371 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 09:41:12.30 ]
- 馬鹿には無理
- 372 名前：デフォルトの名無しさん [2012/07/27(金) 10:18:48.93 ]
- >>370
>>371
バカはお前ら
お前らのパッパラパーなアルゴリズムでさっさと俺様を笑わせやがれ
- 373 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 11:49:22.94 ]
- 馬鹿には無理
- 374 名前：デフォルトの名無しさん [2012/07/27(金) 12:10:13.43 ]
- >>373
お前には無理と言うことかw
- 375 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 19:08:10.29 ]
- >>374
お前が馬鹿
- 376 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 19:54:35.27 ]
- ＿＿＿＿
／∵∴∵∴＼
/∵∴∵∴∵∴＼
/∵∴∴,（・）（・）∴|
|∵∵／ ○ ＼|
|∵ / 三 | 三 | ／￣￣￣￣￣
|∵ | ＿_|＿_ | ＜ うるせー馬鹿！
＼| ＼＿/ ／ ＼＿＿＿＿＿
＼＿＿＿_／
- 377 名前：デフォルトの名無しさん mailto:sage [2012/07/27(金) 20:23:22.78 ]
- どーでもいい。
- 378 名前：記憶喪失した男 忍法帖【Lv=9,xxxP】 [2012/07/28(土) 07:59:18.69 BE:3079593959-2BP(3)]
- 入力された内容は次のとおりです。
■件名： 日本のロボットトレーディングサイト「カブロボ」について
■ご意見・ご感想：
ロボットトレーディング、あるいはアルゴリズム取引トレーダーについて、少しは知識を得ました。その現状について知ったところ、やはり憂慮すべき事態だったため、意見申し上げます。
「カブロボ」というサイトを知りました。そのサイトについての意見です。政府として、このようなサイトを支援していただきたく思います。
アルゴリズム取引トレーダーとしては、株だけでなく、債券、為替取引にも当然対応するべきであります。
また、株、債券、為替取引は、現実に存在する二百か国以上の国や地域を網羅する必要があります。
それが賢いアルゴリズム取引トレーダーのするべきプログラムであり、
たった三百銘柄の仮想取引では、日本の投資家を育てるのに不適切だと思われます。海外銘柄を扱わないアルゴリズム取引トレーダーに魅力を感じません。
扱う銘柄を、全世界の株、債券、為替をすべて網羅する上級者向けのカブロボを立ち上げることを希望いたします。
- 379 名前：デフォルトの名無しさん [2012/07/28(土) 10:23:42.25 ]
- >>375
バカw
- 380 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 11:39:47.47 ]
- >>324
その学科何年か前は違う名前じゃなかった？
- 381 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 14:26:03.68 ]
- >>378
当事者が遊びで作ってるものに政府が金なんか出す訳ないだろ
- 382 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 21:18:50.51 ]
- ぷよぷよのAIを作っているんですが窒息死します
どうすればいいですか
- 383 名前：デフォルトの名無しさん mailto:sage [2012/07/28(土) 22:12:51.40 ]
- ぷよぷよで強いAIってどうすんの？
toro.2ch.net/test/read.cgi/tech/1336825232/
- 384 名前：デフォルトの名無しさん mailto:sage [2012/07/29(日) 10:05:48.14 ]
- >>383
こんなスレあったんですか
ありです
- 385 名前：デフォルトの名無しさん [2012/07/31(火) 08:19:02.42 ]
- ﾌﾟｯ
- 386 名前：デフォルトの名無しさん mailto:sage [2012/07/31(火) 09:24:11.53 ]
- ﾖｯ
- 387 名前：デフォルトの名無しさん mailto:sage [2012/07/31(火) 09:52:41.53 ]
- ﾌﾟｯ
- 388 名前：デフォルトの名無しさん mailto:sage [2012/07/31(火) 21:35:14.84 ]
- ﾖｯ
- 389 名前： 【大吉】 mailto:sage [2012/08/01(水) 08:41:13.81 ]
- O(N)
- 390 名前：デフォルトの名無しさん mailto:sage [2012/08/02(木) 10:09:55.05 ]
- ｵﾅﾗﾌﾟｰ
- 391 名前：デフォルトの名無しさん mailto:sage [2012/08/02(木) 20:47:04.14 ]
- ガベージ・イン／ガベージ・アウト：
善き人々が悪しきプログラムに手を染める時
practical-scheme.net/trans/gigo-1997-03-j.html
- 392 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 20:45:11.38 ]
- ハッシュだけどチェイン法＞開番地法なんだよね？でなければ溢れを気にする必要はないからね
ハッシュのチェインの長さに制限があるやつの削除、参照の計算量の解析ってどっかにない？
- 393 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 20:56:13.76 ]
- 「チェイン法＞開番地法」
この意味は何？
- 394 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 21:49:02.14 ]
- 参照、追加、削除の計算量です
- 395 名前：デフォルトの名無しさん mailto:sage [2012/08/03(金) 22:12:44.83 ]
- A>B はAのほうが良い、ってことで
- 396 名前：デフォルトの名無しさん mailto:sage [2012/08/04(土) 18:35:46.31 ]
- >>392
> 長さに制限があるやつ
って何よ。
ハッシュ値が衝突した要素を格納するためのコンテナの計算量でいいんじゃないの？
- 397 名前：デフォルトの名無しさん mailto:sage [2012/08/05(日) 17:00:36.26 ]
- ハッシュ法って、均したらまともな実装ならO(1)にならにゃいかんのでは？
- 398 名前：1/4 mailto:sage [2012/08/06(月) 18:50:54.98 ]
- アルゴリズム考えてもらえませんか。
恥ずかしながら、一応自分の考えたのも載せます。
ただ、絶対もっとスマートな解法があると思うのでよろしくお願いします。
ちなみに言語は PHP です（＞＜）
【問題】
整数が二つ入った配列がいくつかあります。(配列の配列)
これは何らかの数列の範囲を表しています。
最初の数字が範囲の開始位置、二つ目の数字が範囲の長さ。
例えばこんな具合です。
$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 2 ),
array( 4, 1 ),
array( 8, 2 ),
array( 10, 5 ),
array( 10, 6 )
);
------------- 長いので続きます --------------
- 399 名前：2/4 mailto:sage [2012/08/06(月) 18:52:06.84 ]
- ---続き---
抽象的に書くとこうなりますか。
$data = array(
array( a1, b1 ),
array( a2, b2 ),
--- 中略 ---
array( an, bn ),
);
a1からanは昇順にソート済みです。
同じ値の場合もあります。
b1からbnは1以上で不定です。
$data は、ある数列の 0番目から3スパン、2番目から1スパン、4番目から2スパン...という意味です。
ただし、この $data は範囲の重複の可能性があります。
実現したいアルゴリズムは、この $data が示す範囲を重複のない形で再定義することです。
- 400 名前：3/4 mailto:sage [2012/08/06(月) 18:53:22.57 ]
- ---続き---
例えばそれを実装した関数を linearize とした場合、
$newData = linearize( $data );
の結果は、
array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);
でなくてはなりません。
- 401 名前：4/4 mailto:sage [2012/08/06(月) 18:56:51.88 ]
- ------続き------
こちらが自分が考えた関数です
function linearizedRange( $data ) {
$strage = array();
foreach( $data as $datum ) {
if( isset( $strage[$datum[0]] ) && $strage[$datum[0]] >= $datum[1] ) {
continue;
}
$strage[$datum[0]] = $datum[1];
}
foreach( $strage as $i => $v ) {
$strage[$i] = $v + $i;
}
$len = count( $strage );
if( $len > 1 ) {
$last = null;
foreach( $strage as $i => $v ) {
if( null === $last ) {
$last = $i;
continue;
}
- 402 名前：5/4 mailto:sage [2012/08/06(月) 18:58:01.19 ]
- ------続き------
すいません、予定より1レス多くなりました。
関数の続きです。これで最後です。
if( $strage[$last] >= $i ) {
if( $strage[$last] < $v ) {
$strage[$last] = $v;
}
unset( $strage[$i] );
} else {
$last = $i;
}
}
}
$data = array();
foreach( $strage as $i => $v ) {
$data[] = array( $i, $v - $i );
}
return $data;
}
- 403 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:04:16.15 ]
- $data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 2 ),
array( 4, 1 ),
array( 8, 2 ),
array( 10, 5 ),
array( 10, 6 )
);
↓
array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);
- 404 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:09:14.78 ]
- 理屈がよくわからん
- 405 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:14:28.31 ]
- できた！
function linearizedRange( $data ) {
$n = -1;
$result = array();
foreach( $data as $datum ) {
if ($dataum[0] > $n) {
$result[] = $dataum;
$n = $dataum[0] + $dataum[1];
}
}
return $result;
}
- 406 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:15:48.26 ]
- でたらめを教える悪い例
- 407 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:20:34.70 ]
- DPでいけそう
Viterbトレリスを作って一発
- 408 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:23:59.40 ]
- ならばこうか！
function linearizedRange( $data ) {
$n = -1;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($dataum[0] > $n) {
if ($t !== null) {
$t[1] = $dataum[0] - $t[0];
$result[] = $t;
}
$t = $dataum;
$n = $dataum[0] + $dataum[1];
}
}
$p = array_pop($data);
$t[1] = $p[0] + $p[1] - $t[0];
$result[] = $t;
return $result;
}
- 409 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:25:08.27 ]
- 動かないコードなど無意味
- 410 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:28:20.86 ]
- うおりゃ！スペルミス直したぞ！
function linearizedRange( $data ) {
$n = -1; $m = 0;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($datum[0] > $n) {
if ($t !== null) {
$t[1] = $datum[0] - $t[0];
$result[] = $t;
}
$t = $datum;
$n = $datum[0] + $datum[1];
}
if ($datum[0]+$datum[1]>$m) {
$m = $datum[0] +$datum[1];
}
}
}
$t[1] = $m - $t[0];
$result[] = $t;
return $result;
}
- 411 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:30:11.37 ]
- 動かないぞ
- 412 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 20:31:20.11 ]
- 括弧が一つ多かった！直したぞ！
function linearizedRange( $data ) {
$n = -1; $m = 0;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($datum[0] > $n) {
if ($t !== null) {
$t[1] = $datum[0] - $t[0];
$result[] = $t;
}
$t = $datum;
$n = $datum[0] + $datum[1];
}
if ($datum[0] + $datum[1] > $m) {
$m = $datum[0] +$datum[1];
}
}
$t[1] = $m - $t[0];
$result[] = $t;
return $result;
}
- 413 名前：5/4 mailto:sage [2012/08/06(月) 22:54:42.75 ]
- >>412 さん、さっそくありがとうございますｍ（＿＿）ｍ
凄く短いコードなので感動しました(^-^)
が、どこか不具合がある模様です(-_-;)
例題の
$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 5 ),
array( 5, 1 ),
array( 10, 2 ),
array( 12, 3 ),
array( 12, 4 )
);
の答えが
- 414 名前：398 mailto:sage [2012/08/06(月) 22:55:22.08 ]
- Array
(
[0] => Array
(
[0] => 0
[1] => 4
)
[1] => Array
(
[0] => 4
[1] => 6
)
[2] => Array
(
[0] => 10
[1] => 6
)
)
になってしまいました(´・ω・`)
- 415 名前：398 mailto:sage [2012/08/06(月) 22:56:52.95 ]
- Array
(
[0] => Array
(
[0] => 0
[1] => 4
)
[1] => Array
(
[0] => 4
[1] => 6
)
[2] => Array
(
[0] => 10
[1] => 6
)
)
になってしまいました(´・ω・`)
- 416 名前：398 mailto:sage [2012/08/06(月) 23:11:31.65 ]
- 別のデータを用いて模式図を書くとこうなります
( 0, 3 ) … データ1
( 2, 1 ) … データ2
( 4, 1 ) … データ3
( 5, 1 ) … データ4
01234567.... 数列
---------------------
***___________データ1
__*___________データ2
____*_________データ3
_____*________データ4
***_**________求める答え(V)
V1 = (0,3)
V2 = (4,2)
こうしてみるとOR演算ですね
- 417 名前：デフォルトの名無しさん mailto:sage [2012/08/06(月) 23:49:58.47 ]
- #PHPのことはわからんのに、適当に投げてみる
#どうせどっかでエラーが出る
function linearizedRange( $data ) {
$max = $min = $data[0][0];
$result = array();
foreach( $data as $datum ) {#----
if ( $datum[0] > $max ) {#====ギャップ感知
$result[] = array( $min, $max - $min );
$min = $datum[0];
}#====
if ( $datum[0] + $datum[1] > $max ) {#====
$max = $datum[0] + $datum[1];
}#====
}#----foreach
$result[] = array( $min, $max - $min );
return $result;
}
- 418 名前：398 mailto:sage [2012/08/07(火) 00:47:35.30 ]
- >>417
m(__)m
もう、ほんとうに感謝感謝感謝です。
ありがとうございます。
しかもそのまんまコピペでOKでした。
>>417 さん以外の皆様もありがとうございました。
どこか別の場所で恩返しできるといいです。
- 419 名前：398 mailto:sage [2012/08/07(火) 00:53:50.40 ]
- あぁ、そうかぁ、
$result に格納するタイミングは
datum[0] > $max
のときとループを抜けた最後だけでいいわけか・・・
すごくなるほど。
- 420 名前：398 mailto:sage [2012/08/07(火) 01:03:25.12 ]
- あと、元のデータが ( 開始位置, 幅 ) だったので
それをループの中でいったん終了位置を $max として求めているのですね。
ということは、元のデータを ( 開始位置, 終了位置 ) として同じコストで作成できるとするならば、
それを採択した方がより良いアルゴリズムになるのですね。
元データの取得方法を再検討してみます。m(__)m
- 421 名前：デフォルトの名無しさん mailto:sage [2012/08/07(火) 02:43:10.51 ]
- 宿題は宿題スレって約束忘れちゃったのかおまえら
- 422 名前：デフォルトの名無しさん mailto:sage [2012/08/09(木) 18:31:48.66 ]
- ヒープソート、書き換わってるなw
- 423 名前：デフォルトの名無しさん mailto:sage [2012/08/10(金) 07:22:34.38 ]
- ホントだ
- 424 名前：デフォルトの名無しさん [2012/08/14(火) 13:57:01.43 ]
- あらゆる状況や環境を無視して質問するんだけど
STXとETXで囲まれたバイト列を取得 というとき、
<STX>unko<STX>chinko<ETX>
というならびになっちゃってるときは chinko オンリーが正解か
unko<STX>chinko が正解か、どっちがセオリーかなぁ
- 425 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 14:05:59.01 ]
- 最長一致にするか最短一致にするかは
セオリーというより定義の問題だ
- 426 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 14:06:25.67 ]
- 後者。
/*foo/*bar*/ だってコメントアウトされるのは foo/*bar でしょう。
- 427 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 14:20:48.63 ]
- >>426
そっちの方が作るのも楽なんだけどさ
なんでわざわざ囲ってんのか という根源的なとこを思うと
chinkoオンリーが正解な気がするんだよな
- 428 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 15:07:33.07 ]
- >>427
プロトコル定義次第。
・<stx>で始まり、<etx>で終わるまで全てがデータ(unko<stx>chinko)
・<stx>で始まり、<etx>以外の制御コードを含まない区間がデータ(chinko)
・<stx>で始まり、<etx>以外の制御コードを無視した区間がデータ(unkochinko)
・<stx>で始まり、<etx>で終わるまでがデータだからネストを認め、内側から有効とする(chinko)(unkoはペンディング)
・<stx>で始まり、<etx>以外の制御コードが出現したらその後のデータは無効(データなし)
ちょっと考えただけでもこれだけバリエーションが作れる。
要は、エラーに対する強度の問題。
- 429 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 15:10:09.72 ]
- >>427
<stx>が出現したら出力インデックスを初期化するだけだから、作る手間は殆ど変わらないだろ。
- 430 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 15:32:23.36 ]
- >>428
STXとETXに挟まれたもの という定義なんか作った理由って
開始と終了を検知したいということなんだから、
STXまたはETXの見逃しを恐れるべきですね
ということは、STXのあとETXが来ないでSTXきちゃったのは
ETXを読み飛ばしちゃったと思った方がいいんだよな、きっと
つまり、とりあえずchinkoのみを採用すべきとすべきかなぁ
- 431 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 16:03:01.12 ]
- >>430
再入可能かどうかが分からないとなんとも言えないだろ
- 432 名前：デフォルトの名無しさん mailto:sage [2012/08/14(火) 16:13:36.40 ]
- そうか。 再入可能かどうかがキモになるのか。
- 433 名前：デフォルトの名無しさん [2012/08/20(月) 12:52:16.26 ]
- AVL木の回転って適当すぎない？
別に回転じゃないじゃん。
ただ引き上げてるだけで、入れ替えたりしてる時点で
回転ではないだろ。
- 434 名前：デフォルトの名無しさん mailto:sage [2012/08/20(月) 17:32:15.47 ]
- 死ねゴミ共がw
- 435 名前：デフォルトの名無しさん mailto:sage [2012/08/20(月) 20:27:00.20 ]
- >>433
subtreeのrotationじゃなくて、nodeのrotationなんで。
「入れ替え」くらいが適切な訳だったという感じでしょうかぁ↓
- 436 名前：デフォルトの名無しさん [2012/08/21(火) 09:13:13.56 ]
- バカばっかw
- 437 名前：デフォルトの名無しさん mailto:sage [2012/08/21(火) 09:44:31.25 ]
- >>435
いいね！
- 438 名前：デフォルトの名無しさん [2012/08/22(水) 00:06:18.81 ]
- お知恵をお貸しください。
xy平面上にランダムに配置された複数個の点があったとき、
それらを線で結ぶとして、結んだ結果が網の目のように見える
ようなアルゴリズムってありますでしょうか。
完全に見た目だけが目的なので自分でも要件が絞り込めて
いないのですが、網の目のように見えるための要件は
おそらく次のようなものでしょう。
・全ての点が2個以上の他の点と結ばれている
・線同士が交差しない
・近い点同士が結ばれていて、遠い点同士は結ばれない
・線で囲まれた図形は三角形ないし四角形を構成し、五角形以上にはならない
よろしくお願いいたします。
- 439 名前：デフォルトの名無しさん mailto:sage [2012/08/22(水) 00:11:11.92 ]
- ドロネー図でggr
- 440 名前：デフォルトの名無しさん mailto:sage [2012/08/22(水) 23:00:26.94 ]
- >439
ありがとうございます。
ttp://tercel-sakuragaoka.blogspot.jp/2011/06/processingdelaunay_3958.html
↑ここを参考にして実装を進めようと思うのですが、この方法だと、
一度完成したドロネー図から点を削除して線を引きなおすには、
再度（その点を除いた点群を入力として）ゼロから作図しなおす
しか無いのでしょうか？
- 441 名前：デフォルトの名無しさん [2012/08/30(木) 18:01:25.35 ]
- Ｂ木がよく分かりません。誰か簡単に説明してくれませんか？
- 442 名前：デフォルトの名無しさん [2012/08/30(木) 18:23:37.01 ]
- >>441
B木は多分岐の平衡木。
ノードは最大M個のサブノードとM-1個の値を保持する。
ノードの値がM-1個を超えるとノードの分割が行われる。
- 443 名前：デフォルトの名無しさん mailto:sage [2012/08/31(金) 00:00:52.49 ]
- 2分平衡木の存在意義がゼロに
- 444 名前：デフォルトの名無しさん mailto:sage [2012/08/31(金) 20:16:21.92 ]
- ゼロどころではない。もはやマイナスだ。
- 445 名前：441 [2012/08/31(金) 20:35:10.27 ]
- >442
ありがとうございます。
プログラム文がきわめて長いので、使いこなせません…。
- 446 名前：デフォルトの名無しさん [2012/09/01(土) 03:33:46.99 ]
- >>445
プログラム使うだけだったら実装の細部まで理解する必要ないっしょ。
Addメソッドを呼んだらが値を追加できてGetメソッドを呼んだら値を
取得できるというようなことさえわかってればじゅうぶんっしょ。
- 447 名前：445 [2012/09/01(土) 23:51:43.84 ]
- >446
そうですかねえ。確かに文が400行以上あるので(コメントも含めて)、理解は無理っぽいですねえ。
二度目ですが、シェルソートが挿入ソートより速くなる理由を誰か教えて頂けませんか？
- 448 名前：デフォルトの名無しさん mailto:sage [2012/09/02(日) 00:27:54.32 ]
- ランダムに並んだデータを挿入していくと
比較回数の期待値が挿入１回に対しソート済みデータの半分になるけど
先頭に近そうなデータから挿入していけば
比較は後ろの方の１，２回だけとなることが期待できるってことでは
- 449 名前：デフォルトの名無しさん mailto:sage [2012/09/02(日) 00:28:30.47 ]
- １，２回だけ→ほとんどが１，２回くらい
- 450 名前：デフォルトの名無しさん [2012/09/02(日) 00:43:09.47 ]
- >>447
語尾が腹立つから教えてあげない
- 451 名前：447 [2012/09/02(日) 01:05:24.33 ]
- >448-449
ありがとうございます。けれどやっぱり納得できないというか…。最終ソートの前で既に結構比較・交換にコストがかかってる気がして。
>450
何でですかあ？そんな事言わないで下さいよお。
- 452 名前：デフォルトの名無しさん [2012/09/02(日) 06:09:50.86 ]
- >>451
あんまりふざけたこといってるとぶちぎれるゾ（ゝω・）vｷｬﾋﾟ
- 453 名前：451 mailto:sage [2012/09/02(日) 23:53:28.52 ]
- >452
怒ったらダメですう。貴方に足りないのはＣａですよお。(特に深い意味はない)
- 454 名前：デフォルトの名無しさん [2012/09/03(月) 05:10:27.93 ]
- つまんね
- 455 名前：デフォルトの名無しさん mailto:sage [2012/09/03(月) 06:29:18.19 ]
- 例えば挿入ソートだと比較回数は期待値でだいたいこんな感じだろう
右から+の箇所で比較していって*に収まるイメージ(平均なので真ん中)
-----------------------------------*+++++++++++++++++++++++++++++++++++
でもシェルソートのごとく予め4つのグループに分けると比較回数がガクッと減らせる
-----------------------------------*---+---+---+---+---+---+---+---+---
さらに前段階で13のグループに分ければ比較回数が格段に減る
-----------------------------------*------------+------------+---------
いくら前段階というプロセス数が増えるとはいえ、比較や交換回数が小さいわりに
好位置へデータを移動させておくことができるから、全体としてみれば
効率が良くなるんだろう
- 456 名前：453 [2012/09/06(木) 16:51:56.41 ]
- >455
しかし何故そうなるのかが分かりません。
今ヒープソートを勉強してますが、これはさらに分かりません。
- 457 名前：デフォルトの名無しさん [2012/09/06(木) 18:32:25.30 ]
- >>456
挿入ソートでは要素数が多くなると遠くまでテケテケと要素を1個ずつ移動せにゃならんから
超大変。シェルソートでは要素数が増えても離れた要素を交換することで遠くへ移動するときの
コストが減らせちゃうわけ。ゆえに要素数が増えるほどシェルソートが挿入ソートより
速くなるはずよ。
ヒープソートは2分木作っちゃうやつだろ、わかるだろ。
- 458 名前：デフォルトの名無しさん [2012/09/08(土) 19:22:54.12 ]
- 基数ソートって分かりやすいしすばらしいですね。
- 459 名前：デフォルトの名無しさん [2012/09/10(月) 20:53:39.37 ]
- アルゴリズムとデータ構造の質問なんですけど、ここでいいですか？
１．2次元以上で、無限に広がるユークリッド空間があります。
２．空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。
３．ここより先では、砂粒を追加しません。
４．空間上の任意の座標を選びます。
５．選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色？
安定じゃなくてもokです。
こういう状況で、良い検索アルゴリズムってありませんか？
- 460 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 21:04:04.91 ]
- > 安定じゃなくてもok
って、等距離に赤も黒もあった場合は、返す値は赤でも黒でも良いと言いたいのか？
- 461 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 21:07:23.58 ]
- 1ビットごとに次元を変えていくやり方なら地図サービスとかで使われている
- 462 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 21:08:15.28 ]
- >>461
kwsk
- 463 名前：デフォルトの名無しさん [2012/09/10(月) 21:25:53.08 ]
- >>460
あ、その通りです。安定ソートっぽい意味でした。すみません。
等距離に、または同じ座標に、赤と黒があるときは、
答えは赤でも黒でも良い、検索のたびに答えが変わっても良い、
ってことです。
あと、例えば等距離に黒が複数ある場合、答えは「黒」と返すだけでokです。
アルゴリズムがどの座標の「黒」を指したのか、
それはアルゴリズム利用者に知らせる必要はないです。
>>461
1ビットごとに？？
すみません、ちょっと想像がつきません…。
どんな仕組みなんでしょうか？
- 464 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 22:52:42.26 ]
- >>463
１ビットずつ混ぜるんだよ。分かれよ。
x座標とy座標をそれぞれ32ビット整数値で表現するとして
x = { x31, x30, ... x1, x0 }
y = { y31, y30, ... y1, y0 }
だとするだろ。x31が上位ビットでx0が下位ビットな。
それを混ぜると、
z = { y31, x31, y30, x30, ..., y1, x1, y0, x0 }
という64ビット整数値になるわけだ。
地図系サービスはだいたいこんなのが多い。
- 465 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 22:58:35.49 ]
- >>464
で？ その64ビット整数値をどうする気だよ？
- 466 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 23:01:13.24 ]
- 砂粒座標データはどう整理された状況で提供されるのかが気になる
あるいは事前にデータを整えていいのか否かも
- 467 名前：デフォルトの名無しさん mailto:sage [2012/09/10(月) 23:06:48.73 ]
- >>465
ソートしておけば、upper_bound lower_boundである程度漠然とした領域が拾えるだろ。
全座標の重さが平等でないと使えないやり方だけどな。
そういう想定を置けないなら諦めてR-Tree書けだな。
|
 |
