アルゴリズム総合スレ in ム板
レス数が950を超えています。1000を超えると書き込みができなくなります。
0001デフォルトの名無しさん
2008/08/03(日) 23:23:35アルゴリズムのスレが無かったので立ててみました。
自作アプリ作成に於けるアルゴリズム指南、
基本情報レベルの幼稚園児用鈍足アルゴリズムから
高度な数式が必要な大学院生用神速アルゴリズムまで
語りませう。
0002デフォルトの名無しさん
2008/08/03(日) 23:24:53プログラマ板(マ板)⇒プログラマー板(マー板)
プログラム板(ム板)⇒プログラムー板(ムー板)
になるんじゃね
0003デフォルトの名無しさん
2008/08/03(日) 23:25:25は?2ちゃんは昔から『プログラマー板』なんだが?
0004デフォルトの名無しさん
2008/08/03(日) 23:28:12ツーちゃんねる用テキストエディタを作りたいのですが
レス番号はどうやって把握させればいいのでしょう。
3番の人の書き込みで、『4 名前:デフォルトの名無しさん 投稿日:2008/08/03(日) 23:25:26』という文字列の書き込みをされると
判断が出来なくなるような・・・
0005デフォルトの名無しさん
2008/08/03(日) 23:29:20いっぽすすんでえらいひと
ひっくりかえってぺこりんこ
よこにあるいてきょろきょろ
0006デフォルトの名無しさん
2008/08/03(日) 23:31:38現実的な時間で駒を打ってくれる最強のオセロCPU(AI?)は作れますか?
ここでいう最強とは、全部の組み合わせを探索できる最適なCPUです。
0007デフォルトの名無しさん
2008/08/03(日) 23:32:21おまいら最強のリバーシプログラムしてみろよ part3
http://pc11.2ch.net/test/read.cgi/tech/1173784074/
C言語で素晴らしいオセロを作らないか?
http://pc11.2ch.net/test/read.cgi/tech/1087979678/
【思考】オセロのAIを作りたいのだが【難問】
http://pc11.2ch.net/test/read.cgi/tech/1180430969/
0008デフォルトの名無しさん
2008/08/03(日) 23:33:38http://pc11.2ch.net/test/read.cgi/tech/1215510861/
0009デフォルトの名無しさん
2008/08/03(日) 23:35:11序盤は無理
終盤は可能
0010デフォルトの名無しさん
2008/08/03(日) 23:35:54沢山あるんだが・・・
アルゴリズムオタク
http://pc11.2ch.net/test/read.cgi/tech/1141740363/
計算アルゴリズム【�U】
http://pc11.2ch.net/test/read.cgi/tech/1129376543/
<集大成>アルゴリズム大辞典
http://pc11.2ch.net/test/read.cgi/tech/1086272325/
3Dアルゴリズム全般
http://pc11.2ch.net/test/read.cgi/tech/1164171086/
0011デフォルトの名無しさん
2008/08/03(日) 23:37:27あるよ
少しは探せよゴミ
http://pc11.2ch.net/test/read.cgi/tech/1129376543/
http://pc11.2ch.net/test/read.cgi/tech/1086272325/
http://pc11.2ch.net/test/read.cgi/tech/1141740363/
0012デフォルトの名無しさん
2008/08/03(日) 23:38:27The Art of Computer Programming
Introduction to Algorithm
は必須。
〜のアルゴリズム事典みたいな本は
稚園児向け。
00131
2008/08/03(日) 23:39:29どうもありがとうございました。
00141
2008/08/03(日) 23:39:58http://pc11.2ch.net/test/read.cgi/tech/1212217022/
0015デフォルトの名無しさん
2008/08/03(日) 23:40:170016デフォルトの名無しさん
2008/08/03(日) 23:41:49ぶっちゃけ仕事で使うプログラミングなんて
アルゴリズム知らなくてもいい。
それよりコミュニケーション能力のほうが大事
研究者は例外だからさっさと氏ね。
0017デフォルトの名無しさん
2008/08/03(日) 23:43:550018デフォルトの名無しさん
2008/08/03(日) 23:44:28俺なんかジンバブエ問題を多項式時間で解くアルゴリズムを発見したぞ。
でもそれを記述するにはこの余白はあまりにも少なすぎ
0019デフォルトの名無しさん
2008/08/03(日) 23:46:010020デフォルトの名無しさん
2008/08/03(日) 23:58:07本当はアルゴリズムのほうが大事なのに・・・
0021デフォルトの名無しさん
2008/08/04(月) 00:14:530022デフォルトの名無しさん
2008/08/04(月) 00:19:50アルゴリズムで苦戦して初めて入門者
0023デフォルトの名無しさん
2008/08/04(月) 00:25:54そんなのはどうでもいいんだ。
アルゴリズムの話をするんだ。いいな?
0024デフォルトの名無しさん
2008/08/04(月) 02:45:58マ板にいけよITドカタw
0025デフォルトの名無しさん
2008/08/04(月) 05:01:11入った会社が求人票と全然違う会社でとてもとても。
年休65とかwww
0026デフォルトの名無しさん
2008/08/04(月) 08:59:16> 〜のアルゴリズム事典みたいな本は
Springerから出てるぞおい。Encyclopedia of Algorithms
お高いぜ……。
0027デフォルトの名無しさん
2008/08/04(月) 15:45:040028デフォルトの名無しさん
2008/08/13(水) 13:08:480029デフォルトの名無しさん
2008/09/08(月) 01:34:44任意の敷き詰め方で敷き詰めるアルゴリズムがわっからん
いいかげんにやらせると隅とかで詰んでしまう
0030デフォルトの名無しさん
2008/09/08(月) 01:45:26何となく言ってる事はわかるけど例題出してみてくれる?
0031デフォルトの名無しさん
2008/09/08(月) 01:54:36ソースとかじゃなくて悪いけど
効率を求めないのであれば、
X*Yの範囲におけない場所を任意に作る
おける場所の個数をNとして2の倍数でなければエラー
N/2個のブロックを用意、位置と縦か横かのパラメータを持つ
ブロックを左上から積めていき詰まったらブロックを戻して再検索
0032デフォルトの名無しさん
2008/09/08(月) 02:16:40トライアンドエラーでいけるのかな…
>>30
こんな感じ
┌┬┬┬┬┬┬┬┐ ┏┓
├┼┼┼┼┼┼┼┤ ┃┃
├┼┼┼┼┼┼┼┤ ┗┛
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
└┴┴┴┴┴┴┴┘
0033デフォルトの名無しさん
2008/09/08(月) 03:13:01はずしてたらすまんけどゲームとかでランダムに敷き詰めた
ものが欲しいのなら、こういう形で必ず敷き詰められるから
┌┬┬┬┬┬┬┬┐
│││││││││
├┼┼┼┼┼┼┼┤
│││││││││
├┼┼┼┼┼┼┼┤
│││││││││
├┴┼┴┼┴┼┴┤
└─┴─┴─┴─┘
これから
┌┬┐┌─┐
│││├─┤
└┴┘└─┘
をランダムに90度回転するというのはどうだろう。
0034デフォルトの名無しさん
2008/09/08(月) 03:21:54(特に乱数が擬似で無いならば)
乱数の機嫌がよければどの敷き詰め方も得られる可能性があるアルゴリズムが欲しい
0035デフォルトの名無しさん
2008/09/08(月) 11:15:44(理想的には)ブラックボックステストでは疑似かどうか判定できない
ものが疑似乱数列。
本題
あらゆる敷き詰め方を網羅できるアルゴリズムを考えてみる。
左上から順番に空きを探して、空きがあったらまず横向きに置いて、
その先を置いていく。その先のパターンを全て網羅したら、縦向きに
置く。つまったらバックトラック、というアルゴリズムで、あらゆる
敷き詰め方が網羅できる。
まず横向きに置く→次に縦向きに置く、この順序を乱数で決定
するようにすればランダムになる。
0036デフォルトの名無しさん
2008/09/08(月) 12:24:54C++かなにかで再帰使って実装すれば一日もあればできそうだね。
>>29
勿論、隅で詰まったら手を戻して詰め直してみるだけ。
0037デフォルトの名無しさん
2008/09/20(土) 03:26:23という検索がありますが、
あれは文字列の形式やフォーマットあるいはエンコードなどをすべての
ケースで調べているのでしょうか?
たとえばExcelやワードなどのファイルの場合は、それをテキスト形式
で取り込んで調べるのでしょうか?
よろしくお願いします。
0038デフォルトの名無しさん
2008/09/20(土) 06:02:430039デフォルトの名無しさん
2008/09/20(土) 11:23:21次のようなもので悩んでます。
1.複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか?
場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。
総当たり以外でエレガントな方法というとどんなんざんしょ?
2.同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。
教えてエロイ人・・・
0040デフォルトの名無しさん
2008/09/20(土) 11:25:03すれよごしすまんそ。
0041デフォルトの名無しさん
2008/10/14(火) 22:58:25アルゴリズムは分かっても、それをうまくフローチャート化できなかったりします。
あとソートに関しても前述の理由でうまく説明が出来ない場合があります。
初歩以前の質問かもしれませんが、どなたかご教示願います。
0042デフォルトの名無しさん
2008/10/15(水) 05:17:46ちゃんと説明してくれるのは少ないよね。
英語で良ければHtDPがいいよ。
0043デフォルトの名無しさん
2008/10/15(水) 20:42:21ありがとうございます。
書籍だと1万円するようなのですが、とりあえずwebサイトも見つけたので書籍購入までで時間が取れる時はそちらを参照してみます。
どなたでも、日本語の書籍でも何か参考になるものがありましたら、お願い致します。
0044デフォルトの名無しさん
2008/10/22(水) 00:40:29ただしファイル名が長すぎて使えないことは考慮しないとします。
UnixならBase64、WindowsならBase32を使っておけばとりあえずOKですが。。。
UnixはスラッシュとNUL以外は何でも使えるようなので、Base64は非常にもったいない気がします。
なにかいいアイディアはありますか?
0045デフォルトの名無しさん
2008/10/22(水) 06:44:17> UnixはスラッシュとNUL以外は何でも使えるようなので、Base64は非常にもったいない気がします。
だからといってマルチバイト文字列でもなしに
printableでないバイトを使うのは非常に愚かだと思うがどうかね。
0046デフォルトの名無しさん
2008/10/22(水) 11:18:130047デフォルトの名無しさん
2008/10/24(金) 21:57:47詳しい書籍、HPなどがあれば教えてくださると助かります。
0048デフォルトの名無しさん
2008/10/24(金) 22:02:44使っていい文字n個を全部使ってBase<n>エンコードすればいいやん。
0049デフォルトの名無しさん
2008/11/18(火) 12:10:38こっちむいてふたりで前ならえ
あっちむいてふたりで前ならえ
こっちむいてふたりで前ならえ
手を横に あら危ない
頭をさげればぶつかりません
手を横に あら危ない
頭をさげれば大丈夫
0050デフォルトの名無しさん
2008/11/18(火) 12:48:410051デフォルトの名無しさん
2008/11/18(火) 12:51:140052デフォルトの名無しさん
2008/11/18(火) 14:08:122つの同数の葉を持つ木構造のデータの類似性を比較するアルゴリズムってなにかないでしょうか?
データの文字列に対して編集距離を使って計算を行ったのですがそれではあまり差異が出ないので他の方法を探してます
0053デフォルトの名無しさん
2008/11/22(土) 16:46:56のコナミは。何がって、1面の竜!1本の竜に見えるけど、よーく見ると複数のパーツが
組み合わさってできている。多関節キャラの範疇に入るのかな?
他のギミックを見ると、どうやら回転機能は使ってないようだ。(カニの脚の上(膝より上って
意味ね)は一見すると回転機能を使っているように見えるが、よく見ると使ってない)
ということは、少しずつ回転させた絵をいっぱい用意してあるんだろうな。普通に蛇型?
竜型?のキャラを作ったらR-TYPEの蛇みたいに各パーツが別れて見える。それをきれ
いにつながっているようにデザインしているのがすごい!
0054デフォルトの名無しさん
2008/12/10(水) 21:45:28参考になる情報をお持ちでしたらご教授のほどよろしくお願いいたします。
凹凸組み合わせた図形を考えると難しそうです。
入力:多角形の頂点座標リスト
出力:四角形(rectangle)のリスト
0055デフォルトの名無しさん
2008/12/10(水) 21:50:010056デフォルトの名無しさん
2008/12/10(水) 21:59:561.三角形に分割する
2.三角形をノード(節点・頂点)、辺をエッジ(枝・辺)とするグラフ理論に置き換える
2B.ただし辺を共有していても合体して三角形になる場合は
合体三角形でまた別のグラフを作る
(そもそも2Bの条件に引っかかる場合はそもそも合体三角形をなぜ分割したのだろう?
ということはこの処理は要らない?)
3.グラフを共通のエッジを持つ2つのノードの組に分解する
どうやるんだろう…市松模様のように塗れるのだろうか?
0057デフォルトの名無しさん
2008/12/10(水) 22:26:00(ディグダグ2みたいな感じ)
三角形の分割から入るということですか
0058デフォルトの名無しさん
2008/12/10(水) 22:32:10要は、水平線と垂直線だけ? 単に長方形に分割すればいいって話?
# だったら最初からそう書けよ。
0059デフォルトの名無しさん
2008/12/10(水) 22:34:05四角形じゃなくてrectangleか
道理で
0060デフォルトの名無しさん
2008/12/10(水) 22:34:42言葉足らずですみません。
0061デフォルトの名無しさん
2008/12/10(水) 22:44:41水平垂直矩形の組み合わせ(ドット絵の影絵?)なのか
そこまで気になってきた
0062デフォルトの名無しさん
2008/12/10(水) 22:48:500063デフォルトの名無しさん
2008/12/10(水) 22:54:470064デフォルトの名無しさん
2008/12/10(水) 23:13:580065デフォルトの名無しさん
2008/12/11(木) 07:28:490066デフォルトの名無しさん
2009/01/19(月) 03:39:520067デフォルトの名無しさん
2009/01/19(月) 03:40:230068デフォルトの名無しさん
2009/01/19(月) 09:17:06総務省のu-Japan政策が余りにも現実離れしてる件
0069デフォルトの名無しさん
2009/01/20(火) 03:09:35> O[c^n]とかでも今のハード(例えば携帯とか)では n<2^64 までとか縛ればいいだけです。
とか書いてあったが、c=2としてn=2^32でもO[2^2^32]=O[10^1000000000]程度になって1秒に10万命令できて
1年を100万秒と換算したところで10^999999989年かかるわけで計算間違いがあったとしても現実的な時間で終わらないということがわかってないところがアルゴ君のアルゴ君たるゆえんだと思った。
縛ればいいだけですって、それで縛っても現実的な時間で終わんないつうの。
適当な概算なんで、計算量が2^2^32で1秒に10万計算できたとき、何年で計算が終わるかだれかちゃんと計算してくれ
0070デフォルトの名無しさん
2009/01/20(火) 03:25:140071デフォルトの名無しさん
2009/01/20(火) 03:26:31だから指数時間かかるアルゴリズムは実装がどうこうよりもアルゴリズムとしてO(1.7^n)とかO(1.4^n)に緩和することが大事だということがわからないんだろう。
0072デフォルトの名無しさん
2009/01/20(火) 03:27:43そうなんだが、アルゴ君はその具体的な数値を出してたから、アルゴ君なんだ。
0073デフォルトの名無しさん
2009/01/20(火) 03:28:37http://pc11.2ch.net/test/read.cgi/tech/1129376543/
0074デフォルトの名無しさん
2009/01/20(火) 03:32:07http://pc11.2ch.net/test/read.cgi/tech/1220531647/240
0075デフォルトの名無しさん
2009/01/20(火) 03:32:21美味い棒か?
0076デフォルトの名無しさん
2009/01/20(火) 03:35:08なーんにも経験したことないおまえの方が無能ってことだな。
0077デフォルトの名無しさん
2009/01/20(火) 03:37:00簡単に説明すると、次世代Javaスレでアルゴリズムをアルゴという人があらわれ、アルゴリズムIIスレでアルゴという言葉を使う人が現れたと思ったら次世代Javaスレのときと同じように逆切れしてたのが、アルゴ君なんだ
0078デフォルトの名無しさん
2009/01/20(火) 03:45:41このスレには既にアルゴ君が居る事に
0079デフォルトの名無しさん
2009/01/20(火) 03:58:00なんだかよく分からないが粘着してるのはおまえの方でないのか
キモイからそろそろ消えてくれないか?
0080デフォルトの名無しさん
2009/01/20(火) 04:02:18気づかないフリしてあげて!
0081デフォルトの名無しさん
2009/01/20(火) 22:32:05ワロタw
0082デフォルトの名無しさん
2009/01/24(土) 22:18:120083デフォルトの名無しさん
2009/01/24(土) 22:47:57連続量のエントロピー
0084デフォルトの名無しさん
2009/01/31(土) 15:44:27高校の体育で
アルゴリズム体操やらされてる
私が通りますよ
0085デフォルトの名無しさん
2009/02/18(水) 00:56:26プログラム起動時にキーと値を読み込んだり終了時に書き出したりしないといけない上、
データが増えてきてメモリに収まらない程になってきたので、
ハードディスク上にデータを置いたままキーの検索などが行えるように改造しようとしています。
ググったらB+treeやB*treeや赤黒木なんかが見つかりましたが
お勧めのアルゴリズムとその理由を教えてください。
ちなみにキーは8バイトのハッシュ値で、値は16バイトの構造体です。
0086デフォルトの名無しさん
2009/02/18(水) 01:24:552.ハッシュ値の上位8ビット〜16ビットごと+キャッシュ、つまり257〜65万くらいに
データを分割する。十分な性能を持つハッシュならキーは十分平均的に分散するはず
なんて方法がさくっと浮かんだが、間違ってるかもしれない
0087デフォルトの名無しさん
2009/02/18(水) 15:17:490088デフォルトの名無しさん
2009/02/18(水) 22:01:59HDD上でのシーク回数が木構造よりも減るんじゃないかと。
0089デフォルトの名無しさん
2009/02/19(木) 11:23:580090デフォルトの名無しさん
2009/02/19(木) 11:37:480091デフォルトの名無しさん
2009/02/20(金) 12:21:27求めるアルゴリズム(数学どおりの余因子による方法)ではどちらが実用的なんでしょうか。
行列式の方法が効率的だと、逆行列は余因子展開で求められてしまうんですが・・・
0092デフォルトの名無しさん
2009/02/20(金) 14:37:150093デフォルトの名無しさん
2009/02/20(金) 15:16:530094デフォルトの名無しさん
2009/02/20(金) 22:13:12余因子展開のときの行列式はどうやって計算するの?
>>93
逆行列の計算と行列積の計算は同じオーダーでできるので
現在最速の行列積がO(2^376)なので,これが現在最速.
ただし定数部分がでかすぎて実用的には使い物にならない.
0095デフォルトの名無しさん
2009/02/20(金) 23:16:21余因子を使ったdet値の導出は、公式自体は線型代数の教科書に普通に載ってるんですが。
たぶん、主要部分はいれご(再帰)になるだけでプログラムはかなり簡単になるんじゃないかな。
ピボットとかの職人技法的なことを考えることなく、機械的なプログラムのほうがいいかなっと思ってまして。
n^5は一見遅いけど頑張ってもn^3, n^2なので激遅いってことじゃないみたいですね。
それに通常の使い方では、逆行列は一度計算して変数に入れておくことが多く、det値を再計算しないで再利用して使いまわすので、
やはりプログラムが簡単なアルゴ(笑)のほうが言いかなって思うんですけど。
0096デフォルトの名無しさん
2009/02/21(土) 01:54:53一番良い実装ってどれですか?
0097デフォルトの名無しさん
2009/02/21(土) 01:58:5564bit が atomic にロード/ストア出来る CPU か否かによって変わってこないか?
0098デフォルトの名無しさん
2009/02/21(土) 02:04:200099デフォルトの名無しさん
2009/02/21(土) 11:49:30何を聞かれているか理解できてないみたいね.
(1) 逆行列を余因子行列を用いて表す方法がある.これには O(n^2) の行列式の計算が必要.
(2) 行列式の計算に余因子展開を用いるものがある.これには O(n!) の四則演算が必要.
(3) 行列式の計算は巧くやれば O(n^3) 以下でできる.逆行列を余因子行列で計算する方法が O(n^5) というのはこれを用いた場合.
ちなみに O(n^5) は十分遅いレベルで,実用的には使い物にならない.
逆行列の使いまわしも,数値線型計算では逆行列の形では陽に持たないのが常識で,LU分解の形で持つ.
0100デフォルトの名無しさん
2009/02/21(土) 13:54:37もしあるなら、余因子展開で逆行列も高速に出ますよねってことです。
今やってるのは、行列式の値は逆行列(消去法などで)出すときに付随して出てきます。
detだけを出すのは、数学定義通り余因子による方法しか知らないので他にないんでしょうか。
といっても実際は線型打数のパッケージ使うので、アルゴリズムの練習程度なのでこだわってるわけじゃないんですが。
0101デフォルトの名無しさん
2009/02/21(土) 14:08:52次は従来の算法など数値計算用(ソルバー)と、文字列・グラフ理論なども含む探索用(ファインダー)とかで2冊ぐらいに分けて出してくれませんか?
そろそろぼろぼろになってきたし、先生の本は解説は個人的な偏りがなくソースは素直で読みやすいから次も買うんで。
0102デフォルトの名無しさん
2009/02/21(土) 15:28:270103デフォルトの名無しさん
2009/02/21(土) 15:49:47行列式を計算するアルゴリズムは存在する.
効率的なものと非効率的なものがあり,余因子展開によるものは非効率.
効率的なものでも,行列の積や逆行列よりも小さなオーダで行うことはできない.
逆行列と同じオーダでやるのは簡単で,行基本変形で上三角形にして(ガウス消去),
対角成分の積を取ればよい.これも行列式の定義の1つとしてよく知られている.
0104デフォルトの名無しさん
2009/02/21(土) 16:00:07アルゴリズムでは直接求めたりはしないけどね。
>>103
やっぱり消去法とか三角行列になるんですか。参考になりました。
0105デフォルトの名無しさん
2009/02/21(土) 16:00:17そこまで大規模な改訂は多分行われないので諦めよう.
現代的な項目を追加しようとか,ソースが汚いので直そうとか,
何度か意見は出てるけど,結構な大仕事で,人材不足だとさ.
0106デフォルトの名無しさん
2009/02/21(土) 16:21:31もし掛け算のパートと足し算のパートを並列化できれば別の手法が考えられるし、作業配列を当然に仮定するので演算は前後演算に影響はなく、並列化どころかストリーム処理でもできそうな感じですかね。
そうすると、FFT乗算やカラツバ法とかと同等になるんじゃないでしょうか。といっても、パッと浮かんだ程度で専門でもないんで・・・
0107デフォルトの名無しさん
2009/02/21(土) 16:28:360108デフォルトの名無しさん
2009/02/21(土) 16:44:54FFTとかと同等ってどういう意味か分からないけれど,所謂Strassen系のアルゴリズムは
先に「後に使いまわせる和の項を作っておく」方法なので,その着眼点は良いよ.
ちなみに,昔から行列乗算の最適計算量は Θ(n^2) だろうと信じられていたんだけど,
2005年くらいの結果で,組合せ論と群論における2つの未解決予想を認めると,
実際に O(n^2) が達成できることが示されている.
0109デフォルトの名無しさん
2009/02/21(土) 17:24:56例えば多倍長で1−100桁目の加算と、これと同時に別スレッドで101−200桁目を計算できます。
したがって、掛け算パート用の配列、足し算パートの用の配列をいくつも用意して、スレッドで並列計算すればいいだけです。
配列やスレッド生成のコストとか、配列ではスレッドローカル変数、スレッドは予め行列演算用のスレッドをクラス定義しておけばいいので主要コストとは考えられません。
100x100以上だとしても、結局はやってること(演算)は画像のブレンドと同等になっていくので考え方次第ではストリーム処理が可能となり、よって「同等」です。100x100の行列は普通使わないんですけど。
シングルスレッドにこだわるなら、確かにO[n^5]は遅いんですが、実際使うのは10x10とかテイラー級数で15桁程度の多項式係数を求める程度(20x20程度)なんで、
マテマテカ使って式展開させて行列式と逆行列をハードコーディングでもいいかなって思います。
他にはO[n^5]でも10x10程度だと、今のPCリソースからすれば遅いって実感は全くないのでプログラミングが楽な再帰による方法(つまり余因子行列)でもたいして問題は生じないってところです。
プロジェクションなどの用途なら4x4程度だし、そもそもDirectXとかになるからソフトウェア上のアルゴリズムとは関係ありません。
ただ、逆行列と行列積は球根と数値計算の要なんで速いに越した事はないですけど。
0110デフォルトの名無しさん
2009/02/21(土) 18:52:06で,君は何を主張したいの?
間違いだけ指摘しておくと,余因子展開で行列式を計算すると O(n!) 掛かる.
これは既に >>99, >>103 でも指摘済み.
0111デフォルトの名無しさん
2009/02/21(土) 18:53:140112デフォルトの名無しさん
2009/02/22(日) 01:44:2110x10程度まで良く使うなら式展開すればよいって書いてあるので、例えば2x2で行列式を展開した方法 a d - b c もO[n!]なんですけど、これ以外に他に方法はあるんですか?
0113デフォルトの名無しさん
2009/02/22(日) 06:18:05どう式展開するつもりか知らないけど,行列 A の成分をすべて不定元だと思って
行列式を書き下したものをハードコーディングするつもりなら,止めたほうがいいよ.
項の数が O(n!) になるので,結局四則演算の回数は減ってないから.
0114デフォルトの名無しさん
2009/02/22(日) 08:25:06やめたほうがいいじゃないくて、他に方法はないのかと聞いてるようですが?
そのようなアルゴリズムは知りませんと答えるのが正しいんじゃないですかね。
いつまでも計算量にこだわってるようじゃあなたの人生、先に進みませんよ。
0115デフォルトの名無しさん
2009/02/22(日) 10:18:09> PCリソースからすれば遅いって実感は全くない
みたいな色々な主観を全部記述するほうがアホみたいだと思われ
そんでもって,そんなの書いて人に聞くより試しにやってみればいいんじゃないの?
俺にはサッパリわからんが
0116デフォルトの名無しさん
2009/02/22(日) 10:21:54君は >>103-104 の流れで別のアルゴリズムがあることを理解したんじゃなかったかい?
0117デフォルトの名無しさん
2009/02/22(日) 10:25:54> いつまでも計算量にこだわってるようじゃあなたの人生、先に進みませんよ。
みたいなことが言えるんだろうな
0118デフォルトの名無しさん
2009/02/22(日) 10:51:12せいぜいn=4か5までだろ、計算量的に考えて…
0119デフォルトの名無しさん
2009/02/22(日) 11:28:44普通は行列式の計算はQR分解じゃなくてLU分解を使うことが多い気がする.
実際,LUのほうが精度的に良いケースが多いはずで,LAPACKはこちらを推奨している.
0120デフォルトの名無しさん
2009/02/22(日) 13:10:12行列は結局n=4,5ぐらいが一番使うんだけど。
どうせ誰かが実装したアルゴリズムを使うだけで自分で実装なんかしないんだし、ハードコーディング(笑)でなにか問題でもあるのか?
0121デフォルトの名無しさん
2009/02/22(日) 13:32:29なんとか自慢のアルゴリズムで特許とったところで、組み込みとかでブラックボックスにされちゃ確認のし様がないし。
>>117
言いたいことは分かるが、10マイクロ秒単位を気にして生きてかなければならない人生なんて哀れだな。その研究は幾らになるんだ?
0122デフォルトの名無しさん
2009/02/22(日) 13:39:16( ゚д゚) ・・・ (つд⊂)ゴシゴシ (;゚д゚) ・・・ (つд⊂)ゴシゴシゴシ
_, ._
(;゚ Д゚) …!?
0123デフォルトの名無しさん
2009/02/22(日) 13:50:20誰かが実装した"ライブラリ"のtypo?
あと、ハードコーディングの意味は分かってる?
QRでもLUでもべた書きしたらいいじゃない
>>121
行列演算で10マイクロ秒って驚異だろ
何回呼ばれると思ってんだ
0124デフォルトの名無しさん
2009/02/22(日) 13:51:010125デフォルトの名無しさん
2009/02/22(日) 14:12:29> 行列は結局n=4,5ぐらいが一番使うんだけど。
ご冗談をw
0126デフォルトの名無しさん
2009/02/22(日) 14:14:35オーダーの違いがマイクロ秒単位でしか現れないという認識が残念すぎる
オーダー1つ落としたおかげで実社会で使われるようになったアルゴリズムがどれだけあると思ってるんだ
0127デフォルトの名無しさん
2009/02/22(日) 14:17:070128デフォルトの名無しさん
2009/02/22(日) 14:19:38行列の話などしてないし、誰かと勘違いしてないか?
ところで、最近 sin/cosを効率的に求める CORDIC というとんでもないアルゴリズムを知ったのですが、
いまではこれら超越関数は普通にテイラー展開することが多くてすでに見捨てられるようです。
http://en.wikipedia.org/wiki/CORDIC
このような有用なアルゴリズムがあっても結局見捨てられてしまうわけで、どうして計算量にこだわるんですか?
上にもありましたが並列化など全く別のアプローチを取れば、一気に計算量が減らせることもあるわけで、
計算量を評価の指標とする考え方は全くずれてるに思うんですが。
0129デフォルトの名無しさん
2009/02/22(日) 14:26:40それは既にアルゴリズムというよりも粒度が大きいプログラム、というか逆行列を解くための専用のアプリケーションじゃないでしょうか。
つまりifなどの分岐だらけになるようなアルゴリズムは、既に汎用のアルゴリズムではなくてその問題に特化したただの「プログラム」じゃないでしょうか。
アルゴリズムの複雑な組み合わせとなっているような大きいアルゴリズム(プログラム)などに計算量による評価とか全く意味ないと思うのですが。
実装がしやすい理解がしやすいかどうかで評価するべきじゃないでしょうか。
0130デフォルトの名無しさん
2009/02/22(日) 14:36:55当時、スパコンと呼ばれていた計算機は、現在のパソコン並か、それ以下です。
無駄な計算量の向上に時間を費やすよりも、使いやすくて読みやすいプログラムを書くことに時間をつかうべきですよね。
優れたアルゴリズムを考えても、すぐに廃れてしまうのです。
優れたプログラムを書けば10年後も使えるんです。
0131デフォルトの名無しさん
2009/02/22(日) 14:39:03行列はn=2,3,4,5ぐらいが一番多いけど、他に何に使ってるの?
まさか測定点を全て通る多項式とか出してないよね。
0132デフォルトの名無しさん
2009/02/22(日) 14:40:18>>128
> いまではこれら超越関数は普通にテイラー展開することが多くてすでに見捨てられるようです。
現在でもCORDICが使われている場面はある.あなたが知らないだけ.
> このような有用なアルゴリズムがあっても結局見捨てられてしまうわけで、どうして計算量にこだわるんですか?
本当に,テイラー展開など比べて有用なのか評価したのかい?
特に,計算量はどういう測り方をして,どちらがどうなるのか分かってる?
> 並列化など全く別のアプローチを取れば、一気に計算量が減らせることもあるわけで、
並列計算機上の計算量にはそれなりの測り方があり,台数効果は計算量減少にカウントしない.
>>129
> 例えば行列なら、Strassen法のように速度(計算量)を稼ぐために全く意味不明な実装になっているなら、
Strassen程度で意味不明というのは力不足.
既にメジャーな数値計算ライブラリにおいてStrassen法は実装されており,
それまで時間が掛かりすぎていた問題が,解けるようになったという報告がある.
> それは既にアルゴリズムというよりも粒度が大きいプログラム、というか逆行列を解くための専用のアプリケーションじゃないでしょうか。
あなたの「アルゴリズム」と「プログラム」と「アプリケーション」の定義は何?
> アルゴリズムの複雑な組み合わせとなっているような大きいアルゴリズム(プログラム)などに計算量による評価とか全く意味ないと思うのですが。
なぜそう思うの?
> 実装がしやすい理解がしやすいかどうかで評価するべきじゃないでしょうか。
そういう評価があってもよいと思うけれど,これは定量的に量れるもの?
0133デフォルトの名無しさん
2009/02/22(日) 14:40:56計算時間(計算量ではなく)を見積もって
余因子並列をぶちのめせたら解決、のような気がしないでもない
と下書きしていたら>>130に噴いた、どういう宗教だろう
その考え方はアルゴリズムスレじゃなくてプログラムスレで論ずるべきだな
0134デフォルトの名無しさん
2009/02/22(日) 14:41:080135デフォルトの名無しさん
2009/02/22(日) 14:44:40> 当時、スパコンと呼ばれていた計算機は、現在のパソコン並か、それ以下です。
> 無駄な計算量の向上に時間を費やすよりも、使いやすくて読みやすいプログラムを書くことに時間をつかうべきですよね。
例えば巡回セールスマン問題で,アルゴリズムを変えずに100倍のサイズの問題を
同じ時間で解こうと思ったら,計算機性能は何倍になればいいか知ってる?
0136デフォルトの名無しさん
2009/02/22(日) 14:48:02電波・お花畑板が相当だと思う
0137デフォルトの名無しさん
2009/02/22(日) 14:50:55別にその報告や論文書くわけじゃないし。
おまえはそんなに凄い「世の中を変えちゃうような壮大な」研究でもしてるか?(脳内でw)
組み込みとか4ビット8ビットの貧弱CPU向けのアルゴリズム(というかすでに特化プルグラムだけど)の議論なら分かるけど、
PCやスパコンwとかだと、結局カッコいいこといってるけど実際は実装が面倒だからハードでごり押しじゃないの?
大金もらってるから面倒とか言うことは無いだろうけど、もしくは断念して誰かが作ったライブラリを使うとか。
つまり時代が流れて、ハードが進化したから、実社会で採用されたと考えられなくもない。
例えばインタプリタや中間コードは当時70年代は研究目的で全く見向きもされなかったけど、今は見直されたというよりもハードが進化したから普通に当たり前になってるとかのこと。
0138デフォルトの名無しさん
2009/02/22(日) 14:52:51書き込みの同一人物判定が苦手な俺。
ちなみに俺は >>92 >>107 >>122 >>133 で、身分は素人ね。
間違ったことかなり言ってしまってると思うけどごめん。
でも興味が出たんで、LU・QRの具体的な方法について勉強して
十分に並列化した場合の計算時間コストがどんなものか見積もってみたくなった。
これと余因子並列時間コストとの比較が焦点っぽいけど、それでいいのかな。
>>136なるほど
0139デフォルトの名無しさん
2009/02/22(日) 14:53:39arctanがいくら高速でも全体が速くならなければ意味なし。 実装してバグでるほうが問題。
使いたいやつが使えば良いんだ
0140デフォルトの名無しさん
2009/02/22(日) 15:01:41近年=十数年
0141デフォルトの名無しさん
2009/02/22(日) 15:04:42あまりに酷いのはあんたの方だな。勉強不足とは失礼な奴だし、そもそも世の中のことを知らずに自分の研究だけに情熱を注ぐだけだろう。
あんたがどれほど勉強不足か、少し突っ込んで議論してみようか。
当然アルゴリズムなど君の専門分野を知ってるわけではないが、君は2chの分際で少々生意気だな。
自分の傲慢を原因として、人様を怒らせるもんじゃないし、そのうちIP抜いて不幸の手紙でも送ってやろうか?w
CORDICが使われてるのはあるだろうが、それではなぜCORICは廃れたんですか?
当時のハードで実用的なわけで、非常に有用なアルゴリズムのはずですよね?
テイラー展開と比べて有用かどうかを評価しましたが何か?
計算量云々について君に報告する必要はありませんが、いくらなら報告書買いますか?
・・と、お前の暇つぶしに付き合ってるほどヒマじゃないんだよね・・どうせお前なんか誰も相手してくれない禿げオッサンだろうしww
0142デフォルトの名無しさん
2009/02/22(日) 15:07:41なんか一気に吹き出したって感じだな。このオッサンはww
なぜ?どうして?定義は何?とかどこの哲学版だよ
お花畑版ってのが2chにあるから、君は早いところそっちに引っ越した方がいいよw
0143デフォルトの名無しさん
2009/02/22(日) 15:11:58>そのうちIP抜いて不幸の手紙でも送ってやろうか?w
受けるw
もっとやれ
014492他 ◆DRdCZDy4PY
2009/02/22(日) 15:14:51うわあ、礼儀飛び越えて中傷脅迫してるなり…
>>142
定義が大事な話してるのに、それを蔑ろにしては何も語れないかと
というわけでお花畑はあなたが行くべきっぽいんだが
0145デフォルトの名無しさん
2009/02/22(日) 15:21:21奥村センセの本でも「複雑すぎるし、たいして性能向上ないから省略」とか書いてあるし。
>>132
君はアルゴリズムの深みにはまりすぎてんじゃないの?w
一番理解できないのは、
>それまで時間が掛かりすぎていた問題が,解けるようになったという報告がある.
それもO[n^3]やO[n^2]で影響が出るほどの行列(想定できないが10000x10000とか)のことでしょ。
実社会やビジネスではそんなの大きい行列は使いません。
ベンチャー企業や研究機関でもこの行列を必要とするところは考えにくく皆無なため、結局その報告は「これは実用的です」って言う宣伝(サクラ)じゃないの?
誰かが論文にあるサンプルコードどおりに実装してライブラリにすれば終わりだから別にStrassen法程度を否定するつもりはないけど、壮大な話を聞いて君は騙されちゃったんだねw
0146デフォルトの名無しさん
2009/02/22(日) 15:37:49というか、このスレは同じ人がレスしてるっていう前提を持ってる時点であなたの妄想じゃないの?
たとえば「計算機性能は何倍になればいいか知ってる?」について知ってる・知らないと答えたところで、議論についてあなたに何か変化があるんですか?それはあなたの傲慢から生じるあなたの偏見じゃないですか?
よく読んでみると、「ハードが進化すると当時遅いっていわれてたアルゴリズムも遅くないよね」って書いてあるようですけど。
行列で計算量云々についての議論をしたとしてもn=1000なら、
8バイト*1000^2で8メガぐらいあるんですが、いくらO[n log[n]]となったとしても常時8メガの演算(それもメモリ間コピー含む)が実用的だと思いますか?
結局現在でもn=100ぐらいが実用の限界でありアルゴリズムの制約条件じゃないですかね。
つまりアルゴリズムの計算量の議論は既にお花畑なんでしょう。もっと実社会に即した評価の目をもってみてはいかがですか。
0147デフォルトの名無しさん
2009/02/22(日) 15:40:21あのー
>>131に答えてもらえないんですか?
どうせ線型代数の教科書も読んだことないんでしょうけどw
0148デフォルトの名無しさん
2009/02/22(日) 15:40:290149デフォルトの名無しさん
2009/02/22(日) 15:42:090150デフォルトの名無しさん
2009/02/22(日) 15:44:12まじめに相手にする人がいると激しくなっていくものだ
霊が見えるって人もこのたぐい
0151デフォルトの名無しさん
2009/02/22(日) 15:44:450152デフォルトの名無しさん
2009/02/22(日) 15:48:540153デフォルトの名無しさん
2009/02/22(日) 15:53:19普通は速い・遅いは時間ですが、オーダは計算量で、式のステップ数というか計算回数とでもいいましょうかもしくはリストの個数とでもいましょうか
どちらにしても計算量というのは時間ではないようなので、全く速い遅いの指標になってないんじゃないでしょうか。
そうすると、計算量が多いアルゴリズムO(n^3)でもスレの流れにあるような議論のように、速いとか実用とかは実際はアルゴリズム自体ではなくてハードによるってことだけなんですけど・・・
それでも観念しないのはアルゴリズム職人としてのポリシーか何かあるんですか?アルゴリズム研究とは一種の宗教なんですか?
015492他 ◆DRdCZDy4PY
2009/02/22(日) 16:02:05並列的な余因子展開で逆行列を求める速度と
並列的なQR分解または並列的なLU分解で逆行列を求める速度を
それぞれ算出するんだ
一般的なCPUでの実測とベクトルプロセッサでの実測と四則演算等の段数両方考察するといいぞ
ちなみに俺に任せるとQR分解の勉強からはじめなければならないから
演算の段数数えるだけでたぶん一ヶ月はかかる、ひゃほーい
0155デフォルトの名無しさん
2009/02/22(日) 16:02:150156デフォルトの名無しさん
2009/02/22(日) 16:24:21構造計算や大規模偏微分方程式に使うFEMのソルバについて軽く調べてみるといいよ
nが数万とかの(疎)行列の固有値救解や連立方程式計算をすることになるから
んで、その為のスカイライン法とか、マルチフロンタル法とか、
効率のいいアルゴリズムを見つけた上で更に並列計算に持っていこうとするんだよ
やってることは結局のところ全てLU分解(正確にはコレスキー分解)なんだけどね
そういう行列計算の世界もあるんですが、知らなかっただけですよね
0157デフォルトの名無しさん
2009/02/22(日) 16:37:53お望み通り、「nが数万の行列」になるね
FEMやらBEMやらがビジネス(笑)で実用化されてないとはまさか言われないだろうしね
0158デフォルトの名無しさん
2009/02/22(日) 16:39:16まあまあおまえら、コレでも読んでマターリしようぜ
0159デフォルトの名無しさん
2009/02/22(日) 16:46:140160デフォルトの名無しさん
2009/02/22(日) 17:21:13Googleのページランクの計算は結局のところ行列の計算なんだけど,
どれくらいのサイズの行列を使ってるか知ってるかい?
数値計算の分野では 10000×10000なんて「十分小さい」行列だよ.
0161デフォルトの名無しさん
2009/02/22(日) 17:22:25行列をプロセッサ数に効率よく分割できなくね?
0162デフォルトの名無しさん
2009/02/22(日) 17:28:34シッ!そういう言い方すると
>議論についてあなたに何か変化があるんですか?それはあなたの傲慢から生じるあなたの偏見じゃないですか?
とか言われちゃうよ。どうせ知らないのにね。
で、どんぐらいなの?
0163デフォルトの名無しさん
2009/02/22(日) 18:00:24凄い勢いでデータが増えているので今現在ではもっと増えてるかもしれないけど,
2008年の末で大体数百億くらい.ちなみに2002年くらいで数十億だった.
ただし,もちろん疎行列で,非ゼロ成分もこのオーダーくらいしか存在しない.
0164デフォルトの名無しさん
2009/02/22(日) 19:05:11> よく読んでみると、「ハードが進化すると当時遅いっていわれてたアルゴリズムも遅くないよね」って書いてあるようですけど。
逆だ逆w 具体的に何倍になるか答えてみろよw
0165デフォルトの名無しさん
2009/02/23(月) 01:31:582MHzの頃のアルゴリズムを後生大事にしてる愚か者っているよなw。
016692他 ◆DRdCZDy4PY
2009/02/23(月) 01:42:44今でも極限までアルゴリズムや実装をチューンナップするものだ
もっともプロセッサの配線やライブラリと化したものが多いだろうけど
0167デフォルトの名無しさん
2009/02/23(月) 02:28:08> 8ビット時代のメモリが4kBくらいでCPU駆動周波数が
> 2MHzの頃のアルゴリズムを後生大事にしてる愚か者っているよなw。
誤字?
×アルゴリズム
○プログラム
0168デフォルトの名無しさん
2009/02/23(月) 02:29:15おまえはアルゴリズムの評価に コンニチハ セカイ みたいな文字列の出力まで考慮するタイプの人間なのか
016992他 ◆DRdCZDy4PY
2009/02/23(月) 02:43:52#まじめに読まないこと推奨のような気がしてきた
(r s t)
(u v w) = A なる3次正則行列 A についてクラーメルの公式
(x y z)
(vz-wy xw-uz uy-vx)
(ty-sz rz-tx xs-ry)÷{r(vz-wy)-u(ty-sz)+x(sw-vt)}
(sw-vt tu-rw rv-su)
vzで1段、vz-wyで2段、r(vz-wy)で3段、
r(vz-wy)-u(ty-sz)+x(sw-vt)は3項だから一気に足せず5段
それと2段で計算終わってる(vz-wy)〜(rv-su)を掛けて6段
必要な計算の段数は6段
2次正方行列の固有値を求めるのに2段
3次正方行列の固有値を求めるのに+3段で5段
4次正方行列の固有値を求めるのに+3段で8段
5次正方行列の固有値を求めるのに+4段で12段
6次正方行列の固有値を求めるのに+4段で16段
n次正方行列の固有値を求めるのに+(1+天井[log(底2){n}])段で総計は…めんどくさい
行列式の算出が一番段数食うので
余因子を固有値で割る最後の1段があれば逆行列は求まる
とりあえずべらぼうに回路の面積食いそうな点とか
検証が怖いので考えない方向。
何で俺、こんな時間にこんなこと考えてるんだろ。
そして絶対どっか豪快に間違えてるぜ、眠いし。
017092他 ◆DRdCZDy4PY
2009/02/23(月) 03:40:143次正則行列をAとおく。このとき
(1 0 0) (u v w)
(r 1 0) (0 x y) = A
(s t 1) (0 0 z)
となるように r〜zを求める。
左側を具体的に乗算するとわかるとおり、u v w は0段で求まる。
(u v w)
(a b c) = A
(d e f)
いやだってiとか1と紛らわしいから避けたいん。
愚痴はひとまず置いといて。
r = a / u で1段、sも同様。x = b - rv は3段、yも同様。
t = (e - sv) / x で4段。
z = f - sw - tyで6段。
三角行列の逆行列を求めると段数だけ表示すると
(1 5 10)
(0 4 8) = U^-1
(0 0 7)
(0 0 0)
(2 0 0) L^-1
(6 5 0)
A^-1 = (U^-1)(L^-1) なので 12段で出揃う。
高次…き、気力が…。ただUの右上隅が一番、そして派手に段数食いそう。
0171デフォルトの名無しさん
2009/02/23(月) 05:22:34それって、よくわからんけどグラフ理論にある隣接行列のことじゃないか?
要素が1か0とかほとんど固定パターンのやつ。それを愚直に演算してるとでも思ってんのかよ。
「行列サイズは数億になるんだ!」とか偉そうにするな。お前は一生知ったかのカス野郎のくせにww
0172デフォルトの名無しさん
2009/02/23(月) 05:27:06要素が0と1じゃ情報少なすぎだろjk
おまえの頭はどこまで真っ直ぐなんだよ・・・
0173デフォルトの名無しさん
2009/02/23(月) 05:41:57そういのは研究所や専門の工務店がやるもんで、あまりビジネス(商売)って感じではないですね。
今ではベンチャーが調査の受注を受けてレポートして報酬を受けるわけで、その何とか法のアルゴリズムは、
汎用(一般用)というよりもその分野に特化したアルゴリズムなんじゃないですか?
この算法は、「キーボードのキーピッチは13-17が最適解でありこのれを求めるアルゴリズムである」といわれても、
「そんなの知らんわ!」じゃないですかね。
つまりそういう特化した分野のアルゴリズムを出してきたり、その分野の計算量がどうとか全く意味がない議論です。
大事なことなのでもう一度上げておきますが、1000^2*sizeof (double)サイズの計算を常時必要とするなら、800万画素の画像を常時フィルター処理しているのと同じですよ。
そもそもここでいう「高速」とは時間ではなくて計算回数が少ない(1000^2か1000^2.78)ってことであって、体感では2−3秒は待たされることかわりありません。
行列の積について言えば、ユーザー入力や初期値まちを求めるifなどの分岐がアルゴリズムにないため(単純な演算上は定数の内積なので)、
ストリーム・プロセッサ用のアルゴリズムにすれば一気に変わると思うんですけど、それはソフトウェア上の計算量(アルゴリズム)とは関係なく、ハードの機能によるものです。
どうしてもアルゴリズムや計算量にこだわるなら、数学上の証明や理論的裏付け(積分シンプソン法などのように)をちゃんと示してもらえませんか?それがないのに、ただ「やはくなった!」というのは学問じゃないでしょう。
0174デフォルトの名無しさん
2009/02/23(月) 05:51:51たぶん極端に言ってみただけだと思うんですけど、そんなにパラメータ(n=10000以上とか)必要なんですか?
もっと細かく区分にして各区画を評価すれば足りると思うんですけど。最終的には各区分の計算結果を「人間」が評価するんじゃないですかね?
それとも、その構造や系の全要素の変化を評価したりする、「神にでもなった」つもりのシミュレーションなんでしょうか?
どちらにしてもPCでやるというよりは、PCを並列にしたりより特化した計算機でやるんでしょうし、汎用的なアルゴリズムとは関係なく、その問題に特化したアルゴリズムことを話されても興味ありません。(実装が複雑でそのCPU用のコールだらけなので)
0175デフォルトの名無しさん
2009/02/23(月) 05:58:54よくわからないけど,ユーザ体感のサービスのクオリティと,サービス時間を比べられても困るという点で,一切交じり合う気がないんですねわかります
0176デフォルトの名無しさん
2009/02/23(月) 06:31:030177デフォルトの名無しさん
2009/02/23(月) 07:17:16とりあえず、君は名前を付けてみない?
0178デフォルトの名無しさん
2009/02/23(月) 07:18:40もう放っておけ
0179デフォルトの名無しさん
2009/02/23(月) 07:20:00誰が書いたか知らないけど、行列で言えばn=3万つまり、
30000^2 * 8バイトは6ギガで既に32ビットのメモリアクセスの限界を超えてるってことは分かってる?
>>160で戯言が書いてあったけど、「小さい行列」とか知ったかもそれぐらいにした方がいいよ。
アルゴリズムが200^3か200^2かなんて実質関係ないし。
2次関数のグラフで見てもその値は両者ともはるか上のほうでしょ。
結局そのアルゴwで解を得られるかどうかでしかないんじゃないのかな…
計算量を指標とすることで、学問・理論とは関係ないお花畑の議論に持ち込まれちゃって騙されちゃってるんだろうなwww考え直した方がいいよ
0180デフォルトの名無しさん
2009/02/23(月) 07:21:07バブルソートでソートしとけや
0181デフォルトの名無しさん
2009/02/23(月) 07:27:29その都度再計算したり、0でない要素だけ保存したり、ディスクに保存したり。
0182デフォルトの名無しさん
2009/02/23(月) 07:30:19そもそも、普通に買える計算機では1000x1000の行列なんかは普通はOSに叱られて作れないし、オーダーでそれぞれのアルゴリズムを比較するって言う思考自体が理想論なんだろう。
6ギガの配列は32ビット環境では確保できないし、「6ギガ^3 と 6ギガ^2 では計算効率が全然違うんです!」とか夢の話をされてもな・・・(笑)
0183デフォルトの名無しさん
2009/02/23(月) 07:31:21画面のキャプチャもできないよwwww
0184デフォルトの名無しさん
2009/02/23(月) 07:33:04速いか遅いかではないよ。
君だって、文字列検索とか結局は線型サーチ使うでしょ
0185デフォルトの名無しさん
2009/02/23(月) 07:42:41文字列検索が遅いと感じる大きさのデータを扱う場合は
他のアルゴリズムを使う事を検討するさ。
0186デフォルトの名無しさん
2009/02/23(月) 07:43:37じゃあ Google も線形サーチを使えば満足するんだねw
0187デフォルトの名無しさん
2009/02/23(月) 07:56:52アルゴリズムの話で何で評価基準ガユーザビリティなんだw
0188デフォルトの名無しさん
2009/02/23(月) 08:03:20たった8メガwww
0189デフォルトの名無しさん
2009/02/23(月) 08:06:26仮定は「無限に大きな回路を用いる」ことかな?
行列式をハードコーディングした際の計算段数は大体
log(項の長さ) + log(項の数)で, n log n くらい.
LU分解(ガウス消去)による方法の計算段数は,
各行ごとの掃き出しが 3 段(並列的に b - (a/u) v を計算)なので 3n くらい.
b - (a/u) v で計算したものを次々と使いまわすことで,段数の爆発を抑止してる.
0190デフォルトの名無しさん
2009/02/23(月) 08:11:32> 1000x1000の行列なんかは普通はOSに叱られて作れないし
どんなOSw
0191デフォルトの名無しさん
2009/02/23(月) 08:15:32それ書いたの自分だけど、メモリマップドファイル知らないの?グーグル先生に聞いて。
で、ディスクからの読み出しは線形時間の処理で、行列の処理はO(n^3)だから、行列がでかいほどアルゴリズムの改善が優位になるんだけど。
むしろ、小サイズ行列ってどこに使われるか例が欲しい。同次変換以外には?
0192デフォルトの名無しさん
2009/02/23(月) 08:31:170193191
2009/02/23(月) 08:43:35「数千数万行の行列を使うのはそういう需要があるから」ってのが答えなのか。PCやスパコンの記憶容量の発達(と十分な処理速度)でそれが近年ようやく現実的になっただけで。
019492他 ◆DRdCZDy4PY
2009/02/23(月) 12:01:06あとご指摘の通りハードウェア実装なら回路の広さはべらぼうに必要でしょう
ガウスの消去法でやります
(r s t 1 0 0)
(u v w 0 1 0)
(x y z 0 0 1)
1行以降の各行を1列目で割る。uの列ならuで割る。1段かかる。
(1 s/r t/r 1/r 0 0)
(1 v/u w/u 0 1/u 0)
(1 y/x z/x 0 0 1/x)
※1行以降の各行から第1行をひく、ただし第1行はそのまま。1段かかる。
(1 s/r t/r 1/r 0 0)
(0 v/u-s/r w/u-t/r -1/r 1/u 0)
(0 y/x-s/r z/x-t/r -1/r 0 1/x)
2行目以降も同様に。ただしm行目ならば※のときに
m-1行目までは第m行ではなく第m行に被減算行のm列目倍をひくので2段かかる。
段数表はr〜zが単位行列になることを考慮して次のようになる。
(0 0 0 7 7 7)
(0 0 0 7 7 7)
(0 0 0 5 5 5)
n次行列ならば2n+1段で終わる?
2次なら5段、3次なら7段、4次なら9段、5次なら11段、6次なら13段
#…LU分解のとき何の理解を間違えてるんだろう…
019592他 ◆DRdCZDy4PY
2009/02/23(月) 12:13:40クラメール(てかクラーメルじゃないやん)の公式が優位なのは
4次以下の行列に対してで、5次以上の行列に対しては
ガウスの消去法のほうが有利
ただもちろん加減乗除それぞれで速度違いそうなところとか
一番致命的と思われるのは、そんなだだっ広い贅沢な回路できるかーいなところ
とはいえガウスの消去法ならパイプライン方式諦めてレジスタ使うようにすれば
異なった段数で回路使いまわしできそうなんで…というかたぶんまんま
ベクタープロセッサが求められた理由の多くをこれが占めてるような
という夢をみたので、ここから壮絶な袋叩きが始まるか華麗にスルーされるのであった
019692他 ◆DRdCZDy4PY
2009/02/23(月) 12:48:26クラメールの公式で行列式や余因子の値求めるときに
ガウスの消去法が効率的な場合はそっち使えばいいじゃないか
019792他 ◆DRdCZDy4PY
2009/02/23(月) 13:09:55逆行列まであとたった2段やん…
一方、行列式の素はn項あるんで、掛け合わせるだけでlog(2)nはかかるし
そして余因子に掛け合わせる1段も必要
余因子による行列式計算の段数が
nが1増えるごとにlog n のペースで増えてしまう余因子展開法と
nが1増えるごとに2のペースでしか増えない上に逆行列まであと2段まで迫る
ガウスの消去法、か。
0198デフォルトの名無しさん
2009/02/23(月) 15:24:071000x1000の行列の書き間違いのレベルだとやっとついてこれると思ったのか、反応するゴミが多いなっておもった・・・・
2chでそれもこんな糞スレでゴミのあいてしてもね・・・
0199デフォルトの名無しさん
2009/02/23(月) 15:28:11そういうこと言っちゃうと後々責任問題になるから、もしまっとうに生きていきたいなら、自分の発言には責任もっていたほうがいいよ。あまり世の中のこと知らないだろうけど、警察とか怖いからw
0200デフォルトの名無しさん
2009/02/23(月) 15:36:13うざいだけどチラシの裏でやってくんない?
0201デフォルトの名無しさん
2009/02/23(月) 15:47:57>列の処理はO(n^3)だから、行列がでかいほどアルゴリズムの改善が優位になるんだけど。
言いたいことはよく分かるが、しかしそれは理想論じゃないか?俺も一時計算量のマジックにはまったことがる。
たとえばn=100の行列では(100^2)^3で950ギガ、改善されて(100^2)^2になっても95ギガ。
確かに早くなった気がするがそもそも「ギガ」の単位は実用的なのか?
950ミリ秒が95ビリ秒になればそれは速いが、この「速度」による評価はアルゴリズムではなくて、ハードによるんじゃなかったか?
もう一度確認するが、オーダ表記は関数(n^2, n log[2])や関数の値(n^2.22, n^3.12)が問題なのではなくて、関数の「形」が問題だったはず。
つまりいくら速くしたところで関数の形(指数関数)であることに変わりはない。
さらに>>180や>>186みたく勘違いしちゃうゴミが多いけど、「速くなった」「バブルソートは遅い」などの表現はアルゴリズム評価の参考にすらならない。
結局は実際に動かして体感で判断するんだろ。これが計算量のマジックだけど、何の指標なんだかちゃんと理解し解かないとな。
0202デフォルトの名無しさん
2009/02/23(月) 15:50:39> n=100の行列では(100^2)^3で
何で n^6 してるの?w
0203デフォルトの名無しさん
2009/02/23(月) 15:52:27> 関数の形(指数関数)
n^2 とか n^2.22 とか n^3.12 って指数関数なの?
0204デフォルトの名無しさん
2009/02/23(月) 15:59:11多少複雑なアルゴリズムなら、たいては他のアルゴリズムの組み合わせでしかないし、そうでないなら数学による証明などの理論的裏づけがないと全く理解できない。
アルゴリズムが速いかどうかなんかどうでもよくて、解が出ればいいよ。それよりも理論的な不備や実装によるバグ探しの方が数十倍恐ろしい。
020592他 ◆DRdCZDy4PY
2009/02/23(月) 16:04:33最悪のアルゴリズムでもそこそこ速い小さな問題も数多く
そういう場面では多少遅くてもバグの少ない実装を心がけるべきという主張はわかる
が
全ての問題がそうとは限らない
巨大な行列の計算なんかはモロにそういうチューンアップが問題になるケースでしょ、と
0206デフォルトの名無しさん
2009/02/23(月) 16:24:03トレードオフってものがあるよね
0207デフォルトの名無しさん
2009/02/23(月) 18:15:390208デフォルトの名無しさん
2009/02/23(月) 18:44:42> 950ミリ秒が95ビリ秒になればそれは速い
えー
0209デフォルトの名無しさん
2009/02/23(月) 20:36:440210デフォルトの名無しさん
2009/02/23(月) 20:47:170211デフォルトの名無しさん
2009/02/23(月) 20:48:060212デフォルトの名無しさん
2009/02/23(月) 20:51:19指数時間じゃなくて多項式時間な。根本から間違ってるぞ。
あと、形が問題になるのはnが大きいと言う仮定をおくから。お前はnが大きい方がいいのか小さい方がいいのかどっちなんだ。
>950ミリ秒が95ビリ秒になればそれは速いが、この「速度」による評価はアルゴリズムではなくて、ハードによるんじゃなかったか?
ハードを変えて実行速度を10倍にするのがどれだけ大変だと思ってんだ
問題の評価は同ハードでやるに決まってんだろアホ
0213デフォルトの名無しさん
2009/02/23(月) 21:02:170214デフォルトの名無しさん
2009/02/23(月) 21:04:34どこどこ?
0215デフォルトの名無しさん
2009/02/23(月) 21:06:360216デフォルトの名無しさん
2009/02/23(月) 21:27:580217デフォルトの名無しさん
2009/02/23(月) 22:37:010218デフォルトの名無しさん
2009/02/24(火) 03:13:15そんないきり立って主張するのもいいが、バグのほうが怖いな。
ちゃんと動いてたのに2年後に動かなくてバグ探しとかどうする?
そのアルゴリズムの仕様や制約が原因で。
今あるハード以上のことを考えて、限界を突破しようと、人より先に行こうとしても苦難の道なだけじゃないか?
それで報酬はいくらもらえるんだろう。windows95の時代はメモリ16-32が標準だったけど、今じゃハードの進化は10倍どころじゃないよな…
所詮ソフトウェア上での実装でしかなく上にはハードによる制約があるから、そんなにこだわっちゃうとストールマンみたいな一種の宗教になっちゃうよ。
オレはFF10で「全てを超えしもの」をもらったけど、結構大変だったぞw
0219デフォルトの名無しさん
2009/02/24(火) 03:14:570220デフォルトの名無しさん
2009/02/24(火) 03:29:10なんかカッコつけて書いてるようですけど、多項式と関数の違いを区別できてますか?
「多項式の形が重要だ!」とは普通言いませんよね?
あなたは関数との違いを書きたいようですが、多項式というからには「+」による連結を想定してるんですか?
根本的に間違ってるのはあなたの脳味噌の方でしょう。あなたの脳味噌はとっても臭そうですけど。
022292他 ◆DRdCZDy4PY
2009/02/24(火) 03:31:39ストールマンの行列の積の計算の省力方法程度で宗教なら
アンドリュー・ワイルズのフェルマー最終定理の証明とか
ペレルマンのポアンカレ問題解決とかどう評価するんだろう…
0223デフォルトの名無しさん
2009/02/24(火) 03:36:17なんでこいつはこんな時間にこんな糞スレに張り付いてるんだ?
どうせニートだろうし。一回切腹してみた方がいいんじゃね?w
0224デフォルトの名無しさん
2009/02/24(火) 03:39:13評価?おまえには一生謎のままの方がよさそうだな。一生悩んで自分なりのアルゴを出してみたらどうよ?アルゴ君w
022592他 ◆DRdCZDy4PY
2009/02/24(火) 03:41:24丸っきり気付かんかったぞ
0226デフォルトの名無しさん
2009/02/24(火) 03:51:49根本的に間違ってるのはお前の方じゃないの?
nに何かの仮定おくなら、nは定数であってn^xの指数関数という考えのはずが、お前の文章ではそれを「多項式」と書いてあるけど。
多項式というのは、2^x, 3^xではなくて、x^2 + x^3とかのx^nじゃないの?それもこの指数は普通は正数限定で、多項式ではn^3.11などありえない。
それに大きいという仮定ってのがまた理論的な表現ではないが、例えば行列なら5x5以上は既に大きいと言われて否定できないが、お前の感覚ではまだ小さいのか?
例えば5x5はxmmレジスタに入らない。
オーダーのマジックとはこういう風に、お前の感覚を麻痺させちゃうんだろう。これもまた宗教だろうな。
お前は早いところ自分の巣に帰ったほうがよさそうだ。
0227デフォルトの名無しさん
2009/02/24(火) 03:53:57ださ
おまえは早く巣に戻ってさ、もう巣から出てくんなよww
ダサいからw
0228デフォルトの名無しさん
2009/02/24(火) 04:40:210229デフォルトの名無しさん
2009/02/24(火) 04:52:22ブルーバックスを読みすぎると、あなたのように頭がおかしくなっちゃうんで今度から気をつけたほうがいいですよ。
023092他 ◆DRdCZDy4PY
2009/02/24(火) 04:55:240231デフォルトの名無しさん
2009/02/24(火) 04:58:53同ハードで評価するのは当然ですけど、その報告書や論文・ベンチマークで使ったハードが、スパコンとか店で普通に買えないようなハードだと全く意味ないってことじゃないの?
それに、ベンチのプログラムなんかいくらでもそのアルゴリズムが有利になるようなコードを書くことができるんだけど・・
ハードの進化も>>218にあるようにとんでもないし、今のゆとり世代にwindows3.1や95の時代でも「この性能は旧式のスパコンと同等だ!」とか宣伝されてたなんて信じられないだろう。
脳味噌ゆるゆるの奴はすぐ引っかかるみたいだけど、ま、騙されないようにしてよww
0232デフォルトの名無しさん
2009/02/24(火) 05:05:07なんで最初と最後に言ってる事がちがうの?バカなの?
0233デフォルトの名無しさん
2009/02/24(火) 05:21:58バカはおまえだろw
早く働いた方がいいと思うよ
0235デフォルトの名無しさん
2009/02/24(火) 05:26:58実行速度を10倍にするのがどれほど大変なのか明らかにしてくれないか?
そうじゃないならおまえの妄想か、創価学会への勧誘にしか見えんよw
おまえが高校生で、ブルーバックス読みすぎて頭おかしくされちゃってるっていうなら見逃してやるけどww
0236デフォルトの名無しさん
2009/02/24(火) 05:33:54いいやおまえだ
0237デフォルトの名無しさん
2009/02/24(火) 05:39:26> それに、ベンチのプログラムなんかいくらでもそのアルゴリズムが有利になるようなコードを書くことができるんだけど・・
なんて言っちゃってる辺りは確かにバカに思うよ
0238デフォルトの名無しさん
2009/02/24(火) 05:51:29そんなこといってる余裕があるなら早いところハロワで職探せ。おまえのお母さんは泣いてるぞ。
0239デフォルトの名無しさん
2009/02/24(火) 06:12:30どっかの市長がブログで公務員給料を公開してた。
いくら難しい勉強しても、いくら資格をいっぱい取っても年収がこれにも満たない底辺(ITドカタ)は多いだろ。
民間よりも公僕のはずの公務員の方が給料多いってのはおかしな話だけどねぇ
こんな糞スレで傷の舐めあいなんかしてないで早く働いたほうがいいんじゃないの?ww
0240デフォルトの名無しさん
2009/02/24(火) 06:20:580241デフォルトの名無しさん
2009/02/24(火) 06:29:52政治家が悪いというよりも公務員のニート・派遣への偏見の方が問題は大きそうだ。
基本給は年収100万!のバイトとか年収300万の派遣ぐらいにして、後は成果主義なら公務員も世の中の厳しさを気がつくかもな。
>>222
おまえは年収100万の分際で、「フェルマーの定理バンザイ!」とか哀れな奴だ・・・
0242デフォルトの名無しさん
2009/02/24(火) 06:50:41ニートの君には実感沸かないだろうけど、早いところ仕事探して世の中に出ればこれに実感が湧くようになるんじゃないか?かなり大問題だよ。
0243デフォルトの名無しさん
2009/02/24(火) 06:58:47こんな単発レスしか出来ないゴミに何言っても無理。
一生2chと一緒に生きていくって宣言してるようなもんだろw
確かにこういうのは自民党が言ってたけど自業自得だよな・・・自己責任だったか?w
0244デフォルトの名無しさん
2009/02/24(火) 07:20:52http://pc11.2ch.net/test/read.cgi/tech/1233622578/
0245デフォルトの名無しさん
2009/02/24(火) 07:51:540246デフォルトの名無しさん
2009/02/24(火) 08:00:290247212
2009/02/24(火) 08:01:31多項式時間、指数時間、ランダウの記号の意味ぐらい調べてきてからもう一度釣りに来てくれ。
この流れでnなんて問題の大きさ以外に何があるよ…。
0248デフォルトの名無しさん
2009/02/24(火) 08:10:38このスレの奴らは、各種アルゴリズムに詳しいだけで自分でアルゴリズムを発案するようなタイプではないな。
いつまでも計算量による評価を過信してばかりで、ただの安月給のオッサン(それもアルゴリズムは趣味なんです!とか)でしかないんじゃないかな。
その詳しそうな人という奴らの書き込みをよく見ると、ググればすぐ出てくるようなことを少し難しく偉そうに言ってるだけってことに気がつく。
各種アルゴリズムを知っていても、ここのオッサンも所詮はハードでごり押ししかできなだろうしなぁ・・・
「行列式のハードコーディングはO[n!]だから絶対ダメ!」とか
「O[n^5]のアルゴリズムは遅くて使い物にならないから使ってはだめだ!」とかアホだろ。
もしちゃんと勉強してる奴とか専門家ならこういう表現は使わない。
信用すのは勝手だけど、n=無限大みたいな何の具体例もないお花畑の説明は、上のレスには層化がどうとかあるけど宗教の勧誘と同じ
0250デフォルトの名無しさん
2009/02/24(火) 08:17:30アルゴリズム専門の准教授ですが何か
0251デフォルトの名無しさん
2009/02/24(火) 08:28:28如何お考えでしょうか
0252デフォルトの名無しさん
2009/02/24(火) 08:35:20おまえさ、アルゴ君ってだれよ?ウザイよ。
グラフ理論とかNP困難とかに関心持ってるんだろうけど、おまえの脳味噌じゃ時間の無駄だから止めとけ。
そもそも関数とか多項式の違いとか分かってないんだろ。
そのていどの奴がアルゴリズムに関心持っちゃうのはブルーバックス(もしくはウィキ)の読みすぎ。はよ働けw
0253デフォルトの名無しさん
2009/02/24(火) 09:03:03アルゴ君今日も元気だね
0254デフォルトの名無しさん
2009/02/24(火) 09:24:01おまえがこのスレで偉そうにしてる奴か。2chごときでいきがる。
2chばっかりみてると研究所のPCにウイルスが入しちゃうかもな。
研究所のPCから2chへのアクセスには最新の注意をしておいた方がいいぞ
0255デフォルトの名無しさん
2009/02/24(火) 09:25:38おまえがアルゴ君か。2chのやりすぎで頭おかしくなっちゃってんだろ。
0256デフォルトの名無しさん
2009/02/24(火) 09:29:370257デフォルトの名無しさん
2009/02/24(火) 09:58:05専門家ということですけど、アルゴリズムの分類が仕事でしょ。
分類以外に他に仕事あるんですか?
「例えば行列式は数学的定義どおりにコーディングしたらダメ」って言うのは、いいすぎですよ。
あなたがだれか知りませんが、計算量と実測速度の違いぐらい分かってますか?
それで、本当に専門家を名乗るつもりなんですかね…
0258デフォルトの名無しさん
2009/02/24(火) 10:02:50他のスレでフルボッコされてこのスレを住処にしてんだから悪口言っちゃダメ
このスレが一番の楽しみなんだしとっても可哀想な人なんだから、お山の大将が気に食わなくても黙っててあげて
0259デフォルトの名無しさん
2009/02/24(火) 10:04:090260デフォルトの名無しさん
2009/02/24(火) 10:40:39ニートのようですが、何かお仕事はお持ちなのでしょうか?
(ry
0261デフォルトの名無しさん
2009/02/24(火) 12:01:10何がもったいないの?
0262デフォルトの名無しさん
2009/02/25(水) 02:05:10あれ?レスないね。
「準教授」とか言ってみたけど名前負けだよねw
0263デフォルトの名無しさん
2009/02/25(水) 03:28:24「それもこの指数は普通は正数限定で、多項式ではn^3.11などありえない。」wwww
アルゴ君ってここまでバカだったのか
0264デフォルトの名無しさん
2009/02/25(水) 03:41:300265デフォルトの名無しさん
2009/02/25(水) 04:33:00026692他 ◆DRdCZDy4PY
2009/02/25(水) 05:23:340267デフォルトの名無しさん
2009/02/25(水) 07:50:250268デフォルトの名無しさん
2009/03/01(日) 01:31:230269デフォルトの名無しさん
2009/03/01(日) 01:35:19では考えてください。
0270デフォルトの名無しさん
2009/03/01(日) 01:51:14そのパズルを知らないし、○○のような〜では尚更わからないよ。
誰が読んでも理解できるようにルールを書けるかな?
0271268
2009/03/01(日) 02:23:525×5にボタンが配置されていて、
ボタンを押すと自身とその四方のボタンが押される。
周りにボタンが無い場合、そこは無視して考える。
すべてのボタンが押された状態になるとクリア。
これを解くアルゴリズムを考えたい。
(例:一番左上のボタンを押した場合)
■■□□□
■□□□□
□□□□□ ■押された状態
…略… □押されていない状態
僕の考えでは
一回で押せる可能な数は、3,4,5個なので
3*X + 4*Y + 5*Z = 25(5*5)
のように最適なX,Y,Zの組み合わせを考えて、無駄なくボタンを押せばいいのではと考えている。
ここでは5×5での場合を考えているが、任意の個数でも可能なアルゴリズムを考えたい。よろしくお願いします。
027292他 ◆DRdCZDy4PY
2009/03/01(日) 02:50:20オレ流解法のヒント:
最上段の押すパターンAを仮定 → N段目を■■■…■にするようN+1段目で調整
→ 最下段にパターンBがあらわれる
ので、AとBの組み合わせを幾つか調べておく
0273デフォルトの名無しさん
2009/03/01(日) 08:33:46ちなみに
・プレイヤーが押すことが出来るのは、押されてないスイッチだけ
・スイッチを押すと、上下左右の4つのスイッチの状態が反転する
・全部押した状態にしたら勝ち ~~~~~
0274デフォルトの名無しさん
2009/03/01(日) 08:52:47反転するのか。てっきり押したものはひっくり返らないのかと思って、
それならほぼ自明な解があるかなと思ってた。
0275デフォルトの名無しさん
2009/03/01(日) 09:15:05>>273 のルールなら,多項式時間で解けるね.方針は次の (1), (2) による.
(1)「押されているスイッチも押せる」というように問題を緩和して解く.
これを解くと,最終的に押すべきスイッチの一覧が得られる.
(2) 押すべきスイッチ一覧を適当な順番で押していく.
(1) はライツアウトの変種なので,連立方程式を立てて解けばいい.
詳しくは「ライツアウト 連立方程式」あたりで検索すれば分かる.
(2) は,押し方によっては手詰まりになるのが怖いのだけれど、
実はどんな順番で押していっても,手詰まりにならないことが証明できる.
よって (1) で作った一覧から押せるものを見つけて押す,を繰り返せばよい.
0276デフォルトの名無しさん
2009/03/01(日) 09:21:42解を知っていなければn×nの一時方程式(ただし変数は全部bool型)になるかな?
踏まれた状態:
1 0 0
0 0 1
0 0 0
を考えると,床の状態は
1 1 1
1 1 1
0 0 1
ってなるから…わからん
アルゴ君たのんだ
0277デフォルトの名無しさん
2009/03/01(日) 10:03:26アルゴ君じゃなくてごめんね.
マス目に対応する n^2 個の {0,1} 変数 x[1,1], ..., x[n,n] を用意し,
x[i,j] = 1 のとき (ij) ボタンを押すことを表すことにする.
さらに,各マス目の状態を表す n^2 個の条件式を立てる.
例えば ij マスに対する条件式は,
x[ij] + x[i-1,j] + x[i+1,j] + x[i,j-1] + x[i,j+1] = 1 (mod 2)
になる(関連するマスを奇数回押す条件).
あとは,立てた n^2 個の条件式を適当な方法で解けばよい.
0278デフォルトの名無しさん
2009/03/01(日) 10:26:03私をもっと踏みつけて〜
0279268
2009/03/01(日) 11:24:23ありがとう。とりあえず、やってみる
0280デフォルトの名無しさん
2009/03/01(日) 22:50:24アルゴ君のコメントが欲しいな
0281デフォルトの名無しさん
2009/03/01(日) 23:00:16そのアルゴのルールだとグラフ理論が一番効果あるんじゃないか?
0282268
2009/03/01(日) 23:20:37順番は関係ないらしい。
後は連立方程式を解くアルゴリズムを実装するだけ
みんなサンクス
0283デフォルトの名無しさん
2009/03/02(月) 05:40:32対角化ではなく,連立一次方程式だよ.
mod 2の計算だと対角化問題は解けない.
>>281
mod 2の計算をわざわざ実数ではやらないよ.
グラフ理論って,具体的には何?
028492他 ◆DRdCZDy4PY
2009/03/02(月) 05:47:14そういうことか
0285デフォルトの名無しさん
2009/03/02(月) 07:06:240286デフォルトの名無しさん
2009/03/02(月) 22:57:437年前の記事ww
俺小学生www
0287デフォルトの名無しさん
2009/03/03(火) 17:32:53素数位数の有限体 F_p というやつでな、
素数 p について p 個の元からなる集合 {0, 1, ..., p-1} の上で加減乗除を定義することができるんだ
加算減算乗算に関しては普通に mod p の上で計算すればよい
除算は乗算の逆演算で、 p が素数の場合は一意に定まる
例えば p = 7 なら
1 / 1 = 1 (1 * 1 = 1)
1 / 2 = 4 (4 * 2 = 1)
1 / 3 = 5 (5 * 3 = 1)
1 / 4 = 2 (2 * 4 = 1)
1 / 5 = 3 (3 * 5 = 1)
1 / 6 = 6 (6 * 6 = 1)
てな具合だ
こうしておくと体としてうまく成立するんで、連立方程式も矛盾なく解くことができる
(加減乗除するところを上のような演算に置き換えてやるだけだ)
今回は F_2 上での連立方程式だから単純だがな、
こういう場合に実数を持ち出さなくて済むということは知っておくといいぞ
0288デフォルトの名無しさん
2009/03/09(月) 20:24:16スレチなら申し訳ないですが誘導お願いします。長すぎるみたいなので分割投下させていただきます
----------------------------------------------------------------------------------
以下の事柄に注意し各問題に答えなさい
・与えられた文字列等のデータについては問題の指示に合うように事前処理が必要な場合がある。
・木等を表記する際に、 ダミー接点であるheadとz(外部接点)は表記する必要はない。
・同一キーについては後から挿入される方を大きいものとして扱う。
1.文字列「ASORTINGBYPOLYPHASEMERGINGEXAMPLE」に対し、3ウェイ併合を用いたポリフェーズ法による外部整列を行うこととする。
このとき、整列が始まる直前のランが配置されたテープの姿を現しなさい
条件)・主記憶の容量は文字3文字分とする。
・使用できる磁気テープは4本。
2.文字列「BINARYSEARCHQUESTION」について
1)「H」を2分探索で行うとキーの比較は何回必要か。
2)内装探索を行った場合はどうか。
ただし、比較対象文字が確定しない(文字を示すポインタアドレスが整数でない)場合は
ポインタアドレスを切り上げ後方の文字を比較対照とせよ。
ソートしたもの「AABCEEHIINNOPQRSSTUY」
3.文字列「BINARYTREESEARCH」について赤黒木を作成せよ。なお、黒リンクは1本線、赤リンクは2重線で表記せよ。
0289デフォルトの名無しさん
2009/03/09(月) 20:27:15なお、ハッシュ関数は h1(k) = k mod 23
h2(k) = 8 + (k mod 8)
とせよ。
またキーは以下のアルファベット対応表を参照し数値化せよ。
数値化したものB I N A R Y T R E E S E A R C H
2 9 14 1 18 25 20 18 5 5 19 5 1 18 3 8
5.文字列「PRACTILGOHMEV」についてパトリシアを作成せよ。
なおキーは以下のアルファベット対応表を参照し5ビットに数値化すること。
5ビット数値化したもの
P 10000 R 10010 A 00001 C 00010 T 10100 I 01001
L 01100 G 00111 O 01111 H 01000 M 01101 E 00101 V 10110
6.文字列「BTREESEARCHQUESTION」についてB木を作成せよ。ただし、レコードは外部接点のみに置くものとする。
ディスクはいくつ使用しても良いが、1ディスクにはそれぞれ3ページが格納でき、
1ページにはレコードなら4、キーとリンクならばそれぞれ7、8つずつ 格納できるものとする
----------------------------------------------------------------------------------
連投・長文お目汚し本当に失礼しました
0290デフォルトの名無しさん
2009/03/11(水) 05:49:36少しは自分で考えろ
0291デフォルトの名無しさん
2009/03/18(水) 01:54:58線形代数でライツアウト
http://d.hatena.ne.jp/tnkysr/20060510
F_2で25x25の連立方程式を解く問題。
隣接行列をA、解をx、bを問題(初期状態)として、
あと今回の場合、全消灯でなく全点灯が目的だそうなので
Ax + b = (1,...,1)^T
を解けばいい。
有限鯛F_2なんて小難しいことはさておき
実装する上では0,1のビット演算と考えればいい。
ようするに+はOR演算、*はAND演算に置き換えて
ガウスの消去法あたりで解く。
ただし5x5マスの問題だとAがランク落ちして23なので、
逆行列が存在せず(一意な解はない)、解の存在する場合は
(25-23)^2=4通りの解がある。
0292デフォルトの名無しさん
2009/03/18(水) 03:08:410293デフォルトの名無しさん
2009/03/19(木) 20:46:380294デフォルトの名無しさん
2009/03/20(金) 08:39:040295デフォルトの名無しさん
2009/03/30(月) 21:57:37特に基数木なんかの扱いに強い本ってありますか?
5ページぐらいでさらっと流されてもよーわからんのです
頭の悪い子ですいません
0296デフォルトの名無しさん
2009/04/05(日) 03:25:030297デフォルトの名無しさん
2009/04/05(日) 06:35:460298デフォルトの名無しさん
2009/04/05(日) 17:37:05どうしても、前後のポインタが2個ずつ必要になり前1、前2、次1、次2のポインタを持たせた、ダブル双方向リストなるものを考えいるのですが、こういうアルゴリズムって、皆さん使ったことありますか?
0299デフォルトの名無しさん
2009/04/05(日) 17:41:54node->prev->prevとnode->next->nextってこと?
0300デフォルトの名無しさん
2009/04/05(日) 17:48:09>>298です、どうぞよろしく
node->prevlhs
node->prevrhs
node->taillhs
node->tailrhs
こういうイメージを描いていましたが、この方が良い気もします
node->prev
node->taillhs
node->tailrhs
0301デフォルトの名無しさん
2009/04/05(日) 17:57:56node->taillhs
else
node->tailrhs
if句で、次のノードを選択するような、振る舞いにしたいので、入力に2つのポインタ
出力に二つのポインタが必要なのですが、いかがなものでしょう?
(入力側は1つでもいけそうです)
0302デフォルトの名無しさん
2009/04/05(日) 18:03:36なんで毎回前2つと次2つが必要なの
スキップリストでいいじゃん
なんでなんでなんで?
言えよコラ
0303デフォルトの名無しさん
2009/04/05(日) 18:12:01そうなんです、毎回前2つと次2つはいらないんですよ
なので、実装では
こういうのか
//ノード
struct Node {
TYPE* value;
struct Nodeprev {
Node* lhsprev; //前1番目のノード
Node* rhsprev; //前2番目のノード
};
struct Nodetail {
Node* lhsnext; //後1番目のノード
Node* rhsnext; //後2番目のノード
};
};
このように、コンストラクタで生成しようと思ってるんですが
class Node {
public:
Node(Node*);
Node(Node*, Node*);
Node(Node*, Node*, Node*);
Node(Node*, Node*, Node*, Node*);
};
ようは、ダイナミックバインドに対応した、双方向リストが欲しいんですよね、変ですか?
0304デフォルトの名無しさん
2009/04/05(日) 18:12:330305デフォルトの名無しさん
2009/04/05(日) 18:13:08×このように、コンストラクタで生成しようと思ってるんですが
○または、コンストラクタで生成しようと思ってるんですが
0306デフォルトの名無しさん
2009/04/05(日) 18:51:56どんなデータ扱うために
そんな変体データ構造必要なの?
0307デフォルトの名無しさん
2009/04/05(日) 19:35:20▲if(a == 1)
┃・処理1
┣
┃・処理2
▼
このような擬似言語ってしってますよね? これをフローチャートに展開しようと
思ったんですが、最初、2次元のvector配列で考えたんだけど、単純なif旬やfor旬などは
簡単に出来たんだけど、ネストが深くなったり、構文が複雑になると、
頭がごちゃごちゃになり、分からなくなって、混乱しました、
そこでリストポインターで、連結して、動的に連結させたほうが、
すっきり理解できると思って、思い浮かんだ発想なんです、
他に、良いアイデアがあれば教えて欲しいのですが。
0308デフォルトの名無しさん
2009/04/05(日) 19:52:16そういうのは普通は多分木でやるもんでしょ。
0309デフォルトの名無しさん
2009/04/05(日) 20:09:24struct node {
const char* name;
int depth;
struct node* child;
struct node* next;
};
0310デフォルトの名無しさん
2009/04/05(日) 20:35:300311デフォルトの名無しさん
2009/04/06(月) 02:11:090312デフォルトの名無しさん
2009/04/06(月) 02:38:490313デフォルトの名無しさん
2009/04/10(金) 19:50:210314デフォルトの名無しさん
2009/04/10(金) 22:15:07適当に抽象的に言うと、年賀状が束であると思いねぇ。
束を解いて、あて先ごとに束にし直す。
この時、最も早く仕分を終えるにはどうすればいいか?
0315デフォルトの名無しさん
2009/04/10(金) 22:23:28もっと仕分けの条件を具体的にplease
0316デフォルトの名無しさん
2009/04/10(金) 22:26:290317デフォルトの名無しさん
2009/04/10(金) 23:53:53MapReduceで。
0318デフォルトの名無しさん
2009/04/10(金) 23:55:02結局、あて先でソートするだけじゃねぇの?O(n log n)よりは速くならなそう。
0319デフォルトの名無しさん
2009/04/11(土) 10:00:380320デフォルトの名無しさん
2009/04/11(土) 10:03:450321デフォルトの名無しさん
2009/04/11(土) 10:05:230322デフォルトの名無しさん
2009/04/11(土) 10:19:35仕分けとかちゃんと定義しとくれ
0323デフォルトの名無しさん
2009/04/11(土) 10:28:04年賀状の束というのは、1つのファイルだと思ってください。
ファイルの中にはある形式で、宛先が埋め込まれており、
プログラムは宛先だけを見て、
宛先毎のファイルに分割する
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
これが想定している「仕分」です。
アルゴリズムの言葉だとどういうのかな。こんな感じか? ええと、
「宛先、a,b,c,…の 任意の組み合わせの列(長さ:可算個無限)から、
宛先毎の列を求めなさい。」
つまり、入力される列によっては、出力される列が、{a,a,a} {b,b}
0324デフォルトの名無しさん
2009/04/11(土) 10:37:12率直には、最初に出現した宛先だけを抽出する手続きがあって、
それを空集合になるまで繰り返せばいいような気もするが、
並列度を上げると早く終わるかというと、
宛先の数と関係して非効率的に思えたりするし、どーなのかなと思い。
0325デフォルトの名無しさん
2009/04/11(土) 10:43:48与えられた文字列(ストリーム)を適当な条件(宛先毎?)で分割せよ,ということ?
入力のフォーマット,特に宛先の形式と出力の形式が分からないのでなんともいえんが,
普通に考えれば.宛先の形式を受理するオートマトンを作って入力を流すだけ.
0326デフォルトの名無しさん
2009/04/11(土) 10:44:20想定してる問題が、順序を持っているので
入力
(a, b, d, a, a, c, b)
=>答え{(a,a,a)、 (b,b)、 (d)、(c)} の、列の集合かなと思ってるけど、
宛先aの(a,a,a) について、宛先は一緒だけど中身は異なるので、
aの出現順序は保存しててもらいたいです。
0327デフォルトの名無しさん
2009/04/11(土) 10:46:38入力フォーマットの説明が全然足りんよ。
その入力と書かれてる a ってのは、アルファベット小文字の a じゃないんでしょ?
0328デフォルトの名無しさん
2009/04/11(土) 10:54:070329デフォルトの名無しさん
2009/04/11(土) 10:55:220330デフォルトの名無しさん
2009/04/11(土) 16:03:550331デフォルトの名無しさん
2009/04/11(土) 21:18:29その部分に工夫の余地はなさそうだけど・・・
0332デフォルトの名無しさん
2009/04/11(土) 22:25:42ないとおもうのじゃが皆の衆
0333デフォルトの名無しさん
2009/04/21(火) 17:05:300334デフォルトの名無しさん
2009/04/22(水) 13:26:05「4以上の全ての偶数は、二つの素数の和で表すことができる。」といったものです。
次のアルゴリズムを修正して、正しい結果が得られるようにせよ と言われましたが
ゴッチャゴチャしてて意味が分かりません・・・どこを修正すればよいのでしょうか
[1]入力x
[2]a←2
[3]b←2
[4]x=a+bならyesを出力して停止 そうでなければ[5]
[5]x<a+bならbの次の素数をbとして[4]、そうでなければ[6]
[6]aの次の素数をaとする
[7]x≦a+bなら[3]、そうでなければ[8]
[8]noを出力して停止
流れ図を描いたりしてみたのですが、
入力を偶数と定めて無かったり無限ループになったりで
正しくないことは分かりますがどこを直せばいいかが良く分かりません
0335デフォルトの名無しさん
2009/04/22(水) 18:12:240336デフォルトの名無しさん
2009/04/22(水) 21:14:02「x = 素数1 + 素数2」を満たす素数1, 素数2 があると
仮定するだろ。そうすると x/2 以下の素数表が必要だ
が、まぁそれはあるとして。
その素数表の中から二つ選んで、足して x になるのを
見つければいいんだよ(無ければ多分 x は「4 以上の
偶数」じゃないってことで)。
素数表を P[i] で引けるとして、N = x/2 とすれば俺は
↓みたいに書くかな。
for (int i = 0; i < N; ++i) {
int a = P[i];
for (int j = i; j < N; ++j) {
int b = P[j];
if (a + b == x) {
// 見つかった
}
}
}
// 見つからなかった
で、その問題の a = 2 とかやってるのは、↑でいえば
a = P[0] に相当するわけだ。
0337デフォルトの名無しさん
2009/04/22(水) 22:09:19> N = x/2
これは「x/2 <= P[N] となるような N」だな。
0338デフォルトの名無しさん
2009/04/23(木) 10:44:42奇数か偶数かを最短時間で判断するようなアルゴリズムってありますか?
現状、各ビット全ての排他的論理和を計算して、奇数、偶数判定をしています。
Population Count の結果の最下位ビットを見るのが最速?
0339デフォルトの名無しさん
2009/04/23(木) 11:49:17最短時間の意味とか、どんなCPUを対象にしてるか知らんけど、
スーパースカラとかパイプラインとか考慮しつつ最短を保証するのは難しいよ。
少なくとも、現行CPUにおける(最悪判断時間が)最短のアルゴリズムは知られていない。
0340デフォルトの名無しさん
2009/04/23(木) 12:09:08CPUは16ビット〜32ビット程度の組み込み用途で想定していました。
CPUの命令セットに、ビット毎の排他的論理和を計算する専用の命令があったので、
よく知られているPopulation Count のアルゴリズムでカウントした結果の最下位ビットを
取り出すよりは、早く奇偶判定が実装出来ています。(特殊な巡回符号で符号化されたデータの復号化処理)
何か特殊なアルゴリズムがあって、総当りで排他的論理和をやるのが非効率だと困るなぁと
思って質問してみました。
0341デフォルトの名無しさん
2009/04/23(木) 13:17:16まさしくそのCPUのパフォーマンステーブルが無いと答えられるわけがない質問だったな
0342デフォルトの名無しさん
2009/04/25(土) 14:43:57CPUの処理時間とか持ち出す奴ってアルゴリズムわかってないだろ
0343デフォルトの名無しさん
2009/04/25(土) 16:12:01「アルゴリズム」がわかってなくて「現行CPUにおける最短のアルゴリズム」とか言っちゃうやつ。
0344デフォルトの名無しさん
2009/04/25(土) 16:50:23理論的には、計算可能と不能の2種類しか存在しません。
解ける問題は、定量的解釈により多項式か指数関数は、計算機モデルには依存しません。
しかし、異なる計算機モデルではその枠内で計算量が異なるのはごく当たり前です。
nビットランダムアクセスメモリモデルと、シーケンシャルアクセスメモリモデルでは、
求まる計算量が違うのです。
その場合、最短計算時間を出すことのできるアルゴリズムも変わってきます。
0345デフォルトの名無しさん
2009/04/25(土) 17:54:150346デフォルトの名無しさん
2009/04/25(土) 18:07:23「頑張ってグーグル先生に聞きました!」て感じのレス乙
0347デフォルトの名無しさん
2009/04/25(土) 19:09:20http://tsushima.2ch.net/test/read.cgi/newsplus/1240642932/
0348デフォルトの名無しさん
2009/04/25(土) 20:25:40前段は正しいが、計算機のモデルに合わせて計算量が変わるというのはアルゴリズムの問題ではないので後段は前段と矛盾している。
計算量はそのアルゴリズムに所属しているものですが、30年前O[n^3]で30分のものを今の計算機で行うと1秒で完了するって事は、計算量は多いが完了するのは超高速というアルゴリズムによくあるマジックです。
0349デフォルトの名無しさん
2009/04/25(土) 20:26:48詳しく教えてもらえませんか?
0350デフォルトの名無しさん
2009/04/25(土) 20:35:14要ははパリティだよね。組み込みという事なら符号化/復
号化も含めてハードでやった方が良い気もするけど、
unsigned
parity(unsigned x) {
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 1;
}
位がオーソドックスじゃない?x86 なら演算結果下位
8bit のパリティが PF に入るから、
unsigned parity(unsigned x) {
x ^= x >> 16;
x ^= x >> 8;
__asm__ __volatile__("pushf; pop %0":"=r"(x)::);
return !((x >> 2) & 1);
}
ってところか。
0351デフォルトの名無しさん
2009/04/25(土) 20:48:01いまだに開眼出来てない人なのでほっとしておいてください。
この人たちは>>348をいくら読んでも理解できず自分で考えることが出来ない人たちなんで。
たとえば「このアルゴリズムは速い!遅い!」とか考えてる人たちですよ?
0352デフォルトの名無しさん
2009/04/25(土) 20:49:17344はアホっぽいからどうでもいいんだけど、
計算機のモデルにあわせて計算量は代わるんじゃない?
極端な例だと、「ソートがΘ(n log n) 」というのは代数決定木モデルなどの話で、
O(n) になる計算モデルもあるよね(例えば実数を持ちまわれるモデル)。
そこまで極端に変えなくても、基本演算のコストが変われば
O(...) に隠れた定数が変わるのは当たり前だと思うんだけど?
0353デフォルトの名無しさん
2009/04/25(土) 21:05:33厳密に言うと、多項式で解けるようになる
当然計算モデルによって計算量は変わるぞ
>>348は計算モデルをわかってなさすぎ
CPUの処理時間とか言いだす奴は論外
0354デフォルトの名無しさん
2009/04/25(土) 21:13:46スマン
計算量はアルゴリズム固有であって、計算モデルが変わったらアルゴリズムは通用しないことが抜けてた
0355デフォルトの名無しさん
2009/04/25(土) 21:16:11何が通用しないって?
0356デフォルトの名無しさん
2009/04/25(土) 21:18:15荒らすな鼻糞
0357デフォルトの名無しさん
2009/04/25(土) 21:20:10ってこと。
クイックソートは単一のチューリングマシン上ではO(NlogN)だが
それを並列計算機モデルや量子コンピュータモデルでは動かせないからO(logN)にはならないってこと
0358デフォルトの名無しさん
2009/04/25(土) 21:24:21それもチューリング何とかと同じ空想の産物つまり実現不可能なモデルでアルゴリズムを作るとことでは?
このスレはSFネタスレなんですか?
0359デフォルトの名無しさん
2009/04/25(土) 21:25:230360デフォルトの名無しさん
2009/04/25(土) 21:25:52量子チューリングマシンでも通常のクイックソートは動くでしょ。
もちろん、計算量は O(log n) にはならないけど。
0361デフォルトの名無しさん
2009/04/25(土) 21:33:58量子コンピュータはアルゴリズムもまともに検討されてない段階
0362デフォルトの名無しさん
2009/04/25(土) 22:15:21実体としての量子コンピュータをどうするかという問題はさておき、
数学的な概念としての量子チューリングマシンははっきりしてるし、
それが古典的チューリングマシンと計算可能性の意味で等価であることは証明されてるから
どちらか一方でしか本質的に動かないアルゴリズムは存在しないよ。
0363デフォルトの名無しさん
2009/04/25(土) 22:54:45あとは実際の計算機ができるのを待っているような状態。
>>362 のいうように、実際の計算機で計算可能かどうかはともかくだが。
0364デフォルトの名無しさん
2009/04/25(土) 23:10:30というかオーダー決めるときに使う”ステップ”って何?
0366デフォルトの名無しさん
2009/04/26(日) 00:01:51理論計算量の人のいう「ステップ」はチューリングマシンで実装したときの
状態遷移のこと(これは明確に定義可能)。
ただ、普通のアルゴリズムの議論では、ここまで戻ってステップ数を見積もることは無くて、
アルゴリズム中で支配的な演算の回数を数えるのが普通。
たとえばソーティングだったら「比較が O(n log n) 回」とかいう言い方をするし、
行列計算なら「乗算が O(n^2) 回、加算が O(n^3) 回」とかいう言い方をする。
ある程度共通認識として何に着目するかが分かっていたら、「○○が O(n) 回」を
「計算量が O(n)」とか言ったりするけど、何が O(n) なのかは意識しないといけない。
あと、言うまでもないことだけど、計算量とオーダーってのは、全く別の概念だよ。
歴史的にも別物だし、オーダーで計算量を表記しない分野もあるしね。
0367デフォルトの名無しさん
2009/04/26(日) 00:10:070368デフォルトの名無しさん
2009/05/08(金) 19:20:350369デフォルトの名無しさん
2009/06/06(土) 21:04:42漢字が出てきたらどうすればいいんだろう?
漢字はあくまでデフォルトの並びをします
しかできないのかな
0370デフォルトの名無しさん
2009/06/06(土) 21:06:530371デフォルトの名無しさん
2009/06/06(土) 21:10:300372デフォルトの名無しさん
2009/06/06(土) 21:15:16つ辞書
0373デフォルトの名無しさん
2009/06/06(土) 21:48:50IMEから漢字の読みのデータをテキストファイルか何かに移せるの?
0374デフォルトの名無しさん
2009/06/06(土) 22:07:48MS-IMEでもATOKでもそれ以外でも基本的なAPIは
OSの段階で共通だから、そんな心配は要らないよ。
0375デフォルトの名無しさん
2009/06/06(土) 22:26:350376デフォルトの名無しさん
2009/06/06(土) 23:14:25リストの任意の位置に新たにデータを挿入するときにリストの先頭からポインタを辿っているので次第に遅くなっていきます。
10万件くらいまでならまだ実用的ですが、100万件になると実用に耐えられなくなります。
キャッシュすれば速くなると思い256個のキャッシュを作ったら100万件でも十分実用的になりました。
キャッシュ以外に速くする方法を探しています。
0377デフォルトの名無しさん
2009/06/06(土) 23:18:270378デフォルトの名無しさん
2009/06/07(日) 05:58:41任意の位置が与えられるなら(表現が変か?)、O(1) だよね。
知りたいのは、挿入すべき位置を高速に探索する方法でいいの?
どうしても双方向リンクリストじゃないと駄目な理由があるの?
ソートされてるの?
ソートされてる必要があるなら平衡木とかどうよ。
ソートされている必要が無ければハッシュリストはどうよ。
0379デフォルトの名無しさん
2009/06/07(日) 11:10:11>挿入すべき位置を高速に探索する方法でいいの?
その通りです。
リンクトリストでないとダメな理由は、汎用データのデータ構造のライブラリを作っているからです。
汎用データといってもgeneric pointer(void *)を回しているだけですが。
ソートは、使う側が任意のタイミングで呼び出すことが可能です。
よって、常にはソートされている保証はありません。
ハッシュリストですか。
たしかに検索O(1)ですね。
すでにライブラリに含まれていますので考えてみます。
ありがとうございました。
0380デフォルトの名無しさん
2009/06/07(日) 12:05:26Problem 195 懼
辺が整数の三角形で、60度の角を1つだけ持つ三角形を"60度角の三角形"と呼ぶことにする。
r を60度角の三角形の内接円の半径とする。
r懼100 では60度角の三角形は1234個ある。
T(n) を r懼n を満たす60度角の三角形の数とする。
T(100) = 1234, T(1000) = 22767, T(10000) = 359912 である。
T(1053779) を求めよ。
解き方が解る人 教えてくだせい。
0381デフォルトの名無しさん
2009/06/07(日) 14:15:48自分で作ってたんじゃなかったの?
嘘はいかんよ
0382デフォルトの名無しさん
2009/06/07(日) 14:44:34どこかの誤爆であることを祈るが、勘違いしているようなので言わせてもらう。
汎用なDoubly Linked Listsを作っていて、任意の位置に挿入する関数で時間がかかっている。
理由はポインタを辿っているからなので、それを解消するためにキャッシュ領域を作ってみた。
結果、100万件くらいまでは実用レベルに達した。
もっと効率が良い方法はないかと尋ねる。
リストの挿入はO(1)だよね。<あたりまえだろ
データ構造として平衡木やハッシュはどう?
ハッシュをリンクトリストにコンポジットすればいいのか。
既に作っているから考えてみよう。
リスト作っていたんじゃないの?ハッシュ使うのかよ<勘違い
0383デフォルトの名無しさん
2009/06/07(日) 16:13:520384デフォルトの名無しさん
2009/06/07(日) 19:09:05なんかまったく分かってないみたいだね
そんなことより勉強しなおしたほうがいいよ
0385デフォルトの名無しさん
2009/06/07(日) 19:25:07検索して驚いたんだけど、そこまでは自力で行ったのか?
愚直にやるだけで、なかなか大変だと思うけど。
ちょっと説明してたら小冊子が書けそうだけど、どこが分からないか分かる?
六十度角を挟んだ三角形(二辺)の列挙はできる?
整数比になるかは調べられるよね?
外接円ってのは外心ってのを出すんだけど、これは検索してね。
あと、正三角形を弾くのを忘れないように。
0386デフォルトの名無しさん
2009/06/07(日) 20:06:010387デフォルトの名無しさん
2009/06/08(月) 00:06:270388デフォルトの名無しさん
2009/06/08(月) 00:17:340389デフォルトの名無しさん
2009/06/08(月) 00:31:460390デフォルトの名無しさん
2009/06/08(月) 09:30:57てかアルゴリズムでもなんでもないが、人工知能関係では有名な思考実験。
0391デフォルトの名無しさん
2009/06/08(月) 11:18:340392デフォルトの名無しさん
2009/06/08(月) 18:56:34恥ずかしいな
0393デフォルトの名無しさん
2009/06/08(月) 20:04:260394デフォルトの名無しさん
2009/06/08(月) 20:12:40チーとかウォ言うのが組み合わさって他国語話者が空耳アワー出来るな人口無能
な研究。
0395デフォルトの名無しさん
2009/06/09(火) 00:15:43共産主義者じゃん
0396デフォルトの名無しさん
2009/06/09(火) 04:55:560397デフォルトの名無しさん
2009/06/09(火) 05:09:04共産主義者じゃん」と言ってるの
0398デフォルトの名無しさん
2009/06/09(火) 08:05:520399デフォルトの名無しさん
2009/06/09(火) 08:11:570400デフォルトの名無しさん
2009/06/09(火) 14:14:420401デフォルトの名無しさん
2009/06/11(木) 01:12:220402デフォルトの名無しさん
2009/06/11(木) 01:15:290403デフォルトの名無しさん
2009/06/11(木) 01:19:18えーとそのーあー
書き込んでる最中だけど、読み込みブロックと重ならないなら
同時に読み込みもできるキューってどうやって
書けばいいのですかね?
0404デフォルトの名無しさん
2009/06/11(木) 13:11:340405デフォルトの名無しさん
2009/06/11(木) 13:50:36> 書き込んでる最中だけど、読み込みブロックと重ならないなら
> 同時に読み込みもできるキューってどうやって
各ブロックに read-write-lock 設定すりゃええんちゃうの?
0406デフォルトの名無しさん
2009/06/11(木) 15:22:08lock-free queue あたりで探せば色々見つかると思う
0407デフォルトの名無しさん
2009/06/12(金) 08:56:10・enqueue -> tail.nextとtail に新しいノードを挿入
・dequeue -> head.next が空ならreturnまたはブロック、あればhead := head.nextとして、nextを新たな番人とする
で、どうかな?だめかな?
0408デフォルトの名無しさん
2009/06/12(金) 09:04:340409デフォルトの名無しさん
2009/06/24(水) 17:43:15数学的知識が乏しいので易しめでお願いします。
0410デフォルトの名無しさん
2009/06/24(水) 18:51:500411デフォルトの名無しさん
2009/06/24(水) 19:52:45多角形はしらね
0412デフォルトの名無しさん
2009/06/24(水) 20:01:490413デフォルトの名無しさん
2009/06/24(水) 20:22:490414デフォルトの名無しさん
2009/06/24(水) 21:37:06任意の多角形は三角形分割できるので,三角形分割しておいて
(1) 三角形を、各三角形の面積に比例する確率で1つ選択
(2) 選択した三角形内からランダムに選択
とすることで(一様)ランダムサンプリングすることができる.
前処理の三角形分割は O(n log n) ででき,各サンプリングは O(1) でできる.
その図形を囲むサンプルしやすい領域があって(外接長方形など),
図形がその領域の中の大きな面積を占めているなら >>412 の方法でも良い.
幾何的データ構造を前処理しておけば内外判定は O(log n) でできるので,
O(log n × 1/(1-r)) でできる.ただし r は図形の占める面積の比率.
0416デフォルトの名無しさん
2009/06/24(水) 21:50:33ありがとうござます!頑張ってみます。
0417デフォルトの名無しさん
2009/06/24(水) 21:51:300418デフォルトの名無しさん
2009/06/30(火) 19:21:33取り敢えずttp://next1.cc.it-hiroshima.ac.jp/MULTIMEDIA/numeanal1/node16.htmlで理屈は判ったが
実装に落とす過程がわからん。ついでに言えば、NumericalRecipesの実装もよく判らんかった。
客先の過去の実装はそのどちらとも違っているんだが、こいつが微妙に遅いんだ……
0419デフォルトの名無しさん
2009/07/01(水) 09:25:03客先の実装は
奥村晴彦「C言語による最新アルゴリズム事典」
のコードかな?違っていたら試してみたら?
ネットにもソースが転がっているはず。
0420418
2009/07/01(水) 09:42:40情報THX。
それで正解、奥村本の引用でした。
# つーか、一つのプロジェクト内に奥村本の引用とNRの引用とまた違う実装の三種類も混ざっているのが何とも……_/ ̄|○
これで出自がはっきりしたので心置きなく参考にできる。
引き続き、情報あれば宜しく。
# こちらで最適化した最終版は、問題がないようなら公開しますんで。
0421デフォルトの名無しさん
2009/07/09(木) 18:52:48私はこの事実に関してダチョウアルゴリズムを適用することにした
0422デフォルトの名無しさん
2009/07/09(木) 19:40:190423デフォルトの名無しさん
2009/07/09(木) 20:20:14wikipedia見たらマジであるwくだらねーw
0424デフォルトの名無しさん
2009/07/10(金) 22:10:310425デフォルトの名無しさん
2009/07/10(金) 22:39:040426デフォルトの名無しさん
2009/07/12(日) 00:53:56敵(x1,y1)
プレイヤー(x2,y2)
・求めたいもの
プレイヤーを中心にした半径50pixelの円周上で、敵と一番近い座標
数学嫌いな私には難しくて・・どう計算すれば良いでしょう?
0427デフォルトの名無しさん
2009/07/12(日) 01:01:40距離R
R^2 = (x1-x2)^2+(y1-y2)^2
0428デフォルトの名無しさん
2009/07/12(日) 01:13:150429デフォルトの名無しさん
2009/07/12(日) 01:16:20x = x2 + (x1 - x2) * 50 / R;
y = y2 + (y1 - y2) * 50 / R;
0430デフォルトの名無しさん
2009/07/12(日) 01:16:48ん?
それだけじゃよくわからないけど
0431デフォルトの名無しさん
2009/07/12(日) 01:19:360432デフォルトの名無しさん
2009/07/12(日) 01:21:45ん?
どの円との交点?
0433デフォルトの名無しさん
2009/07/12(日) 02:25:00回答してくれた方ありがとう
0434デフォルトの名無しさん
2009/07/12(日) 03:23:29未定義の識別子ってやつですね: 円
0435デフォルトの名無しさん
2009/08/18(火) 20:44:270436デフォルトの名無しさん
2009/08/24(月) 14:39:06漸化式 (再帰) と一般項 ( a_n = ((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5) ) の両方で作って、
各々の計算時間を計ってみた。
n = 46 のとき、
漸化式だと 28.968 秒、
一般項だと 0.000 秒、
だった。
ちなみにどちらで計算しても a_46 = 1836311903 だった。
0437デフォルトの名無しさん
2009/08/24(月) 16:08:42さすがにその漸化式の計算は O(2^n) かかってるからなあ。
普通にDPすりゃ n = 46 程度一瞬で終わる。
あと、その一般項の計算はきっと結構危うくて、
通常の実装だと浮動小数点の打ち切りが計算途中に含まれている。
sqrtなんて持ち出さずに行列のn乗に落としたほうが安全。
0438デフォルトの名無しさん
2009/08/24(月) 17:49:14漸化式は相変わらず 27.734 秒だった。
プログラムの見た目が単純なら計算が速いと思い込んでたが、
実際に作ってみると行数が多くてもアルゴリズムがいい方が計算が速いんだな。
0439デフォルトの名無しさん
2009/08/24(月) 17:59:480440デフォルトの名無しさん
2009/08/24(月) 18:30:18実測値出せるならそのほうがよくない?
0441デフォルトの名無しさん
2009/08/24(月) 19:34:17#include <stdbool.h>
// 再帰だって結果をプールすれば速いのよ
static unsigned long long fib(unsigned n)
{
if (n == 0) return 0;
static unsigned long long a[94] = {0, 1, };
bool inRange = n < sizeof(a) / sizeof(* a);
if (inRange && a[n] != 0) return a[n];
// if (fib(n - 1) > INT64_MAX) return UINT64_MAX;
unsigned long long val = fib(n - 1) + fib(n - 2);
if (inRange) a[n] = val;
return val;
}
int main()
{
for (int n = 0; n <= 93; ++n) { // max fib with ulonglong
printf("%d:%llu\n", n, fib(n));
}
return 0;
}
0442デフォルトの名無しさん
2009/08/24(月) 19:35:23実時間と理論計算量では計測の目的が違うので
どちらが良いとか比較できるものじゃない。例えばこの例だったら、
「計算量が違うと実際これだけ差が出るんですよ」
と主張したいのならば実時間を出すべきだし、
「こんなに時間が違うけど、その原因はアルゴリズムですよ」
と主張したいのならば理論計算量を出すべき。
438の書き込みを見る限り前者っぽいので、
わたしはこの例なら実時間を出すのが適切だと思う。
ちなみに、実問題への応用のあるアルゴリズムの論文では
計算量をオーダーとかで見積もりつつ、さらに
計算機環境を明らかにして、実時間を出すのが普通。
0443デフォルトの名無しさん
2009/08/24(月) 20:58:43>>437 で DP って出てるじゃん。
unsigned
fib(int n) {
unsigned t = 0;
unsigned x = 1;
while (0 < --n) {
unsigned y = t + x;
t = x;
x = y;
}
return x;
}
0444デフォルトの名無しさん
2009/08/24(月) 21:03:06元のレスに合わせて、あえて再帰で書いたんでしょや
0445デフォルトの名無しさん
2009/08/24(月) 22:04:12http://science6.2ch.net/test/read.cgi/math/1193293517/
273 名前: 132人目の素数さん Mail: sage 投稿日: 2009/08/16(日) 22:23:53
O(logn)で計算する方法。こないだ大学の課題に出てきた。
int fib (unsigned int n) {
int x = 0, y = 1, a = 1, b = 0, t;
for (;;) {
if (n & 1) {
t = a;
a = a * x + b * y;
b = t * y + b * (x + y);
}
n >>= 1;
if (n == 0) return b;
t = x;
x = x * x + y * y;
y = t * y + y * (t + y);
}
}
0446デフォルトの名無しさん
2009/08/26(水) 06:04:41これ、n が奇数の時しか b が更新されてなくて
最後に b を返してるけど、n = 8 とか駄目じゃね?
試してないけど。
0447デフォルトの名無しさん
2009/08/26(水) 06:48:46n=4 t=0 a=1 b=0 x=1 y=1
n=2 t=1 a=1 b=0 x=2 y=3
n=1 t=2 a=1 b=0 x=13 y=21
n=0 t=1 a=13 b=21 x=13 y=21 return 21
1 1 2 3 5 8 13 21
であってるかな
0448デフォルトの名無しさん
2009/08/26(水) 07:56:56失敬失敬。
0449デフォルトの名無しさん
2009/08/26(水) 17:54:55これどうやって導き出したの?
一般項の計算を整数で行うようにしたぽ、とか、そういう感じ?
数学ワカラン俺にもわかる説明をたのむ
0450デフォルトの名無しさん
2009/08/26(水) 20:52:210451デフォルトの名無しさん
2009/08/26(水) 21:29:01450のとおりだけど,もう少し詳しく言うと,
A = {{1,1},{1,0}} という行列を用意すると
A^n = {{fib(n),fib(n-1)},{fib(n-1),fib(n-2)}} になる.
証明は帰納法なり何なり.
よって後は A^n をどう計算するかという話なんだけど,
例えば n = 11 = (0b1011) だったら,A^n = A * A^2 * A^8 みたいにやる.
プログラム中で x, y は A^{2^k} を保持するために使い,
a, b は最終結果が入るように使ってる.
0452デフォルトの名無しさん
2009/08/26(水) 22:21:29数値をn進数とみなして(n-1)の剰余を求めるとできますが
なぜですか?理屈は
0453デフォルトの名無しさん
2009/08/27(木) 06:41:55Kernighanの方法のことを言ってるつもり?
0454デフォルトの名無しさん
2009/08/27(木) 09:39:07http://www.nminoru.jp/~nminoru/programming/bitcount.html
がひっかかった。
バージョン4と5はさっぱりわからん……
0455デフォルトの名無しさん
2009/08/27(木) 11:48:53> ビットカウント演算はビット演算命令の組み合わせで
> ハードウェア回路を用意した場合 以上の速度が出せ
> るのでまったく無駄である
これに発奮したのかわからないが、Core-i7 には
population count 命令 POPCNT が追加された。
0456デフォルトの名無しさん
2009/08/27(木) 11:51:175はBeautiful Codeに載ってたな
十進数で言うと、格ケタの数字を足すのに
12,345 -> 10305 + 204 = 10509
10,509 -> 109 + 5 = 114
114 -> 11 + 4 = 15
ってやってるだけ。見た目はアレだけど、実は難しくないぽ
16進数表現になってる部分を二進数表現に置き換えると分かりやすい
0457デフォルトの名無しさん
2009/08/27(木) 12:09:46PowerPCにはnlzもあるんだっけ。
ビット反転のみハードウェア化して、ntzと組み合わせてもいいよね。
Intelってビット反転は追加してたっけ。
0458デフォルトの名無しさん
2009/08/27(木) 13:05:04bsf(bit scan forward) と bsr(bit scan reverse) があるっぽい。
0459デフォルトの名無しさん
2009/08/27(木) 20:38:050460デフォルトの名無しさん
2009/08/27(木) 21:44:400461デフォルトの名無しさん
2009/09/02(水) 09:32:59このページを参考にしてJavaでダイキストラ法を実装しようとしています。
↓これが私の書いたソースコードのダイキストラアルゴリズムの部分です。
ttp://hwm2.gyao.ne.jp/manu-gino/up/dai.java
allNodeとpath(各リンクのコスト情報を持った行列)を以下のように初期化します。
Vector<Integer> allNode = new Vector<Integer>();
for (i = 0; i < NUM_NODE; i++)
allNode.add(i);
public static int path[][] = {
{MAX, 20, 50, MAX, MAX},
{MAX, MAX, 20, 70, MAX},
{MAX, MAX, MAX, 40, 30},
{MAX, MAX, MAX, MAX, 20},
{MAX, MAX, MAX, MAX, MAX},};
0462461
2009/09/02(水) 09:42:33スレ汚し失礼しました。
0463デフォルトの名無しさん
2009/09/02(水) 12:27:310464デフォルトの名無しさん
2009/09/08(火) 01:55:40200次元程度の実対称行列がターゲットだと,
ヤコビ法より,QR法+LU展開で固有ベクトル求める とかのほうが速度出るのかな?
0465デフォルトの名無しさん
2009/09/08(火) 07:28:18200×200程度だったら何やっても大して問題にならない。
けど、一般的にはヤコビ法はあまり良い方法じゃない。
0466デフォルトの名無しさん
2009/09/08(火) 11:12:15そうなんだ・・・
一応両方実装してみたんだけど,
QR+LUのほうは,なんか収束しないパターンみたいなのがあるみたいで,
無限ループしてる・・・。
0467466
2009/09/08(火) 11:31:4770万回くらい200次元くらいの実対称行列の固有値・固有ベクトル全てを求めるから,少しでも早いほうがいいんだよなぁ・・・
0468デフォルトの名無しさん
2009/09/08(火) 17:00:36収束しないのはきっと実装が悪いんだよ.
それにしても,70万回も固有値固有ベクトルを求めるのは
用途にもよるけど,筋が悪い気配を感じる.
本当に全行列の全固有値・固有ベクトルが必要か,
各行列に関係はないか(同時に前処理,Warm startなどはできないか),
などは検討済み?
0469466
2009/09/08(火) 19:00:46ありがとう。
>収束しないのはきっと実装が悪いんだよ.
もう一回見直し,組み直しするかぁ・・・
>本当に全行列の全固有値・固有ベクトルが必要か,
>各行列に関係はないか(同時に前処理,Warm startなどはできないか),
>などは検討済み?
分析のプログラムだからそういうわけにいかないんだよねー・・・
0470デフォルトの名無しさん
2009/09/09(水) 14:41:02固有値問題のアルゴリズムを実装するのが目的でないならLAPACKなどを使うべき
0471デフォルトの名無しさん
2009/09/29(火) 22:02:390472デフォルトの名無しさん
2009/09/29(火) 22:09:260473デフォルトの名無しさん
2009/09/29(火) 22:37:22俺が考えたのはこれ
int gcf(int a, int b){
int r;
if(a <= 0 || b <= 0) return -1; /* 0以下ならエラー */
if(a > b) r = b;
else r = a;
while((a % r != 0 || b % r != 0 ) && --r > 1);
return r;
}
しかし、アルゴリズムについてのサイトを見るとこのようだった。
int gcf(int a, int b){
int r;
if(a <= 0 || b <= 0) return -1; /* 0以下ならエラー */
if(a < b){
r = a;
a = b;
b = r;
}
while(1){
r = a % b;
if(r == 0) return b;
else{
a = b;
b = r;
}
}
return -1;
}
実測してみると、下のアルゴリズムの方が速かった。
テラ難しいけど、より速いアルゴリズムというのがあると嬉しくなるよね。
0474デフォルトの名無しさん
2009/09/30(水) 09:01:39最大公約数は GCF と言わないこともないが普通 GCD だな
あとアルゴリズムを知りたければユークリッドの互除法でぐぐるとよろしい
0475デフォルトの名無しさん
2009/09/30(水) 09:48:39つまりあなたは、小学生にも理解できるユークリッドの互除法が「テラ難しい」のですね?
それって要は、頭の使い方も忘れているってことだな。
# 元から知らないで来てしまったのかも知れないが。
0476デフォルトの名無しさん
2009/09/30(水) 09:58:27やべ、間違って最小公倍数って書いちゃったorz
最大公約数です。
ユークリッドの互除法っていうのか。
ありがとう。
0477デフォルトの名無しさん
2009/09/30(水) 10:59:35そこまで言う資格があるのはユークリッドの互除法を自分で考え出せた人間だけだと思うが
罵倒レスで安価ミスる奴がそんな頭いいのかなぁ
0478デフォルトの名無しさん
2009/09/30(水) 11:15:21昨今では知らない奴がいるのも仕方ないし
何事もきっかけだから喜んでる奴に水を差すのもどうかと思うが
ごめん3行越えたからやめる
0479デフォルトの名無しさん
2009/09/30(水) 11:26:34知らない人が多いことを想定しているような書き方のサイトばかりだ
0480デフォルトの名無しさん
2009/09/30(水) 11:58:17>>477
私は小学生自分に再発見したよ。
0481デフォルトの名無しさん
2009/09/30(水) 12:36:06そうか
人間的に残念な奴だな
0482デフォルトの名無しさん
2009/09/30(水) 13:43:06小学生「時分」か?小学生は自分の好きなことにだけは特異的な才能を発揮するからな。
0483デフォルトの名無しさん
2009/09/30(水) 14:25:30小六で教えてもらっても尚なかなか理解できない人もいるし
ただアルゴリズムスレって場所においてユークリッドの互除法が
テラ難しいってのはちょっと違和感あるなあ
0484デフォルトの名無しさん
2009/09/30(水) 17:02:07アルゴリズムの基礎の基礎じゃん
0485デフォルトの名無しさん
2009/09/30(水) 18:05:530486デフォルトの名無しさん
2009/09/30(水) 19:35:340487デフォルトの名無しさん
2009/09/30(水) 22:31:042^32 * (2^32 - 1) / 2 ≒ 2^63 通り
あるね
総当たりできるもんならやってみな
0488デフォルトの名無しさん
2009/09/30(水) 22:51:240489デフォルトの名無しさん
2009/09/30(水) 22:54:26w
0490デフォルトの名無しさん
2009/10/03(土) 23:23:39様々な周期、振幅の正弦波を重ね合わせた波形があるんですが
この波形から短期的なピーク値(っぽいところ)を抽出したいと思っています
元の波形がわかっていれば簡単そうですが、
わからない場合にピーク値(っぽいところ)を抽出するにはどんなアルゴリズムが考えられるでしょうか・・・
0491デフォルトの名無しさん
2009/10/03(土) 23:53:050492デフォルトの名無しさん
2009/10/04(日) 07:24:21様々な価値と重さを持つボールが複数と、様々な重量制限のある箱が複数ある。(ボールと箱の数の関係は任意)
ここで、できる限りのボールを箱に詰めたいが、使う箱はできるだけ空きの重量を少なくしたい。
というものです。評価指標は、「使う事になった箱の残重量を最低にする」と「詰めたボールをできるだけ多くする」です。
一つの箱ならナップザック問題になると思っていますが、、、この問題はナップザックも複数あってどうしたものかと思います。
何か良い方法はあるでしょうか。
0493デフォルトの名無しさん
2009/10/04(日) 11:02:480494デフォルトの名無しさん
2009/10/04(日) 11:08:230495デフォルトの名無しさん
2009/10/04(日) 11:34:07(1) ボールを詰められる数の最大化
(2) それを詰める範囲で空き容量の最小化
という問題でいいのかな?だとすると,
これは multi knapsack problem の多段階バージョンで,非常に難しい.
厳密解法としては
(1) は全ての箱を使う前提でボールに関する multi knapsack の実行可能解列挙
(2) はその解候補について箱に関する multi knapsack の最適化
になるので,それぞれで適当な緩和解法を使うのが妥当っぽい.
0496デフォルトの名無しさん
2009/10/04(日) 12:07:57ただのナップザックならそれでも良いですが、入れさせるナップザックをどんな順で並ばせるか、も問題だと思っています。
>>493-495
やはり結構難しい問題になるんですね。。。そこで、遺伝的アルゴリズムを使ってみよう、という話になるのですが
では遺伝子をどのように設計したらよいか?と思うのです。
とりあえずボールがn個(B1,B2,B3,...,Bn)(ボール配列)と箱がm個(H1,H2,...,Hm)あるとして、「ボールpはq番目の箱
に入る」を「ボール配列のp番目にqという数字を振る」事とする。
これでボール配列に1〜mまでの番号をでたらめに撃って初期値とする。。。とりあえず使う箱とそれに入るボール、
使われない箱の特定ができますよね。
この配列は自分自身内で順序を変えるのはいいですが、違う遺伝子と交叉とかしてしまうと、破綻してしまうケース
が大すぎてしまう気がしています。。。
0497デフォルトの名無しさん
2009/10/04(日) 15:14:01> 「ボールpはq番目の箱 に入る」
「ボールを入れられる箱のうち残り容量の大きい方から
q 番目に入れる」にしたら駄目かな?
0498デフォルトの名無しさん
2009/10/04(日) 17:18:17495のアドバイスは完全に無視か
0499デフォルトの名無しさん
2009/10/04(日) 18:01:091) 箱それぞれについて取りうる状態を列挙
2) 1 の中から題意を満たす組合わせを列挙
みたいになるのなら条件によっては爆発するってことじゃね?
0500デフォルトの名無しさん
2009/10/04(日) 23:53:17無視なんてことはないのですが、multi knapsackという用語をはじめてみたのでなんともいえなかったのですよ。
結局はっきりしないままなのですが、理論や実装例みたいなものが載っているサイトがあったら紹介してほしいです。
0501デフォルトの名無しさん
2009/10/05(月) 01:25:34加するとそれまでの最適解で使っていた箱を使わなくな
る可能性もあるんだな。
0502デフォルトの名無しさん
2009/10/05(月) 06:42:16価値???
多分ボールと箱両方から攻めて数次元の代数幾何学云々で余白が狭すぎる。
0503デフォルトの名無しさん
2009/10/05(月) 09:59:45http://en.wikipedia.org/wiki/List_of_knapsack_problems
0504デフォルトの名無しさん
2009/10/05(月) 12:59:29アルゴリズムが載ってるね
0505デフォルトの名無しさん
2009/10/05(月) 17:30:11英語のwikipediaを翻訳すれば良いじゃない?と思ったこともありました。
0506デフォルトの名無しさん
2009/10/06(火) 02:30:52とよく思う。
0507デフォルトの名無しさん
2009/10/06(火) 06:47:04multi knapsack でgoogleとかgoogle scholarとかで調べれば山ほど出てくるでしょ
0508デフォルトの名無しさん
2009/10/07(水) 01:48:54スプライン補間の代表的な応用はベジエ曲線なんでしょうか?
若しくは逆に、ベジエ曲線の数式化がスプライン補間であったってことでしょうか?
0509デフォルトの名無しさん
2009/10/07(水) 02:44:35param boxes,integer, >= 1;
param balls, integer, >= 1;
param box{1..boxes}, integer, > 0;
param weight{1..balls}, integer, > 0;
param ball{1..balls}, integer, > 0;
var x{1..boxes, 1..balls}, integer;
minimize obj: sum{i in 1..boxes, j in 1..balls} (box[i] - x[i, j] * weight[j]);
s.t. f1{j in 1..balls}: sum{i in 1..boxes} (x[i, j]) <= ball[j];
s.t. f2{j in 1..balls, i in 1..boxes}: 0 <= x[i, j];
s.t. f3{i in 1..boxes}: sum{j in 1..balls} (x[i, j] * weight[j]) <= box[i];
solve;
for {i in 1..boxes} {
printf "%d = ", box[i];
for {j in 1..balls} {
printf "(%d) x %d, ", weight[j], x[i, j];
}
printf "\n";
}
data;
param boxes := 4;
param balls := 3;
param box := 1 11, 2 13, 3 15, 4 17;
param weight := 1 3, 2 5, 3 7;
param ball := 1 7, 2 6, 3 10;
end;
0510デフォルトの名無しさん
2009/10/07(水) 02:47:25前から興味があった GNU MathProg でやってみた。容量
11, 13, 15, 17 の箱に重さ 3, 5, 7 のボールそれぞれ
7, 6, 10 個用意して詰め込んだ例。
11 = (3) x 2, (5) x 1, (7) x 0,
13 = (3) x 1, (5) x 2, (7) x 0,
15 = (3) x 1, (5) x 1, (7) x 1,
17 = (3) x 0, (5) x 2, (7) x 1,
みたいに出てくる。
0511デフォルトの名無しさん
2009/10/07(水) 02:57:4815 = (3) x 3, (5) x 1, (7) x 0,
になる。
0512デフォルトの名無しさん
2009/10/07(水) 03:08:4811 = (3) x 2, (5) x 1, (7) x 0,
13 = (3) x 2, (5) x 0, (7) x 1,
15 = (3) x 0, (5) x 3, (7) x 0,
17 = (3) x 1, (5) x 0, (7) x 2,
0513デフォルトの名無しさん
2009/10/07(水) 08:56:24「スプライン(補間)」というのは一般的な語。
「ベジェ」「Bスプライン」というのは特定の曲線を指す。
0514デフォルトの名無しさん
2009/10/08(木) 06:09:05確かにそうですね。wiki(英語も)では二項定理の式ばかりだったので勘違いしてましたが、
奥村先生の本だとスプライン補間の実際の方法いくつか紹介されてましたが、二項定理の式を使ったその曲線はスプライン補間といわれる補間の一つなんでしょうか。
ベジエ曲線は端点を何を根拠につなげてるんでしょうか。
0515デフォルトの名無しさん
2009/10/13(火) 01:49:32テキサスホールデムの勝率を一瞬で出すWebサービスがあってびっくりしたんだけど、
(http://www.cardplayer.com/poker-tools/odds-calculator/texas-holdem)
最初はデータベースに情報があって読みだしているのかと思ったが、
10人まで対応なら現実的な量に収まらないだろうし。
テキサスホールデムというのは、各プレイヤーに2枚ずつ配られて、
中央に5枚配られ、その7枚から最高の役を作った人が勝つゲーム。
中央のカードは最初3枚、それから1枚ずつ配られるので
最初の3枚、次の4枚の時点で勝率が計算できる。
0516デフォルトの名無しさん
2009/10/13(火) 01:59:11中央のカードが配られない時点での勝率も計算できるね
前通りの組み合わせを試して計算するのにそんなに時間がかかるかな?
1 vs 1だとすると、残りのカードは52 - 4 = 48枚だから、
48 * 47 * 46 * 45 * 44通り、205476480通り試せばいいわけだよね。
そんなに大変じゃない印象があるけど…
0517デフォルトの名無しさん
2009/10/14(水) 11:25:51素直な実装でやってみたらかなり大変だった
さらに、最終的な7枚のうちから5枚を選択して最強のカードを選択するから
205476480 * 21通り、4,315,006,080回判定をしなくてはいけない。
上のWebサービスでは何かしらのテーブルか何かを持ってるんじゃないかな
0518デフォルトの名無しさん
2009/10/14(水) 12:20:500519デフォルトの名無しさん
2009/10/15(木) 10:38:42オッズ計算アルゴリズムで特許が取られてる.
大雑把には,重み付け探索の仲間みたいなことをするらしい.
0520デフォルトの名無しさん
2009/10/17(土) 04:45:50を読んでいたら、リストに格納されたn個の要素からk番目に小さな要素を
見つけるナイーブなアルゴリズムとして以下が紹介されていました
(時間計算量はO(kn))。
function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
for j from i+1 to n
if list[j] < minValue
minIndex = j
minValue = list[j]
swap list[i] and list[minIndex]
return list[k]
要はリストの先頭からk番目までに最小の要素からk番目に小さな
要素までを昇順に格納した後に、k番目のセルの中身を「求める
ものですよ」とreturnするアルゴリズムなわけですが、このアル
ゴリズムの利点として以下のようなことが書かれていました。
0521デフォルトの名無しさん
2009/10/17(土) 04:47:08<利点>
j番目に小さな要素の位置づけが終わった後では、k番目に
小さな要素を見つける時間計算量はO(j + (k-j)^2)、
もしくはO(k)(k<=jの場合)となる。
After locating the jth smallest element, it requires
only O(j + (k-j)^2) time to find the kth smallest element,
or only O(k) for k <= j.
--------
k<=jのときO(k)となるのは、k番目のセルまでリンクをたどる
コストだと納得できますが、 k>jのときどうしてO(j + (k-j)^2)
となるのかが分かりません。j+(k-j)^2のうち前半のjはj番目の
セルまでリンクをたどるコストだと思いますが、後半は上のアルゴ
リズムを「(n-j)個の要素から(k-j)番目に大きな要素を見つける」
として適用するのであれば(k-j)(n-j)となるのではないでしょうか。
何卒御教示をお願いいたします。
0522なんじゃこりゃ
2009/10/17(土) 20:50:180523デフォルトの名無しさん
2009/10/18(日) 00:24:20レスありがとうございます。
擬似コードを素直に読めばlist[]は配列ですが、j(>k)番目
に小さな要素が求まった後にk番目に小さな要素を求める
計算量がO(1)でなくO(k)なのと、名前が(A[]とかでなくわざ
わざ)list[]なので、線形リストなのかなあと思った次第です。
listが配列として、上の利点云々の記述はどういうことなの
でしょうか?
何卒御教示をお願いいたします。
0524!522
2009/10/20(火) 10:36:47二番目の "ランダムアクセスを要求しないこと" とゴッチャになってるし、その一文は無視したらいい。
言いたいことは冒頭の "k が小さければ速い" にほぼ含まれてるし。
0525デフォルトの名無しさん
2009/10/20(火) 10:46:150526521
2009/10/23(金) 15:19:52大変遅くなってしまいましたが、レスありがとうございます。
Wikiの記述が間違いということですか。
>二番目の "ランダムアクセスを要求しないこと" とゴッチャになってるし、
二つ目の利点
It can be done with linked list data structures,
whereas the one based on partition requires random access.
とゴッチャになっているとはどういうことでしょうか?
>言いたいことは冒頭の "k が小さければ速い" にほぼ含まれてるし。
これはどういうことでしょうか?
自分は「他の問合せの結果が利用できる」ということ
だと思ったのですが。
御教示どうぞよろしくお願いいたします。
0527デフォルトの名無しさん
2009/10/24(土) 12:35:12> とゴッチャになっているとはどういうことでしょうか?
それまでに連結リストをたどる話は全く出ていないのに、ソート済みの部分を飛ばすコストに
連結リストをたどるコストが計上されている。
他にもその一文には問題があって俺の SF 魂を揺さぶるが、そんなことに付き合う必要は無く
無視すべき。
> 自分は「他の問合せの結果が利用できる」ということ
他の方法でソートしても同じ利点は得られる。
あの文で指摘されているのは k (その時には n もだが)が小さくなる場合があるということで、
レアケースだし無理に言及する必要は無いのではないか。
概要に選択ソートを途中まで行ったものだと書いてあるのだから、混乱を引き起こす文章を
追加するよりは、自明とするのが良いと思う。
0528521
2009/10/24(土) 14:37:08御教示ありがとうございます。
>ソート済みの部分を飛ばすコストに連結リストをたどる
>コストが計上されている。
O(1)ではなくO(k)となっている箇所ですね。自分もそこで
「あ、連結リストの話なのか」と思いました。
>あの文で指摘されているのは k (その時には n もだが)が
>小さくなる場合があるということで
j番目までのソートが終わっているのであれば、(k,n)では
なく(k-j, n-j)で計算できるということですね。
ともあれO(j + (k-j)^2)は間違いということで、ご説明
どうもありがとうございました。
0529デフォルトの名無しさん
2009/10/27(火) 00:54:49ってどんな同期アルゴリズムなんでしょうか?
0530デフォルトの名無しさん
2009/10/27(火) 14:56:51Proceedings of Crypto ’87, pp. 369–378.
この原論文が参考になります.たぶん
0531デフォルトの名無しさん
2009/10/27(火) 22:42:42ソートアルゴリズムだの、データ型だの一連のものは読んだ
でも、データ型で配列だのハッシュだの、ツリーだの
そんなもんはプログラムする上で使うし
ソートアルゴリズムで、バブルソートだのクイックソートだのできるようになった
でもこれって、ただのFor文の組み合わせだよね。
極論言えば、1〜10まで足しこむのもアルゴリズムじゃね?
こんなのやっても、俺が求める
数式をプログラムに落とし込む能力なんかつかねぇし
スマートな実装方法なんてものの応えも出てこない。
結局、何かしたいときに
そのフロー図書いて落とし込むこと=アルゴリズムでいいの?
誰か教えて。
つか、数式をスマートにプログラムに落としこむのに良い本とか教えて
0532デフォルトの名無しさん
2009/10/28(水) 07:17:46アルゴリズムってのは問題に対する解決手続きのこと.
何か問題があったときに,どんなデータ型を使って
どんな For や If を組み合わせたら問題が解けるか,
というのがアルゴリズム.
当然1〜10の和を求める手続きもアルゴリズム.
数式をプログラムに落とし込むのは実装技術で,
アルゴリズムとは普通は呼ばない.
実装に関する良い本は見たことが無いなあ.
経験積むしか無いんじゃね.
0533デフォルトの名無しさん
2009/10/28(水) 07:33:46そもそもお前は求めている物が何なのか分かってないだろ
数式が何を指すのか、そして最終的に何が得られれば良いのか説明してみろよ
0534デフォルトの名無しさん
2009/10/28(水) 07:41:020535デフォルトの名無しさん
2009/10/28(水) 11:12:55確か岩波のは、コンピュータサイエンス的にマニアックな説明だったはず。
0536デフォルトの名無しさん
2009/10/28(水) 12:30:42> 極論言えば、1〜10まで足しこむのもアルゴリズム
それを for を使わず 10*(10+1)/2 で求めるのもアルゴリズム
0537デフォルトの名無しさん
2009/10/28(水) 12:37:41Programming Pearls
Introduction to Algorithms
Algorithm Design
The Art of Computer Programming
この辺が鉄板
あとはDomain Theoryなり、Squiggolなり関数型言語寄りの世界に入ればいいと思う
0538デフォルトの名無しさん
2009/10/28(水) 12:37:410539デフォルトの名無しさん
2009/10/28(水) 12:38:230540デフォルトの名無しさん
2009/10/28(水) 22:09:02Cの実装を見てみたいのですが知りませんか?
0541デフォルトの名無しさん
2009/10/29(木) 12:18:32まぁ頑張って探してくれ。
0542デフォルトの名無しさん
2009/10/29(木) 12:31:250544デフォルトの名無しさん
2009/10/31(土) 01:25:32◆1〜n までの乱数を発生 (a とする)
◆a 番目の要素と (n - a + 1) 番目の要素を交換
● ◆ を n 回以上(充分シャッフルされるまで)繰り返す
●1 番目から n 番目まで順番に取り出す
0545デフォルトの名無しさん
2009/10/31(土) 01:41:040546デフォルトの名無しさん
2009/10/31(土) 02:05:280547デフォルトの名無しさん
2009/10/31(土) 02:17:16{
a = rand(N - i);
SWAP(array[i], array[i + a]);
}
0548デフォルトの名無しさん
2009/10/31(土) 02:32:070549デフォルトの名無しさん
2009/10/31(土) 05:22:51各言語に実装されたRAND系を使用する場合は、
十分多い集合からそれよりも大分少ないn個をランダムに選択。重複したらやり直す
で殆ど重複せずに取れちゃうよな
indexをランダムに選ぶ様な場合は、
nが比較的少ないならn個の配列作ってしまうのが一番楽だろうな
0550デフォルトの名無しさん
2009/10/31(土) 08:51:10547が正解
0551デフォルトの名無しさん
2009/10/31(土) 09:20:400552デフォルトの名無しさん
2009/10/31(土) 10:13:410553デフォルトの名無しさん
2009/10/31(土) 10:41:29>>549 Windows環境だと RAND_MAX=2^16 しかなかった気がする
0554デフォルトの名無しさん
2009/10/31(土) 11:07:58浮動小数点で 0 ≦ r < 1 な r を返すタイプの rand を使えばいいだろうよ
0555デフォルトの名無しさん
2009/10/31(土) 12:53:20表現できる数の集合が有限である限り重複しうる。
0556デフォルトの名無しさん
2009/10/31(土) 13:01:380557デフォルトの名無しさん
2009/10/31(土) 13:44:15>>547 = Fisher yates
というんだってな。
0558デフォルトの名無しさん
2009/10/31(土) 13:47:24俺が再発明したアルゴリズムに名前が付いてたのか
0559デフォルトの名無しさん
2009/10/31(土) 14:07:500560デフォルトの名無しさん
2009/10/31(土) 18:39:13メモリに制限のあるオーディオプレーヤーでシャッフルに苦情が出てさ
0561デフォルトの名無しさん
2009/10/31(土) 19:08:29全単射な関数を発見しておくとかならいけるだろうが。
f ( n番目、 総数N、 乱数r)で、一対一対応のある関数。
0562デフォルトの名無しさん
2009/10/31(土) 19:12:04関数 f(n)がランダムに近い出力だすのも困難だろ。
ランダム、一対一の構築は面倒。運任せに近いと思う。
0563デフォルトの名無しさん
2009/10/31(土) 19:17:01ある程度のランダムは確保できると思う。
0564デフォルトの名無しさん
2009/10/31(土) 19:20:190565デフォルトの名無しさん
2009/10/31(土) 20:19:16あとは、ビットカウントの少なそうなところから埋めていくか
0566デフォルトの名無しさん
2009/10/31(土) 20:24:310567デフォルトの名無しさん
2009/11/03(火) 10:54:48ttp://www.mint.go.jp/coin/coin_topics/pdf/20091008.pdf
当選番号から当落分かるわけでなし何の意味もないが一覧出力させてみたんだが、書いてあるそのまましか思いつかん
最適化した実装キボン
0568デフォルトの名無しさん
2009/11/03(火) 11:03:56ていうか最適化とかするまでもない手順のような気がするが。
0569デフォルトの名無しさん
2009/11/03(火) 14:07:430570デフォルトの名無しさん
2009/11/03(火) 19:18:330571デフォルトの名無しさん
2009/11/04(水) 10:25:160572デフォルトの名無しさん
2009/11/12(木) 16:30:260573デフォルトの名無しさん
2009/11/12(木) 17:26:30PHP以外でバブルソートを書くが如くに書けばいいでしょう。
0574デフォルトの名無しさん
2009/11/25(水) 20:53:23入力としてNxN のbool型2次元配列が与えられる。
この配列は読み書き可能である。
この配列の内容を次のように書き換えて返したい。
1.入力時にtrueだったセルはtrueのまま。
2.入力時にfalseで上下左右いづれかのセルが入力時にtrueなセルはtrueに書き換える。
3.入力時にfalseで上下左右いづれのセルも入力時にfalseなセルはfalseのまま。
このアルゴリズムをメモリ使用量O(1)で実装できるか。
0575デフォルトの名無しさん
2009/11/25(水) 21:04:170576574
2009/11/25(水) 21:07:07一応、囲碁プログラムの一部です。
0577デフォルトの名無しさん
2009/11/25(水) 23:10:430578デフォルトの名無しさん
2009/11/25(水) 23:36:480579デフォルトの名無しさん
2009/11/25(水) 23:57:140580デフォルトの名無しさん
2009/11/25(水) 23:59:17でもメモリ使用量O(1)?
0581デフォルトの名無しさん
2009/11/26(木) 00:01:01そのへんに転がってるプログラムいくつか読んでみろ。
0582デフォルトの名無しさん
2009/11/26(木) 03:30:480583574
2009/11/26(木) 08:12:45もし厳密な証明をしてくれる人がいたら、問題設定がメモリO(1)でできるか?だとちょっとまずそうなので
メモリO(logN)でできるか?に変更させてください。
0584デフォルトの名無しさん
2009/11/26(木) 08:32:320585582 ◆lAx7GGWbgo
2009/11/26(木) 09:01:30にしてもここIDないんだなあ
0586デフォルトの名無しさん
2009/11/26(木) 10:20:18それともなにか,碁盤のサイズはbool型の遷移処理中に大きくなったりチッちゃくなったりするのか?
フヒヒ
0587デフォルトの名無しさん
2009/11/26(木) 11:27:26頼むからオーダーの概念を理解してくれ
585の言う「変数」はプログラム中の変数ではなく
オーダーO(f(N))を決める変数Nという意味だと分かってやれ
0588デフォルトの名無しさん
2009/11/26(木) 11:32:44囲碁プログラムという前提がある以上、Nは定数なんだよ。
よしんばNそのものが定数でなくとも、max(N)は定数で押さえられる。
諸般の事情から、最大でも52かそこらだろうからな。
したがってN*Nも定数で押さえられるので、O(1)なんだよ。
0589デフォルトの名無しさん
2009/11/26(木) 11:37:110590デフォルトの名無しさん
2009/11/26(木) 11:38:330591デフォルトの名無しさん
2009/11/26(木) 11:43:19頼むからオーダーの概念を理解してくれ
585の言う「変数」はプログラム中の変数ではなく
オーダーO(f(N))を決める変数Nという意味だと分かってやれ
0592デフォルトの名無しさん
2009/11/26(木) 11:50:36> オーダーO(f(N))を決める変数Nという意味だと分かってやれ
まあアルゴリズム上,入力はNじゃなくて "NxN のbool型2次元配列" 一つだよなってことなんだけど,分かってやれ
0593デフォルトの名無しさん
2009/11/26(木) 11:56:33// メモリオーダーは定数の例1
int reverse_short_endian(int x) {
int low, high, temp;
low = x & 0x00FFU;
high = x & 0xFF00U >> 16;
temp = low << 16 | high;
return temp;
}
// メモリオーダーは定数の例2
int hogehoge(int[][] goban) {
int[][] goban_temp = <copy of goban>;
...
return temp;
}
こういうことじゃないの?
0594デフォルトの名無しさん
2009/11/26(木) 11:59:460595デフォルトの名無しさん
2009/11/26(木) 12:08:26「t=O(1)」は、Nによらない定数cが存在してNが十分大きいときに「|t|≦c」であるという意味で
tが一定という意味ではない
あと Nを変えないのなら(実際に使うときは定数だったとしても)、オーダーを議論する意味はない
0596デフォルトの名無しさん
2009/11/26(木) 12:31:39要はこの場合のメモリオーダーは碁盤の目数ではなく碁盤の個数に寄るってこと
碁盤の個数はアルゴリズム上一つだろ
0597デフォルトの名無しさん
2009/11/26(木) 12:39:36画像処理の膨張・収縮処理と同じアルゴリズムなので、その辺を調べてみるといいかも。
0598デフォルトの名無しさん
2009/11/26(木) 12:47:440599デフォルトの名無しさん
2009/11/26(木) 16:26:590600デフォルトの名無しさん
2009/11/26(木) 16:28:000601デフォルトの名無しさん
2009/12/15(火) 01:45:46B木
トライ
パトリシア
言語はJavaかCで上記の記述が
実装面で強い書籍ってどれでしょうか?
0602デフォルトの名無しさん
2009/12/15(火) 04:55:250603デフォルトの名無しさん
2009/12/15(火) 13:38:520604デフォルトの名無しさん
2009/12/26(土) 20:23:20って思ってたけど、 f(x, n) = x の n 乗 (n は整数, x は数値ならなんでも) を求めるアルゴリズムで実験したら O(n) も遅いんだなって思った。
(-1)^k を 39999988 ≤ k ≤ 40000012 の範囲で連続して計算すると、
O(n) のアルゴリズムでは 1000000000 回、
O(log(n)) のアルゴリズムでは 948 回掛け算する。
計算にかかった時間は、
O(n) のアルゴリズムでは 547 ms、
O(log(n)) のアルゴリズムでは 0.000 ms だった。
0605デフォルトの名無しさん
2009/12/26(土) 20:25:08× 0.000 ms
○ 0 ms
0606デフォルトの名無しさん
2009/12/26(土) 23:27:50検索の最も簡単、というか何も考えないアルゴリズムがリニアサーチ=O(n)だからね。
個人的にはO(log(n))で十分かと
0607デフォルトの名無しさん
2009/12/27(日) 08:59:230608デフォルトの名無しさん
2009/12/29(火) 14:09:11何がいいですか?
0609デフォルトの名無しさん
2009/12/29(火) 14:42:16£とか
0610デフォルトの名無しさん
2009/12/29(火) 15:07:020611デフォルトの名無しさん
2010/01/07(木) 13:30:28999→1000 なら真
10000→9000 なら真
みたいな。。。
0612デフォルトの名無しさん
2010/01/07(木) 13:52:21$b = 1000;
$c = $a / $b;
if($c != 1) echo "桁が変わってます";
適当書いたけど言いたいことは伝わると思うのであとは改良してください
0613デフォルトの名無しさん
2010/01/07(木) 13:55:550614デフォルトの名無しさん
2010/01/07(木) 14:13:540615デフォルトの名無しさん
2010/01/07(木) 14:30:280617デフォルトの名無しさん
2010/01/07(木) 16:01:02ていうか桁数を問題にしてるんだから log 使おうよ。
0618デフォルトの名無しさん
2010/01/07(木) 18:29:54log(x) … x の対数を返す (底はなんでもいい)
floor(x) … x 以下の最大の整数を返す (C 言語とかでは明示的型変換とか)
-------始め-------
数値 x, beforeFigure, nowFigure;
x = 数値処理;
beforeFigure = floor( log( abs( x ) ) / log( 基数 ) );
ループ {
x = 数値処理;
nowFigure = floor( log( abs( x ) ) / log( 基数 ) );
if( nowFigure == beforeFigure ){
桁数変化なし;
} else {
桁数変わった;
}
beforeFigure = nowFigure;
}
-------終わり-------
アルゴリズムなのかにゃ? これ
0619デフォルトの名無しさん
2010/01/07(木) 18:38:25x == 0 のとき死ぬなorz
桁数 = floor( log( abs( x ) ) / log( 基数 ) );
となっているところを
if( x == 0 ) {
桁数 = 任意定数;
} else {
桁数 = floor( log( abs( x ) ) / log( 基数 ) );
}
って感じにせなアカン。
0620デフォルトの名無しさん
2010/01/12(火) 20:04:14http://tsushima.2ch.net/test/read.cgi/newsplus/1263289353/
仏の技術者が27万円のPCで131日かけ破る★4
0621デフォルトの名無しさん
2010/01/13(水) 00:26:45擬似乱数を使って、ランダムで一様な方向を発生させたかったのだが。
rand()を0以上1未満の浮動小数点の乱数を返す関数として。
2次元の場合は、rand()*2*piでいい。
3次元の場合、rand()*2*piで経度を、rand()*piで緯度を発生させてみたのだが、それだと一様にならない
(北極/南極あたりは緯線と経線の密度が高くなる)
時間がなかったので、その時は、
while(1){
単位立方体内に一様にランダムな1点を取る
if(取った点が単位球内に含まれている) break;
}
逆三角関数で、とった点の角度を求める
のようにしたのだが、あんまりエレガントじゃない。
もっとエレガントな方法は、なかったのだろうか。
0622デフォルトの名無しさん
2010/01/13(水) 01:07:33単に時間かけてのゴリ押しじゃんね
単位時間あたりの桁数算出ではスパコンが2ケタ弱違いに上
0623デフォルトの名無しさん
2010/01/13(水) 01:11:073次元ぐらいなら、もっと良い方法がありそうです
個人的には621も十分賢い方法だと思います
次元数が大きいと外れ確率が増えますが
0624デフォルトの名無しさん
2010/01/13(水) 01:13:09z=rand()*2-1;
x=sqrt(1-z*z)*sin(t);
y=sqrt(1-z*z)*cos(t);
0625デフォルトの名無しさん
2010/01/13(水) 01:16:52zが偏ってる気がする
0626デフォルトの名無しさん
2010/01/13(水) 02:04:32極座標(1,θ,φ)から変換してみたが
0627デフォルトの名無しさん
2010/01/13(水) 02:11:49http://docs.google.com/viewer?a=v&q=cache:1h4SSW-GcA8J:apollon.cc.u-tokyo.ac.jp/~watanabe/pdf/prob.pdf
0628625
2010/01/13(水) 02:20:31個人的に意外だった……
0629デフォルトの名無しさん
2010/01/18(月) 07:01:28とある(任意の)通貨体系、例えば361、147、75、1円玉なんていう無茶な通貨だとして、
お釣りの値を入力したら最小の枚数で切り抜けるCプログラミングを考えます。
この場合例えばお釣りが150円だったら、147×1、1×3で計4枚でなく、75×2で計2枚となるのが正解です。
通貨体系もお釣りも任意に与えられるので、それぞれがどんな値であっても最小の枚数を出すプログラムなんですが、これを考えるとき、どんなアルゴリズムが考えられますか?
すみませんが、言葉でわかりやすく答えて頂けると助かりますm(_ _)m
0630デフォルトの名無しさん
2010/01/18(月) 07:38:19今ぱっと思いついたのは次の2通りのやり方。
1) ちょうどお釣り x になる通貨の組み合わせを全てリストアップし、
そのリストを昇順にソートした場合の先頭要素を答えとする。
リストアップしさえすれば後は簡単だろう。
これは両替アルゴリズムで検索すればすぐに分かると思う。
再帰を使用する。
2) 通貨 n 枚でちょうどお釣り x になる組み合わせを探す。
見つからなければ n を 1 つ増やして再チャレンジ。
たぶん、額面が大きい硬貨から試した方が効率が良さそうだ。
0631デフォルトの名無しさん
2010/01/18(月) 07:59:38なるほど!わかりやすいですね。
素早い回答助かりました。
ありがとうございます!
0632デフォルトの名無しさん
2010/01/18(月) 08:49:24http://codepad.org/rWZe0plv
0633デフォルトの名無しさん
2010/01/18(月) 18:34:36半端じゃないから要素数が1万を越えると
利用に適さないよね?
0634デフォルトの名無しさん
2010/01/18(月) 19:09:18追加の頻度が大きければ問題
それが要素数に比例するならともかく
0635デフォルトの名無しさん
2010/01/18(月) 19:14:49木構造は使えないと
何を使えばいいのだろうか
0636デフォルトの名無しさん
2010/01/18(月) 19:26:03ある程度の量が溜まってきたらAVL木にどばっと入れる、じゃダメ?
0637デフォルトの名無しさん
2010/01/18(月) 19:52:290638デフォルトの名無しさん
2010/01/18(月) 20:09:47それはAVLとは言わないのでダメです
0639デフォルトの名無しさん
2010/01/18(月) 20:42:080640デフォルトの名無しさん
2010/01/18(月) 22:18:13>630 の 1 で全部組み合わせをリストアップするんじゃなくて探索しながら枝刈りとか。
(途中で 3 枚の答えがあるなら 4 枚以上に成るケースは気にしなくてOKなので処理を省ける)
後は動的計画法使うのもあり。
coin[i], count[i] をそれぞれ i 円の時に使うコイン(最初の1枚)と全体の枚数とする。
i 円に対して 361 を使う場合だったら count[i-361]+1 枚になるし、147 円を使う場合なら count[i-147]+1 枚になる。
以下同文で他のコインに対しても処理して coin[i] = 一番枚数が少ないコイン, count[i] = その時の枚数 にする。
(当然 i-x がマイナスになるケースとかは無視する)。
これを i = 1 から目的の数(例題なら 150)までループすればOK。
最終的な解答は coin[i] から逆算していく。
http://codepad.org/Ypjc06tG
>632
バグってね?
http://codepad.org/uF9MfKrI
http://codepad.org/gM5Gh97l
0641デフォルトの名無しさん
2010/01/18(月) 22:24:03>>630 のやり方だとちょっと金額が多くなると計算が終わらなくなる
実行時間効率から考えれば金額に対するDPがいいだろう
table[金額] = 必要な最低枚数 になるように table[0] から1円ずつ順番にテーブルを構築する
どの硬貨を使うか知りたければテーブル更新時に
「その金額に到達するために最後に使った硬貨の種類」を覚えておくテーブルも一緒に作ればよい
>>633
要素数Nの木に対して、要素の挿入・削除は最悪でも log(N) 時間しかかからないぞ?
正しく実装していれば100万要素の挿入くらいは一瞬で終わるはずだ
0642641
2010/01/18(月) 22:25:170643デフォルトの名無しさん
2010/01/18(月) 22:27:36移動して来たなら元スレにも移動しますと書いた上で、こっちにも移動して来ましたと書いてね。
0644629
2010/01/18(月) 23:03:12ありがとうございます。しっかり考えて頂いてとても参考になります。
勉強不足の僕の頭ではあとの話はまだ難しいようです。
>>643
すみません。今さらですが移動してきました。
お手数をかけました。
0645デフォルトの名無しさん
2010/01/18(月) 23:18:03「移動します」って書く理由は元スレでの無駄な(見てもらえない)回答を避けるということと、
情報がちゃんと辿れるようにする(検索で引っかかった人とか元スレで ROM ってた人とかが
辿れるようにする)という意味があると思うので、次があればどこから移動しました、どこに
移動しましたって書いてくだしあ。
0646デフォルトの名無しさん
2010/01/19(火) 03:53:11これって多項式時間で解ける問題?
NP完全だったりするのかな?
なんとなくPartitionあたりから帰着できそうな気はするけど。
0647デフォルトの名無しさん
2010/01/19(火) 09:48:260648デフォルトの名無しさん
2010/01/19(火) 23:55:08これ自身coin changing problemとかcoin exchange problemと呼ばれる
有名問題で,NP困難.いくらでも何にでも帰着で示せる.
0649デフォルトの名無しさん
2010/01/22(金) 00:54:00これって何てアルゴリズム?
0650デフォルトの名無しさん
2010/01/22(金) 01:12:110651デフォルトの名無しさん
2010/01/22(金) 02:49:53どーもです
クイックソートって言うのか
初めて知った
0652デフォルトの名無しさん
2010/01/22(金) 19:02:150653デフォルトの名無しさん
2010/01/22(金) 19:26:300654デフォルトの名無しさん
2010/01/28(木) 08:57:15PN9で生成多項式がX9+X5+1を考えたとき
レジスタの初期値が0x001だった場合、
下のexorした結果の100001000110・・・
が送信するデータになるんでしょうか?
つまり送信するデータ量だけシフトしてexorをとる必要
があるのでしょうか?
シフトレジスタ exor結果
00000|0001 → 1
10000|0000 → 0
01000|0000 → 0
00100|0000 → 0
00010|0000 → 0
00001|0000 → 1
10000|1000 → 0
01000|0100 → 0
00100|0010 → 0
00010|0001 → 1
10001|0000 → 1
11000|1000 → 0
こういう符号理論っていうのですかね?
該当スレってどこかにあったりします?
0655デフォルトの名無しさん
2010/01/28(木) 09:08:160656デフォルトの名無しさん
2010/02/02(火) 15:05:170657デフォルトの名無しさん
2010/02/06(土) 21:55:39良いサンプル教えてください。
0658デフォルトの名無しさん
2010/02/06(土) 22:18:38ランダムさはそれほど厳密でなくてもいい。
1-1000、600という数字はそのときどきで変わる。
ひたすらサイコロ転がすやり方だと、取り出す率が高くなると
けっこう遅くなってしまう。
良いやり方もしくは一般的なやり方があったら教えてください。
0659デフォルトの名無しさん
2010/02/06(土) 22:31:05for(unsigned i=0,t=0;i<c;++i){
s[i]=t+rand()*(e-s);
if(s[i]>e)s[i]-=e;
for(unsigned j=1;j<=i;++j)if(s[i]==s[j]){--i;break;}}}
0660デフォルトの名無しさん
2010/02/06(土) 22:42:26シャッフル シャッフル
0661デフォルトの名無しさん
2010/02/06(土) 22:47:270662デフォルトの名無しさん
2010/02/06(土) 22:56:50データが2個以上含まれている時に
先頭からデータを取得した場合
先頭のインデックスってどう扱えばいいのですかね?
0663658
2010/02/07(日) 01:01:11うまく書けそうです。
0664デフォルトの名無しさん
2010/02/07(日) 15:20:450665デフォルトの名無しさん
2010/02/08(月) 15:41:500666デフォルトの名無しさん
2010/02/08(月) 17:51:210667デフォルトの名無しさん
2010/02/08(月) 18:32:14deque(Double Ended Queue)ではなく
dequeue(キューからの要素取得)の事でいいのか?
どちらにしても質問の意味がよくわからん。
「先頭のインデックス」とは何の事だ?
それは「先頭からデータを取得した場合」の「先頭」と同じものを指してる?
0668デフォルトの名無しさん
2010/02/09(火) 13:36:51例えば3x3マスなら↓のように埋めていきます
123
649
578
・周囲の黒マスの数が7だったら最優先でそこに進む
・白マスが分断するところには進まない
というルールを作ることで10x10ぐらいなら数回試行すれば成功するようになったのですが
もっと大きいサイズだとなかなか成功しないのです
ランダム移動の奇抜さをなるべく残しつつ、一筆書きの成功率を上げるにはどんなルールを追加したらいいでしょうか?
目標は60x60の一筆書きを自動で完成させることです
0669デフォルトの名無しさん
2010/02/09(火) 14:24:57a-b-c
|X|X|
d-e-f
|X|X|
g-h-i
0670デフォルトの名無しさん
2010/02/09(火) 16:44:470671デフォルトの名無しさん
2010/02/09(火) 18:14:14その奇抜さとは何かをとりあえずでも定義してくれないと、
あなた以外にルールを作りようもないと思うんだが。
0672デフォルトの名無しさん
2010/02/09(火) 18:40:40「壁沿いに螺旋状に移動する」みたいに明らかにランダム性を損なうものでなければ何でもいいですよ
何が奇抜さを潰してしまうかは実装してみないとわかりませんから
ワーンスドロフの「次の移動先が少ないものを選択する」というのは参考になりました
0673デフォルトの名無しさん
2010/02/09(火) 19:18:19すまん、俺が悪かった、無視してくれ。
0674デフォルトの名無しさん
2010/02/10(水) 17:28:320675デフォルトの名無しさん
2010/02/10(水) 20:27:450676デフォルトの名無しさん
2010/02/11(木) 01:25:29どんなアルゴリズムなのですか?
調べても全然でてこない
0677デフォルトの名無しさん
2010/02/11(木) 01:44:200678デフォルトの名無しさん
2010/02/11(木) 02:00:41具体的なサンプルって知りませんか?
0679デフォルトの名無しさん
2010/02/11(木) 02:24:44http://www9.atwiki.jp/othello/pages/48.html
w = white & 0x7e7e7e7e7e7e7e7e;
t = w & (black << 1);
t |= w & (t << 1);
t |= w & (t << 1);
t |= w & (t << 1);
t |= w & (t << 1);
t |= w & (t << 1);
blank = ~(black | white); // 空白の箇所
mobility = blank & (t << 1);
0680デフォルトの名無しさん
2010/02/11(木) 23:26:55アルゴリズムってありますか?
正規表現以外で
0681デフォルトの名無しさん
2010/02/11(木) 23:35:27あります。
次の方どうぞ
0682デフォルトの名無しさん
2010/02/11(木) 23:36:29あのー教えてください
困ってるんですよ
お願いしますよ
0683デフォルトの名無しさん
2010/02/11(木) 23:46:520684デフォルトの名無しさん
2010/02/12(金) 02:37:07次のかたどうぞ
0685デフォルトの名無しさん
2010/02/12(金) 03:07:18次の方どうぞ
0686デフォルトの名無しさん
2010/02/13(土) 22:13:570687デフォルトの名無しさん
2010/02/18(木) 21:58:380688デフォルトの名無しさん
2010/02/21(日) 01:02:00質問への答えとしてはズレているが、バックトラックって手もある。
0689デフォルトの名無しさん
2010/02/21(日) 19:55:340690デフォルトの名無しさん
2010/03/03(水) 16:23:27例えばデータが17521〜18759の範囲の場合
下限を17000、上限を19000ぐらいにみたいなデータ幅よりある程度広い
なるべく切の良い数値を求めるロジック見たいなものはないですか?
参考になりそうなヒントでもいいです。
0691デフォルトの名無しさん
2010/03/03(水) 16:29:040692デフォルトの名無しさん
2010/03/03(水) 17:08:03何で割るかを悩んでるんです。。。
0693デフォルトの名無しさん
2010/03/03(水) 17:28:400694デフォルトの名無しさん
2010/03/03(水) 18:15:50これを適当な幅(これはロジックも糞もないな)で分割して
先頭の値を >>691 の方法で決める
0695デフォルトの名無しさん
2010/03/03(水) 18:16:520696690
2010/03/03(水) 19:21:36range取ってその1割を上限下限に足して
rangeの桁数を割る数に
もっとシンプルにならないんだろうか。。。
0697デフォルトの名無しさん
2010/03/03(水) 19:40:500698デフォルトの名無しさん
2010/03/03(水) 19:54:1268円の買い物をして
100円支払い、32円お釣りを受け取るのではなく1 5
123円支払い、55円お釣りを受け取るのは何というアルゴリズムになりますか?
わたしは実生活では上記のような支払い方をしていて、
目的は財布を軽くすることです
他にも支払いで使う硬貨の種類選択基準にどのようなものがあるか教えて下さい
よろしくお願いします
0699デフォルトの名無しさん
2010/03/03(水) 21:08:27↓随分まえに書き込んだネタ
28 デフォルトの名無しさん 2007/04/13(金) 16:00:45
>>25
ずいぶん昔にやったな、オートスケール。
最小値と最大値の差を有効数字2桁にして、その2桁を元に
目盛りの分割数を 5, 7, 10, 12, 15 から選んで、みたいなことを
してたような…
0700デフォルトの名無しさん
2010/03/04(木) 11:36:57財布の中身を全部出せば、財布に戻る硬貨枚数が最小になる
持ち金200円で105円の買い物をすれば残金は95円だろ
持ち金が100円2枚だろうが1円200枚だろうがとにかく全部レジに出してしまえば「95円」返ってくる
この「95円」をレジの人が最小枚数で渡してくれれば財布内の小銭枚数も最小になるってわけだ
0701デフォルトの名無しさん
2010/03/04(木) 12:31:450702デフォルトの名無しさん
2010/03/04(木) 13:23:560703デフォルトの名無しさん
2010/03/04(木) 16:22:30log10(x)とか使わねーw
log(x)の方が安定しそうw
0704デフォルトの名無しさん
2010/03/04(木) 17:15:25安定は…よくわからん
0705デフォルトの名無しさん
2010/03/04(木) 18:05:38>何というアルゴリズムになりますか
0706デフォルトの名無しさん
2010/03/04(木) 18:11:08え?
普通手持ちが1円玉200枚だったら1円玉95枚が残るべきでしょ?
0707デフォルトの名無しさん
2010/03/04(木) 18:36:511円玉95枚は両替する
ということを彼が言いたかったのだよ。
知らんが。
0708デフォルトの名無しさん
2010/03/04(木) 21:05:22つまらない種類選択基準として「常に十分な額の通貨ひとつを払う」
というのはあるな…。財布をまさぐったり考えたりする手間を省ける。
0709デフォルトの名無しさん
2010/03/04(木) 21:12:19それは100円玉一枚とか1000円札一枚という支払い方法ですよね
これやると2万円の買い物とかできなくなりませんか?
あと1円玉とかは使われないで貯まるばっかりですよね
0710デフォルトの名無しさん
2010/03/05(金) 12:14:14持っている硬貨を全部店員に渡す
その後帰ってくるお釣りの最小枚数を求める(高い硬貨から払えば最小)
(店員はお釣りをどんな種類の硬貨でも払えるとする)
その時のお釣りのうち、最初から持っていた硬貨と同じものがあれば
最初から渡さなければいいので、
お釣りからその硬貨を引く
そうすればお釣りが最小になるコインの枚数が求まる
0711デフォルトの名無しさん
2010/03/05(金) 12:21:05どの要素がrootかはわかりません。
この時元の木構造を復元するにはどうするのが効率がよいですか?
1
2 3
4 5 6 7
ならば、与えられるデータは
1 2
1 3
2 4
2 5
3 6
3 7
ですが、与えられる順番はこの順とは限らず不定です
0712デフォルトの名無しさん
2010/03/05(金) 13:37:48復元するまでもなく、それはすでに木だよ
そのまま処理するのがいい場合もあるので
最終的に何をしたいかによるな
0713デフォルトの名無しさん
2010/03/05(金) 13:42:03データに矛盾がないなら、どこか適当なところから逆にたどって行き止まりを見つければいい
0714デフォルトの名無しさん
2010/03/05(金) 14:28:57>>712
最終的にしたいのは木の同型判定です
4
5 6
7 1 2 3
入力がこんな木なら、これはサンプルの木と同じとみなします
つまりノードの番号に意味はなくて
接続関係が同じなら同じとみなします
なのでノードの接続関係だけを記述した
木が作れれば解けるかなと思いまして
>>713
rootを見つけるだけならどの点からたどっても良いっていう
簡単な事実に気付きませんでした
なんか難しく考えてて、トポロジカルソートとかしないといけないのかと
ちょっとやってみます
0715デフォルトの名無しさん
2010/03/05(金) 17:00:57だからそれだと1円玉95枚帰ってくるべきところで50円玉と10円玉x4と5円玉になっちゃうでしょ
それが許されるなら相談するほどむずかしかない
店員に渡す枚数が最も多く
店員から返る枚数が最も少なくなる物を求めたいんでしょ
初期状態を1枚の硬貨と簡単化した時点で破綻してるよ
0716デフォルトの名無しさん
2010/03/05(金) 18:55:42理論上は1円105枚を出せばいいけど、現実にそんな出し方するのは難しいよな。
「同一硬貨はx枚までしか出せない」って制約も必要だろう。
0717デフォルトの名無しさん
2010/03/05(金) 19:01:58ttp://www.mint.go.jp/qa/coin/06.html
0718デフォルトの名無しさん
2010/03/05(金) 19:15:03店員が最小の枚数でお釣りを返すことを暗黙に仮定しているから
ミニマックスではないな
0719デフォルトの名無しさん
2010/03/05(金) 21:30:02123円を払った際、自分が100円1枚と10円2枚と1円3枚で払ったとして
店の人が1円55枚返してきたら、最初から20円は渡さないほうがいいじゃん
そこんところはなんか制約ないの?
710のアルゴリズムはこれね
ttp://www.deqnotes.net/acmicpc/p0006/
確かに最初に渡す枚数を最大にするっていう条件は考えてなかった
でもそれは支払い枚数が決まった後に
手持ちと比べて枚数が多くなるように等価交換すればいいんでないかね
0720デフォルトの名無しさん
2010/03/05(金) 22:30:28木の同型判定は良く知られたアルゴリズムがあるので
車輪を再発明する前に調べるよろし。
0721デフォルトの名無しさん
2010/03/05(金) 22:40:26715の指摘は国内模擬予選(の元問題)作問段階で話題になったところで、
支払う金額の部分金額で支払えたら駄目とか色々条件を考えたんだけど、
結局綺麗なルールにならなかったから諦めたところ。
(ルールを書きすぎるとそれを実装するだけの問題になっちゃうので)
ちなみにその解法は「全ぶちまけ」と内輪で呼んでた。
0723デフォルトの名無しさん
2010/03/06(土) 11:02:03参考になるサイトありますか?
0724デフォルトの名無しさん
2010/03/06(土) 17:01:570725デフォルトの名無しさん
2010/03/06(土) 19:14:110726デフォルトの名無しさん
2010/03/06(土) 19:15:400727デフォルトの名無しさん
2010/03/06(土) 19:50:18アルゴリスですか?
1.まずは指2本を使ってアナルを広げます…
0728デフォルトの名無しさん
2010/03/06(土) 21:10:040729デフォルトの名無しさん
2010/03/07(日) 10:29:47数学の知識があるならアルゴリズムイントロダクションか
アルゴリズムデザインを理解できるまで読むのが第一歩
あとはひたすら実戦
0730デフォルトの名無しさん
2010/03/07(日) 20:01:00数値が大きい時、途中式のpowで0が返ってきてしまいます。
boostの実装も見てみましたが、ifでの場合分けが多くてよくわからないです。
数学の関数を実装って、途中式のオーバーフロー/アンダーフローや計算速度を考えると難しすぎる・・・。
0731デフォルトの名無しさん
2010/03/07(日) 21:39:28[0,1)の一様乱数をn個作ってp未満の乱数の個数を数えればOK
下手に階乗を展開するよりも正確
0732デフォルトの名無しさん
2010/03/07(日) 22:14:05すみませんさっぱり分からないです。
具体的にnやpが何を表していて、「p未満の乱数の個数」がどういう物になるのでしょうか?
0733デフォルトの名無しさん
2010/03/07(日) 23:56:260734デフォルトの名無しさん
2010/03/08(月) 00:12:19それは何度も見てますが、>>731の話と繋がらないです。
その記事のk,n,pの内、>>731はnとpしか出てきてないし、
求める数値は0から1の値なのに、「p未満の乱数の個数」は整数に見えます。
0735デフォルトの名無しさん
2010/03/08(月) 20:32:19boost::binomial_distribution も乱数を発生させるためのライブラリだから
0736デフォルトの名無しさん
2010/03/08(月) 20:40:412項分布の確率値を求めたいだけならば logを計算してから最後にexpを取ってください
log(n!) = log 1+log 2+log 3+....+log n
log(n!/k!) =(log 1+log 2+log 3+....+log n)-(log 1+log 2+log 3+....+log k)
このように求めていけば発散しません
0737デフォルトの名無しさん
2010/03/08(月) 21:52:21boostの例はこっちのつもりでした。
ttp://www.kmonos.net/alang/boost/classes/statistical_distributions.html
>>736
なるほど、その手がありましたか。
解決しました。どうもでした。
0738737
2010/03/09(火) 00:16:32確率密度関数は作れましたが、累積分布関数が作れません。
確率密度関数の返す値が、実数だと小さすぎて0になってしまうのです。
対数のままだと累積(足し算)できないし、どうすれば・・・。
0739デフォルトの名無しさん
2010/03/09(火) 00:45:48L=max(l1,l2,...,ln) としたとき
exp(l1)+exp(l2)+...+exp(ln)=exp(L)*{exp(l1-L)+exp(l2-L)+...+exp(ln-L)}
と展開して計算するだけで精度は十分
exp(Li-L)が0になるような小さい値はほとんど寄与しないから
デカイnなら、wikipediaに書いてあるように正規分布で近似するか
変形ベッセル関数を何とかして計算するとか
数値計算は奥が深い
どんな解析式に対しても安全に計算できる方法はないから
0740デフォルトの名無しさん
2010/03/09(火) 02:06:29なるほど・・・。
決定版といえるような方法はなかなかないんですね。
難しい。
0741デフォルトの名無しさん
2010/03/11(木) 01:06:08これわかんないたすけて
0742デフォルトの名無しさん
2010/03/11(木) 01:47:460743デフォルトの名無しさん
2010/03/14(日) 19:38:16以下のような入力データの場合
A列 B列 C列
-----------------
2 き Z
1 あ C
2 か D
1 い B
2 く A
A列 B列 C列
------------------
1 あ C
1 い B
2 か D
2 き Z
2 く A
という風にA列 > B列 > C列の順に優先度をつけて
ソートしたいのですが、C言語で構造体に1行のデータ
を入れてソートしています。
しかし、A列の要素についてソート後、B列の要素に
ついてソートすると、B列が優先でソートされてしまい
A列についてソートした結果がくずれてしまいます。
どのようにソートすればよいのでしょうか?
0744デフォルトの名無しさん
2010/03/14(日) 19:46:130745デフォルトの名無しさん
2010/03/14(日) 20:00:36A列が同じならB列で比較してB列も同じならC列で比較する
0746デフォルトの名無しさん
2010/03/14(日) 20:01:58A,B,C列を同時にみながらソートしないとだめ
ソートの種類はなんでも良くて
ソートする際の比較関数がちゃんと定義出来てればうまくいく
0747デフォルトの名無しさん
2010/03/14(日) 20:46:020748デフォルトの名無しさん
2010/03/14(日) 21:04:33たくさん載ってる内容が新しめの本で良いものがあったら教えてください。
セジウィック・整列の前半にあるようなオーソドックスなのはちょっとふれているくらいでも良いです。
0749デフォルトの名無しさん
2010/03/14(日) 21:23:19普通のマージソートは、安定ソートじゃないからNG
0750デフォルトの名無しさん
2010/03/14(日) 21:56:09問題自体は、小学生プログラマーでも分かるくらい単純なんですが…
unsigned int a[0xFFFF] という配列を、一つの巨大な unsigned int型のビット列と考えて、 (0000 0000 0000 0000 .... // 2,097,120bit の unsigned int型)
この巨大なビット列同士で、高速に割り算するアルゴリズムが思いつかなくてこまってます。
unsigned int a[0xFFFF];
unsigned int b[0xFFFF];
divFFFF( a, b ); // a /= b
これを普通に手計算と同じアルゴリズムで実装すると、どんなに工夫しても core2実行で0.1秒とかなので、ちょっと遅すぎて不安になります。
これを0.0001秒くらいにするような(笑)、根本的に画期的なアルゴリズムってのはありますか?
それとも、除算はどうしても遅いものなのでしょうか?
0751デフォルトの名無しさん
2010/03/14(日) 22:21:21gmpとかの多倍長整数ライブラリでは、まずニュートン法で逆数を求めてから乗算していると聞いた。
途中に出てくる乗算はFFTを使って高速化しているらしい。
0752デフォルトの名無しさん
2010/03/15(月) 00:12:56>>744、745、746、747、749さんありがとうございます。
安定ソートであれば、そのまま列が維持されるかと勘違いしていました。
比較関数の部分で、すべての要素について考慮した比較を行えばよいのですね。
ありがとうございます。
となると、挿入ソートのようなものを例で考えると、ループの中にさらにループで要素の比較を行うといった形をとるしかないのでしょうか?
0753デフォルトの名無しさん
2010/03/15(月) 01:24:54こんな感じで、もっとエレガントな方法もあるかもしれないけど
function compareA列 foo, bar
variable result
if foo.A列 < bar.A列 then result = SMALL
elif foo.A列 > bar.A列 then result = LARGE
else /* A列が等しいとき */ result = EQUAL
return result
function compareB列 foo, bar
variable result
if foo.B列 < bar.B列 then result = SMALL
elif foo.B列 > bar.B列 then result = LARGE
else /* B列が等しいとき */ result = EQUAL
return result
function compareC列 foo, bar
variable result
if foo.C列 < bar.C列 then result = SMALL
elif foo.C列 > bar.C列 then result = LARGE
else /* C列が等しいとき */ result = EQUAL
return result
function compare foo, bar
variable result
result = compareA列 foo, bar
if result == EQUAL then
result = compareB列 foo, bar
if result == EQUAL then
result = compareC列 foo, bar
return result
0754デフォルトの名無しさん
2010/03/15(月) 01:29:14多倍長整数の演算に関してはGMPのマニュアルの最後にアルゴリズムの解説があるから
本気でやるならそこが参考になる
http://gmplib.org/manual/Algorithms.html#Algorithms
0755デフォルトの名無しさん
2010/03/15(月) 10:58:330756デフォルトの名無しさん
2010/03/15(月) 14:22:29A列の {1, 2}を {0, 1}(2bit)とみなして
B列の {あ, い, か, き, く}を {0, 1, 2, 3, 4}(3bit)とみなして
C列の {A, B, C, D, Z}を {0, 1, 2, 3, 4}(3bit)とみなすと
入力データは
2 き Z =(1<<(3+3)) + (3<<(3)) + (4)=92
1 あ C =2
2 か D =82
1 い B =9
2 く A =96
みたいにみなせる
もちろん実際の入力列に相当する変換はもっと多様なので文字コードでも
しかし>>753推す
0757デフォルトの名無しさん
2010/03/15(月) 19:34:57ありがとうございます。
>>753さんのコードをもとに、がんばってみます。
ありがとうございました。
0758デフォルトの名無しさん
2010/03/19(金) 14:19:15どうやったらいいでしょうか
0759デフォルトの名無しさん
2010/03/19(金) 14:30:190760デフォルトの名無しさん
2010/03/19(金) 14:56:29└─・後ろのデータのうちランダムなひとつと取り替える。自分自身との交換あり
0761デフォルトの名無しさん
2010/03/20(土) 00:29:17{
for (int i = 1; i < a.length; i++)
swap(a, i, (int)(Math.random() * (i+1)));
return a;
}
0762デフォルトの名無しさん
2010/03/22(月) 19:58:02今は、全サンプル点を描画しているのですが、それだと時間がかかります。
適当にサンプルを間引くべきかと思いますが、間引き方について案をください。
あるサンプルおきに描画したら、描画は早くなりましたが、間引かないときと比べ表示される波形
が大きく異なってしまいます。
0763デフォルトの名無しさん
2010/03/22(月) 20:07:260764デフォルトの名無しさん
2010/03/22(月) 20:16:24D言語を使った方がいい
0765デフォルトの名無しさん
2010/03/22(月) 20:20:42ローパスしないとエイリアスが発生するわけですよね。
うーん。じゃあまじめに全点描画するしかないのか・・・?
0766デフォルトの名無しさん
2010/03/22(月) 20:28:46サンプル数が1/2以下にならないようにするのが味噌
0767デフォルトの名無しさん
2010/03/22(月) 20:39:23イマイチどうすればいいのかわからない。。。というか全然
0768デフォルトの名無しさん
2010/03/22(月) 20:47:28いやそんな感じの発想でいい
問題は「領域幅/描画点数」について
サンプリング定理がアドバイスしているということに気づくこと
0769デフォルトの名無しさん
2010/03/22(月) 21:10:01ローカルDBとサーバDBとの同期を行いたいのですが、
同期方法に関して良い文献が見つからず悩んでいます。
一般的な同期の手法など、良い仕組みがあれば参考にしたいのですが、
参考になるサイトなど有りますでしょうか?
例えば携帯の端末など、サーバにあるデータを一度取得するけど、
各々の端末内でもDBの更新や削除などが行え、
サーバと同期することで他人の変更も差分で同期出来る方法を考えています。
そのあたりのルール決めや、差分取得の方法、衝突時の処理などです。
物によって一から考える必要はありますが、
基本的な仕組みの解説があればと思ってるのですが、
よろしくお願いします。
0770デフォルトの名無しさん
2010/03/22(月) 22:22:430771デフォルトの名無しさん
2010/03/22(月) 23:47:39うーん。わかりません。
もうっちょっと詳しくお願いします
0772デフォルトの名無しさん
2010/03/22(月) 23:51:54ちなみに現在こんな表示です。http://vippic.mine.nu/up/img/vp4187.png
上側:間引いたもの
下側:間引かない。C#のMatrixでスケーリングして描画。時間掛かる
0773デフォルトの名無しさん
2010/03/23(火) 00:51:51ちょっと本題とは外れるけど試してない気がちょっとするので
for(k=0 ; k<data_size; k++){
dot(k*graph_size_x/data_size, data[k]*graph__size_y);
}
みたいな感じなんだろうけど
for(x=0 ; x<graph_size_x; x++){
k_start = x/graph_size_x;
k_end = (x+1)/graph_size_x-1;
data_min = min(*data, k_start, k_end);
data_max = max(*data, k_start, k_end);
line(x, data_min*graph__size_y, x, data_max*graph__size_y);
}
みたいなのとの速度比較はやった?
すでにやってるならごめん
0774デフォルトの名無しさん
2010/03/23(火) 00:54:45こういう密な波形って違うアルゴリズム必要にならないのかな?
画像の一ピクセル幅に当たる時間での最大振幅を求めてその
長さの縦線を書くとか。
0776デフォルトの名無しさん
2010/03/23(火) 01:12:36で、サンプリング定理のことだけど、これを参考にするなら
間引きでも少なくとも横幅のドット数の2倍は残したほうがいいと
考えられる。
power = 2;
for(x=0 ; x<graph_size_x; x++){
data_1 = data[(x+1/4)*data_size/graph_size_x];
data_2 = data[(x+3/4)*data_size/graph_size_x];
line(x, data_1*graph__size_y, x, data_2*graph__size_y);
}
こんな感じになるんかなあ。ミスってそうだけど。
powerいじるならminとかmaxとか考えなきゃいかんから
power = int(given()); #与えられる
for(x=0 ; x<graph_size_x; x++){
k_start = (x/graph_size_x)*(1+(1/power*2));
k_end = ((x+1)/graph_size_x)*(1-(1/power*2));
k_step = (data_size/graph_size_x)/power; #ほんとはループの外で計算
mabiki(*local_data, *data, k_start, k_end, k_step); #local_dataを生成
data_min = min(*local_data);
data_max = max(*local_data);
line(x, data_min*graph__size_y, x, data_max*graph__size_y);
}
という風になるかな
さーて、きっとボロが大量にあるぞ…突っ込まれるうう
0777デフォルトの名無しさん
2010/03/23(火) 17:04:52表示エリアのドットと一対一で対応する二次元配列を作成
何も考えずにサンプリングデータから二次元配列にフラグを立てていく
何も考えずに二次元配列のフラグを参考に点を描画していく
これだけで実用レベルになる
0778デフォルトの名無しさん
2010/03/23(火) 19:56:56全然、計算量が減ってない
0779デフォルトの名無しさん
2010/03/23(火) 22:11:30そもそも遅い原因は全く他(描画)にあるはずだから、まずそこを改善しろと
どうせ同じドットに集約される所に何万回と描画してるから遅いんだと言う指摘だ
まぁスレ違いの領域だけどな
0780デフォルトの名無しさん
2010/03/24(水) 00:02:440781デフォルトの名無しさん
2010/03/24(水) 00:10:30サンプリングとか良くわかんねーけどこれでいいんじゃねーの?位の感じで言ってるのか
周波数変換について軽くググった程度の俺には分からない
俺は何れの手法にしても全点走査は必須だと思った
そして>>773と>>777は正しく、>>776は間違ってるとも思う
0782デフォルトの名無しさん
2010/03/24(水) 00:30:200783デフォルトの名無しさん
2010/03/24(水) 00:44:44点が並べば線になることから説明が必要か?
0784デフォルトの名無しさん
2010/03/24(水) 01:08:40とりあえず必要最低限の領域に分割して領域経路を探索しようとしてるんだけど
それでも8000ほどの区画に分かれてる
だいたい90x90の区画になってるわけだけど
実装はとりあえずVB.Netでやって完全に最適化された時点でC++に移植して
並列処理で更なる高速化をするつもりだけど
ただVB状態で端から端の検索に20秒くらい掛かる
これはちょっと移植しても実用レベルにはならない遅さなんだけど
90x90で20秒ってのは普通レベルなの?まだ改善の余地が十分にあると思います?
これが普通レベルなら根本的に探索アルゴリズムを考え直す必要がある
0785デフォルトの名無しさん
2010/03/24(水) 01:10:000786784
2010/03/24(水) 01:41:55他のソース参考にしてやってみたら3秒に縮んだけどこんなもんですかね?
まだ遅い気がする
0787デフォルトの名無しさん
2010/03/24(水) 01:44:39>>772の画像見て言ってんの?
標準的なPCMが1秒間に何万個の点で構成されてるかわかってんの?
実際問題50ms未満の時間をモニタいっぱいに表示して初めてドットが連続しない可能性が出始めるわけだが
拡大時の補間が考えられてないのは>>773>>776>>777全てで同じ。
話にならない馬鹿は黙るといいよ。
0788デフォルトの名無しさん
2010/03/24(水) 02:03:48k_の計算とかバグだらけで意味不明なコードだけど、無理やり解釈すると
graph_size_xが1ならdataを0%から25%間隔で75%の位置まで3箇所だけ読み取ってminmaxで線引くって事でしょ?
で、上手に間引けましたと言いたいわけだ
うん、完全に間違ってる
0789776
2010/03/24(水) 02:16:48思いっきり間違ってた、すまん
誤:
k_start = (x/graph_size_x)*(1+(1/power*2));
k_end = ((x+1)/graph_size_x)*(1-(1/power*2));
正:
k_start = data_size*(x/graph_size_x)*(1+(1/(power*2)));
k_end = data_size*((x+1)/graph_size_x)*(1-(1/(power*2)));
0790デフォルトの名無しさん
2010/03/24(水) 02:51:28単純に元データをk_stepずつ飛ばしながら読んでるだけ?
間引いた結果全部の点が偶然同じ値だったらどうするの?
当然元データには振幅があるけど、間引くとそのx座標は点になるよ?
k_end==data_size-1になる事が無いのは問題ないの?
ここからは仮定だけど、
要はダウンサンプリングすれば計算量が減るよと言いたいの?
サンプリング定理は出現する最大周波数の2倍でサンプリングすればエイリアシングせんよーって言ってるだけで、
ダウンサンプリングする際に読み飛ばしはご法度
そもそもgraph_size_x*2にまでダウンサンプリングしちゃったら得られる物はy=0xの直線しかないんでないの
0791776
2010/03/24(水) 03:01:19> ダウンサンプリングする際に読み飛ばしはご法度
指摘ありがと、>>776は撤回する
0792デフォルトの名無しさん
2010/03/24(水) 09:05:071ピクセルごとにwavのデータ数を拾ってくるだけでいいんじゃないの?
ループの回数をデータ側じゃなくて表示側でやるだけの話なんじゃないの??
0793デフォルトの名無しさん
2010/03/24(水) 14:12:38俺まったくの部外者で、音響関連全然知らないけど、たぶんそれだと少し問題があるかもしれない。
y = f(x) を x = x0 から x = x1 まで、 y = y0 から y = y1 まで、幅 w [px] 、高さ h [px] の長方形の中に描画するプログラムを考える。
画面上で横方向に 1px 増加したら x 方向には dx = (x1 - x0) / w だけ増加する。
よって、 x = x0 から x = x1 まで、 x に dx を足しながら (x, f(x)) に対応する画面上の点にプロットしていき、前回打った点との間に直線を引く。
というプログラムを作ってみた。
振幅 A 、 周期 T の正弦波
f(t) = A*sin((2*π)*t/T)
をこのプログラムで表示してみた。
T が十分長いとき、ちゃんと振幅 A で表示された。
しかし、 T が非常に小さくなると、振幅が一定でなく、上端や下端を見ると別の波長の波が見られた。
また、 T ≦ dx で、 T = dx/n (nは自然数) のとき、波がまったくなく、平らな状態となった。
たぶん、ピクセル単位で間引くと元の波形とは異なる図になる場合があると思う。
0794デフォルトの名無しさん
2010/03/24(水) 14:42:160795デフォルトの名無しさん
2010/03/24(水) 15:04:08それは>>777と等価だろ
>>793
それがサンプリング定理
ただのエイリアシング
0796デフォルトの名無しさん
2010/03/25(木) 13:39:03俺も遅い気がするが助言は出来ないw
どこか間違えてるんじゃね?
0797デフォルトの名無しさん
2010/03/25(木) 22:28:07例えばパラメータの1つが0から255までの値だとします。
これをそのままビットで表すと8個の0か1の値になりますが、
交叉した時、10進数にすると親とはかけ離れた数値になってしまう(突然変異と変わらない)気がします。
0798デフォルトの名無しさん
2010/03/25(木) 22:34:0110万要素の配列を最適化したい時に
10万要素の配列同士を要素単位で適当に交差させる、とか、そういう感じだよ
0799デフォルトの名無しさん
2010/03/25(木) 22:38:38なるほど。
パラメータがA,B,Cの場合、子のパラメータは親1のA、親2のB、親1のCみたいになるっていう事ですね。
0800デフォルトの名無しさん
2010/03/25(木) 22:47:03グレイコード
0801デフォルトの名無しさん
2010/03/25(木) 23:53:52なるほど、10進数で近い値がビットでも近くなる2進数のような物があるんですね。
0802デフォルトの名無しさん
2010/03/29(月) 11:26:43ときオーバーフローしないで pow(b_0,a_0,)*pow(b_1,a_1)*...*pow(b_n,b_n)を計算するアルゴリズムを
教えてください。
0803デフォルトの名無しさん
2010/03/29(月) 11:30:18a_0....a_n∈unsigned int、 b_0...b_n∈int、 pow(a_0,b_0,)*pow(a_1,b_1)*...*pow(a_n,b_n)∈doubleの
ときオーバーフローしないで pow(b_0,a_0,)*pow(b_1,a_1)*...*pow(b_n,b_n)を計算するアルゴリズムを
教えてください。
0804デフォルトの名無しさん
2010/03/29(月) 11:34:04intとdouble以外は使ってはいけません。
0805デフォルトの名無しさん
2010/03/29(月) 12:13:57普通に計算してオーバーフローするのなら、計算結果がそもそもdouble型の値の範囲を越えているのでは?
真に誤差を最小にするのなら、途中の計算をすべて整数の多倍長演算で行い、最後の結果をdouble値に変換すればいいと思う。
そうでなければ、誤差が蓄積しないよう、pow(b_i,a_i)について、値が近いものどうしの乗算となるよう、計算順序を工夫するとか。
0806デフォルトの名無しさん
2010/03/29(月) 12:15:460807デフォルトの名無しさん
2010/03/29(月) 12:23:04計算結果がdouble型を越えないことが保証されるとき、計算結果がオーバーフローするような計算方法があるの?
0808デフォルトの名無しさん
2010/03/29(月) 12:25:140809デフォルトの名無しさん
2010/03/29(月) 12:34:350810デフォルトの名無しさん
2010/03/29(月) 12:34:54なんか宿題スレのつもりで使う人がたまに出てくるけど、
自分が問題を理解していない時には、先にくだ質へ行ってからにして欲しい。
不具合の出るアルゴリズムを不具合の出ないアルゴリズムに置き換えるのは、
どちらかというとアルゴリズムの話というよりバグ修正の話だから。
先にくだ質とかで「何でオーバーフローすんの?」って聞いたほうがいい。
とりあえず、不具合の発生する a[] と b[] の具体的な例を書き込んでごらん。
0811デフォルトの名無しさん
2010/03/29(月) 12:38:06double型ではなくint型を返すpow関数を使ってオーバーフローしてして、計算誤差を最小にしたいのであれば、
やはり多倍長演算を使うべきでは?
0812デフォルトの名無しさん
2010/03/29(月) 12:42:00いずれにしろスレ違いくさい。
0813デフォルトの名無しさん
2010/03/31(水) 14:50:30int n=1;
int d=1;
for( int i=0; i<aSize;++i){
if(b[j]<0){
d*=pow(a[i], abs(b[i]));
}else{
n*=pow(a[i],b[i]);
}
}
}
return (double)n/d;
0814デフォルトの名無しさん
2010/03/31(水) 18:44:04d*=pow(a[i], abs(b[i]));
int 型の変数 d と double 型を返す関数 pow を掛けて、 int 型の変数 d に代入したということは、この時点で最大値は int 型の最大値までとなる。
計算結果が int 型の最大値を超過するとオーバフローとなり計算結果に意味はなくなる。
n*=pow(a[i],b[i]);
int 型の変数 n と double 型を返す関数 pow を掛けて、 int 型の変数 n に代入したということは、この時点で最大値は int 型の最大値までとなる。
計算結果が int 型の最大値を超過するとオーバフローとなり計算結果に意味はなくなる。
0815デフォルトの名無しさん
2010/04/01(木) 19:58:12ドロネー三角形分割について誰かわかりやすく教えて
0816デフォルトの名無しさん
2010/04/01(木) 19:59:090817デフォルトの名無しさん
2010/04/01(木) 20:21:520818デフォルトの名無しさん
2010/04/01(木) 21:40:570819デフォルトの名無しさん
2010/04/10(土) 14:59:23もっと詳しくお願いいたします。
できればコードつきでお願いいたします。。
0820デフォルトの名無しさん
2010/04/10(土) 15:43:05double n = 1.0; /* ← int を double に。 */
double d = 1.0; /* ← int を double に。 */
for( int i = 0; i < aSize; ++i){
if(b[j] < 0){
d *= pow((double)a[i], abs((double)b[i]));
/* もし d が int 型だと、元の d と pow 関数の戻り値の積が int 型で扱える最大値 (INT_MAX) を超えたとき
オーバフローとなり、正しい計算結果を記憶することができない。 */
}else{
n *= pow((double)a[i], (double)b[i]);
/* 同様。 */
}
}
return n/d; /* 型変換は不要。 */
0821デフォルトの名無しさん
2010/04/20(火) 02:21:40簡易的に書くと
連番 名前 深さレベル
1 aaa 1
2 bbb 2
3 ccc 2
4 ddd 3
5 eee 2
の様な構造から、例えばaaaという名前でアクセスすると自分の直下のbbb,ccc,eeeが取得でき、cccは
次の連番に深さ3のdddがあるので、結果的にbbbdddeeeを取得できる。
bbbを取ろうとした場合は、次の行が同レベルのcccなので純粋にbbbを取得できる。
というような感じです。
そもそもはバイナリのファイルをこのようなレイアウトファイル(スタートとレングス、型情報つき)で
数バイト毎に取りだして、然るべき型として解釈するもののようです。
日本語でおけと言われるような感じもしますが、どんな手順を考えると良いかわかりません。。。よね('A`)
0822デフォルトの名無しさん
2010/04/20(火) 03:30:33COBOLも満たしたい仕様も俺が何の仮想言語で書いてるのかもよくわからんが
なんとなくこんなものを書いてみる
&push(@data, $start); #番兵
for($seek = $start; $seek++; $start.depth < $seek.depth){
if($seek.depth < $seek.next.depth){
next;
}
&output($seek.name);
}
&pop(@data); #番兵消去
0823デフォルトの名無しさん
2010/04/26(月) 06:51:20問題は1次元から始まり2次元、3次元、4次元と対象が増えた場合
再起呼び出しでこういうのって出来る?
0824デフォルトの名無しさん
2010/04/26(月) 10:01:35二次元配列(など)をソートしたいの?
適当に一次元参照してソートしたんじゃダメかい?
具体例出すのが早道だと思うお。
0825デフォルトの名無しさん
2010/04/26(月) 14:43:19配列が何次元かは不明で1次元の時は1次元で2次元の時は2次元でソート
3次元の時はもちろん3次元で
0826デフォルトの名無しさん
2010/04/26(月) 14:55:36data1 = [3,1,6,4,8];
tmp1 = sort(data1); #[1,3,4,6,8]
data2 = [[2,5],[7,6],[3,1]];
tmp2 = sort(data2); #[[1,3],[2,5],[6,7]]
こういうことをやりたいのか?
0827デフォルトの名無しさん
2010/04/26(月) 15:37:06何階層あるかの情報もあるから
for(i=0;i<階層;i++){
sort(dataの階層のポインタ、子の階層の数)
}
みたいな感じでこのsort関数の中身は固定出来るのかな?
0828デフォルトの名無しさん
2010/04/26(月) 16:42:34だから、多次元のデータは一次元に写像できるからソートには関係ないってば。
0829デフォルトの名無しさん
2010/04/26(月) 20:43:14どうやって?
0830デフォルトの名無しさん
2010/04/26(月) 21:27:230831デフォルトの名無しさん
2010/04/26(月) 21:30:04多倍長ソートの流用じゃね?
0832デフォルトの名無しさん
2010/04/26(月) 23:02:52言ってる意味が分かった
あらかじめ次元の目印をつけた1次元バッファを用意してそれを並び替えろってことか
そういう方法があるのは分かってる
問題は関数のネストだけでそれが出来るか聞いてるの
>>830
つアルゴリズムスレ
>>831
多倍長って普通ソートには似合わない言葉じゃないかな
0833デフォルトの名無しさん
2010/04/27(火) 08:37:29多次元データを辞書式にソートしたいのか、
それとも再帰的にソート(>>826)したいのか。
まあ何にせよループで書けるものは再帰で書けるから絶対に書けるんだけど。
0834デフォルトの名無しさん
2010/05/03(月) 19:59:30なんかの本で見たんですが、
式:項の加減算
項:因子の乗除算
因子:数字、または式
みたいに考え、それぞれ関数
foo1()
{
}
0835デフォルトの名無しさん
2010/05/03(月) 20:04:37途中で書いちゃった
int foo1()
{
int a = foo2();
int b = foo2();
int c = a + b;
return c;
}
int foo2()
{
int a = foo3();
int b = foo3();
int c = a * b;
return c;
}
int foo3()
{
if(パース文字列==数字)
return 数字;
else if(パース文字列=='('で始まる)
return foo1();
}
みたいな再帰でやるのが普通でございますか?
0836デフォルトの名無しさん
2010/05/03(月) 20:37:510837デフォルトの名無しさん
2010/05/03(月) 20:39:24再帰でやるのが普通
0838デフォルトの名無しさん
2010/05/03(月) 20:40:57再帰になるというか
0839デフォルトの名無しさん
2010/05/03(月) 20:46:06ありがとうございます
そのばあいって、演算子の種類毎に関数作るモノなんですか?
足し算だけする関数とか、引き算だけする関数とか
それとも加減算はまとめて一個の関数とか
0840デフォルトの名無しさん
2010/05/03(月) 21:14:12演算子の優先順位でまとめる
薄いのでいいからコンパイラの本を読んだ方がいい
0841デフォルトの名無しさん
2010/05/03(月) 21:15:32そうですね確かにw
本読みます
0842デフォルトの名無しさん
2010/05/03(月) 21:21:06一まとめにする。最初はEBNF通り全部単関数で作っても良い。
二項演算子は右結合、左結合があるからそれぞれ分ける。
?:の三項演算子もあるから分ける。単項も前置と後置で分ける。
最後に変数名やリテラルや括弧とかを処理する頭を作る。
括弧ならその中の式をさらに再帰的に解析する。
0843デフォルトの名無しさん
2010/05/06(木) 13:47:53何回もやると飽きるけど。
0844デフォルトの名無しさん
2010/05/06(木) 14:22:19その際、常に相手の位置に合わせるのではなく、
相手が現在の角度より上に居る場合は上に、下に居る場合は下に少しづつ向きを変えたい
atan2で取った角度と現在の角度radの値を単純に評価すると、
atan2の角度が30度→-30度となった時にラジアンがPI/6->11*PI/6になって砲台が逆回転し始める。
なんかいい方法はあるだろうか。
0845デフォルトの名無しさん
2010/05/06(木) 15:19:110846デフォルトの名無しさん
2010/05/06(木) 16:09:45相手の座標が(x, y)とすると
-x sinθ+y cosθの符号でいいんじゃね?
0847デフォルトの名無しさん
2010/05/06(木) 17:32:270848デフォルトの名無しさん
2010/05/06(木) 18:27:140849デフォルトの名無しさん
2010/05/07(金) 10:51:14そのとき、片方を90度回転させておく。
すると 846 になる。
0850デフォルトの名無しさん
2010/05/07(金) 10:57:06なに?どういうこと
0851デフォルトの名無しさん
2010/05/07(金) 13:00:11プラスなら前(同じ方向) 180 度、マイナスなら後ろ 180 度だということがわかる。
これを、砲台を回転すべき向きに使用したい。
では、どちらでもよいから片方のベクトルを 90 度回転させておけば、前後ではなく左右を判別することができる。
90 度回転は (x', y') = (-y, x) で表現できる。
なぜなら、sin90 = 1, cos90 = 0 なので、90 度回転は (x', y') = (x*cos90 - y*sin90, x*sin90 + y*cos90) = (x*0 - y*1, x*1 + y*0 ) だから。
砲台から照準対象のベクトルを (x, y) とし、現在の砲台の向きをθ、向きのベクトルを (cosθ, sinθ) とすると、90 度回転した向きのベクトルは (-sinθ, cosθ) となる。
(x, y) と (-sinθ, cosθ) の内積は x*-sinθ + y*cosθ であり、 846。
なお、一度に回転する量があると思うが、必要な回転量がそれよりも小さい時は、atan で算出した向きに設定しないとブルブルいうことになるので注意。
0852デフォルトの名無しさん
2010/05/08(土) 13:41:470853デフォルトの名無しさん
2010/05/08(土) 14:06:14外積は2つのベクトルを右回りにするほうに向くんで、どっち
向きかで判定するってことね。はじめの2つのベクトルが
どちらもxy平面上にあるから外積はz軸方向を向くので
z成分だけ考えれば良くて、結局851が内積で考えたときと
同じ式になる。
他の考え方としては、(x,y)を-θだけ回転させた(x',y')のy'の
正負で判定するというのもある。回転行列を使うわけだが、
これも結果は同じになる。
0854851
2010/05/09(日) 01:10:53丁寧に説明するときには、出てきたベクトルと (0, 0, 1) との内積を取ることになり冗長だ。
個人的には内積での説明が、最もわかりやすいと思う。
それに、回転限界判定の最適化の際に、|A| * |B| * cosθを意識しておくことが役に立つことも、内積推しの理由。
0855デフォルトの名無しさん
2010/05/09(日) 10:36:42回転限界判定の最適化ってなんですか?
0856デフォルトの名無しさん
2010/05/09(日) 10:43:17内積が一番素直かもね
0857デフォルトの名無しさん
2010/05/09(日) 11:46:32正規化するのが一番素直な実装だと思うけど。
0858デフォルトの名無しさん
2010/05/09(日) 11:51:23内積はダメだわ
やっぱ外積だ
0859デフォルトの名無しさん
2010/05/09(日) 12:29:101フレーム当たりの回転量よりも、現在のなす角が大きいかどうかの判定の最適化。
小さければ、atan やベクトル正規化で自機の方向に正対させないとブルブルすることになる。
0860デフォルトの名無しさん
2010/05/11(火) 17:14:24線より左にあったら左に回して
右にあったら右にまわせばいいだけ。
0861デフォルトの名無しさん
2010/05/11(火) 19:36:30どれだけ回すんだ?
0862デフォルトの名無しさん
2010/05/11(火) 21:04:110863デフォルトの名無しさん
2010/05/12(水) 01:05:00誰に何を言ってるんだ?
0864デフォルトの名無しさん
2010/05/14(金) 21:45:34A[i][g]の評価値であるAFitness[g]があります。
AFitness[g]を大きい順に並べ替えているのですが、
同時にA[i][g]も並び替えを行いたいのですが、
いまいち考え方が思い浮かびません。
gの中にi=0〜nの値があってiの中身を評価してgの評価値を
AFitness[g]に格納->ソート->A[i][g]もAFitness[g]の順に並び変えたいのです。
お知恵を頂けないでしょうか?
0865デフォルトの名無しさん
2010/05/14(金) 22:16:36言語が分からんが、C++ならi,g,AFitness[g]を同じクラスに突っ込んで
AFitness[g]で大小を比較する比較関数書けばいい。
0866デフォルトの名無しさん
2010/05/14(金) 22:40:44キャッシュ等を考慮しなければ
0867デフォルトの名無しさん
2010/05/14(金) 23:16:21並び替えであるgがg'に移った情報をインデックスすればよいのですが、
クイックソート内で行う必要があり、ややこしいです。
AFitnessの値を追跡してgがどこに行ったかを探索すればいいですが、
AFitnessの値が同じで、[i]の中身が微妙に違う可能性があり、
しっくりこない次第です。
>>866詳しくお願いします。
0868デフォルトの名無しさん
2010/05/17(月) 14:05:15もしそうだったなら「qsort 使い方」でググって。
評価値とインデックス(あるいは元データ)の組の配列を評価値でソートすればいい。
0869デフォルトの名無しさん
2010/05/17(月) 18:54:09で、qsort() を使っているのか、自前でクイックソートを実装したのかによって回答が違うよね。
自前なら2個 swap() しろってだけの話しだし、流石にそれは無いのかな。
0870デフォルトの名無しさん
2010/05/17(月) 22:13:11実は進んでいません。
qsortがあることを知りませんでした。自前のクイックソートの話でした。
swap() の意味がわからないのがつらいです。
ぐぐってみました。
構造体のやり方が載っていました。
具体的にはGA遺伝的アルゴリズムを実装しています(趣味と実益でです)
A[i][g]iには遺伝子がgは個体格納用の配列です。
0からgの個体にそれぞれA[i]の遺伝子があり、その遺伝子の評価値が
AFitness[g]となっています。AFitnessの順にならびかえているのですが。
単純なはなしなのですが、
ググった例題では構造体を使った例がありました。
しばらく考えてみたいと思います。
0871デフォルトの名無しさん
2010/05/18(火) 03:39:35>具体的にはGA遺伝的アルゴリズムを実装しています
>>867によると異なる遺伝子で同じ評価値になることがあるんですよね。
クィックソートは安定ソートでないので、
同じ評価値の遺伝子の順番がソートのたびに変わります。
意図しないランダムな動きを加えてしまうのでよくないのでは?
基数ソート+分布数えソート(パケットソート)なら安定ソートだし
gが大きければクィックソートより圧倒的に速いです。
下記ページから各ソートの説明に飛べます。
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
0872デフォルトの名無しさん
2010/05/18(火) 07:55:41{[評価値, インデックス, 対象]}をソートすればおk
ってこと?
0873デフォルトの名無しさん
2010/05/18(火) 14:28:21いいえ、対象も並べ替えるならインデックスを追加する意味はありません。
対象のサイズが大きいからソートの時に対象自体を並べ替えるとソートが遅くなります。
代わりにインデックスを並べ替えると対象のサイズがソート速度に影響しません。
だから{[評価値, インデックス]}をソートすればOKです。
処理の単純さを選ぶなら{[評価値, 対象]}、
ソート速度を選ぶなら{[評価値, インデックス]}です。
0874デフォルトの名無しさん
2010/05/18(火) 18:17:11JavaのBigIntegerで行っていますが、これは底2の桁数log2の整数部まではサポートされていて、
頻繁に使う10はサポートされていません。
少し見た限りだと内部では底は2^31あたりで1e+8で連続div+remして文字列の連結をしてるようです。
底2の桁にlog2[10]をかけたりも出来ますが+/-1の誤差が出るので正確に求めるにはコード(分岐とステップ数)が増えるのでメンテナンスが大変になります。
いったん底10でStringにしてlengthが一番単純だと思うのですが他の方法があればを教えてください。
0875デフォルトの名無しさん
2010/05/18(火) 19:13:40底10で文字列にしてlengthが基本.
文字列を必要な分だけ覚えるようにすれば若干速くなるけど
たいしたことはない.
もし本当に早くしたい(=底10を連発する)なら
多倍長整数をそもそも10のベキ底で用意するべきで,
COBOLなんかはそういう風に設計されている.
0876デフォルトの名無しさん
2010/05/18(火) 21:26:38単に、ランク順にならびかえて、その並びになるように評価元の配列も一緒に
並べ替えのよりよいやり方があったらなぁというものだったのですが、
なんかよくわからなくなったので、もうこれぐらいでいいです。
いろいろありがとうございました。なげやりでもうしわけないです。
0877デフォルトの名無しさん
2010/05/22(土) 15:45:47いや敢えて”対象”って入れたのはExcelで複数列を選択してソートするような感じ
{評価値, インデックス}だとソート対象に”対象”が入ってないから出鱈目になるっしょ
ああ,でも{評価値, インデックス, 対象}を新たに”対象”として拡張してソートすると,
要素毎の比較でちょっと時間かかるか
0878デフォルトの名無しさん
2010/05/24(月) 16:52:42対象自体をソートしてしまったらインデックスが出鱈目になる。
0879デフォルトの名無しさん
2010/05/27(木) 05:29:12そうならないように{評価値, インデックス, 対象}をソートする形なん
0880デフォルトの名無しさん
2010/06/07(月) 09:53:46そういう実験データってどこかにないですかね
0881デフォルトの名無しさん
2010/06/07(月) 13:50:420882デフォルトの名無しさん
2010/06/08(火) 03:10:49それは確率か統計の問題だろ。
馬鹿か、おまえは。
0883デフォルトの名無しさん
2010/06/08(火) 09:05:25128bitなんだから16バイト以内で必ず当たるのは
確かだけどさ。
0884デフォルトの名無しさん
2010/06/08(火) 09:15:20周期的じゃないだろうから
0885デフォルトの名無しさん
2010/06/08(火) 09:18:422つ目以降が見つかるまでのバイト数は違うだろうし
「始めて重複が現れる」ってのは意味がない
要するに素数の出現する間隔みたいなもんで
ずっと出ないときもあれば連続して出るときもあるかも知れない
確率でしか評価出来ないと思う
0886デフォルトの名無しさん
2010/06/08(火) 09:40:47総当りに30秒かかったから、128bitの総当りには1.15E27年
かかる計算だ。100万台ぐらい用意したって全く追いつかないよ。
0887デフォルトの名無しさん
2010/06/08(火) 09:42:330888デフォルトの名無しさん
2010/06/08(火) 09:48:38それより短い長さのファイルもあることを考えると16バイト以下の条件
でハッシュが重複するファイルがあるのは確か。でもじゃあ15バイト
以下なら重複がないといえるかどうかという問いに答えるのは難しそう。
0889デフォルトの名無しさん
2010/06/08(火) 10:02:550890デフォルトの名無しさん
2010/06/08(火) 13:16:230891デフォルトの名無しさん
2010/06/08(火) 21:54:100892デフォルトの名無しさん
2010/06/09(水) 21:48:180893デフォルトの名無しさん
2010/06/10(木) 03:39:41現実問題なら、たとえばテキストファイルならどうよ? 2バイト文字は含むのか? サンプルの規模は?
そんなことも考えないで「確率は?」とかバカすぎる。
この手の話題では、自分がバカだと思うヤツは黙ってろ。
0894デフォルトの名無しさん
2010/06/10(木) 07:16:18バカと言う自覚がないのがまずバカの十分条件だろ。
バカだなぁw
0895デフォルトの名無しさん
2010/06/12(土) 22:41:18wikiを見てもよく理解できなかったので、簡単に教えていただけないでしょうか。
0896デフォルトの名無しさん
2010/06/13(日) 00:31:390897デフォルトの名無しさん
2010/06/13(日) 09:05:36ウザw
0898デフォルトの名無しさん
2010/06/13(日) 09:16:240899 ◆dmYlwlD4Tc
2010/06/13(日) 23:49:53そんな事すらわからないのか
0900デフォルトの名無しさん
2010/06/14(月) 08:53:240901デフォルトの名無しさん
2010/06/18(金) 21:08:15それらの合計はm
並び替えて同じものは同一とみなす
上記の条件を満たすすべての並びを
再帰や可変長バッファを使わずに
かつスキップ無しで出力することって可能?
0902デフォルトの名無しさん
2010/06/18(金) 22:18:57m = P1^N1 + P2^N2 + ... + Pn^Nn
の, N1 ... Nn が取りうる, すべての組合わせを出力すればいいのでは?
# そうゆう問題じゃなかったらごめん
0903デフォルトの名無しさん
2010/06/18(金) 22:20:470904デフォルトの名無しさん
2010/06/18(金) 22:46:056 0 0 0
5 1 0 0
4 2 0 0
4 1 1 0
3 3 0 0
3 2 1 0
3 1 1 1
2 2 2 0
2 2 1 1
が欲しい答えです
さらにループで調べて合致していないものを捨てるという方法は無しで
漸化式のように前の解から次の解が求められるようにしたいです
0905デフォルトの名無しさん
2010/06/19(土) 00:30:15m= 6
dim d(n) as integer
d(n-1)= m
f= true
while f
debug.print d
for i= 0 to n
if d(i) > 1 and d(i)-1 > d(i+1)+1 then
d(i)= d(i)-1
d(i+1)= d(i+1)+1
f= false
exit for
endif
next i
wend
思いつきで書いてみた。言語は趣味
デバッグ?何それおいしいの?
0906デフォルトの名無しさん
2010/06/19(土) 01:24:080907デフォルトの名無しさん
2010/06/19(土) 05:50:39その例は先頭桁の大きさの順に並んでいますが、
n=1〜4ごとに出力すると全ての組み合わせを求めやすいです。
各nについて先頭桁以外は全部1の状態で開始します。
自分より2以上小さい桁がある桁のうち一番左側の桁をx桁とします。
x桁より2以上小さい桁のうち一番左側の桁をy桁とします。
x桁を1減らしy桁を1増します。
6 0 0 0 n=1
5 1 0 0 n=2
4 2 0 0
3 3 0 0
4 1 1 0 n=3
3 2 1 0
2 2 2 0
3 1 1 1 n=4
2 2 1 1
0908デフォルトの名無しさん
2010/06/19(土) 08:50:51桁数で並べ替えればよかったんですね
どうもありがとうございました
0909デフォルトの名無しさん
2010/06/20(日) 09:02:04真ん中の一番上を1と置いて〜みたいな特殊な解を使わないとしたら
方程式解いて変数を減らせるだけ減らしてあとは総当たりでやるほかない?
0910デフォルトの名無しさん
2010/06/20(日) 12:47:490911デフォルトの名無しさん
2010/06/20(日) 19:45:290912デフォルトの名無しさん
2010/06/20(日) 19:51:000913デフォルトの名無しさん
2010/06/20(日) 20:00:51○魔方陣
0914デフォルトの名無しさん
2010/06/20(日) 22:08:000915デフォルトの名無しさん
2010/06/20(日) 22:24:560916デフォルトの名無しさん
2010/06/20(日) 23:25:30O(n)でやる方法はある。
ただし、答えは尻から出る
0917デフォルトの名無しさん
2010/06/27(日) 23:03:43sqrtを使わない方法ってある?
もしくは、少しでも軽い方法。
現状はこういう感じ。
circle a, b //略
dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))
return dist < a.radius + b.radius
0918デフォルトの名無しさん
2010/06/27(日) 23:07:19全部2乗で計算
0919デフォルトの名無しさん
2010/06/28(月) 12:30:01更に処理時間を減らしたいなら、radiusの2乗値をキャッシュ。或いは事前に計算。
0920デフォルトの名無しさん
2010/06/28(月) 14:47:13(a.radius + b.radius)^2 ≠ a.radius^2 + b.radius^2
なので、radiusの2乗値は事前計算では駄目。
0921デフォルトの名無しさん
2010/06/28(月) 16:59:19早速のレスどうもありがとうございます!!
なんだかそうやればいけそうな気はしていたのですが、
言われてみるとハイ、なにかもう恥ずかしいくらいです。
アルゴリズムとはかけ離れるかもしれませんが少し。
sqrtは軽くないと聞きました。三角関数も軽くはないと聞きました。
割り算も、それなりに処理時間食ってると聞きました。
では、掛け算は?足し算は?
割り算>>>>>>>>>>>>>掛け算>>足し算=引き算
くらいのものでしょうか?
ttp://www.nextftp.com/swlabo/m1_vbnet/hp_experiment/exp007.htm
こういうサイトによると、割り算だけは異常に時間食ってるようですが。
0922デフォルトの名無しさん
2010/06/28(月) 17:29:26尤も、整数定数除算は乗算で実装してくれるコンパイラも多い。
それよりも何よりも、float ⇔ double ⇔ int の型変換が遅いのでその辺りも注意。
つーか、この辺りのノウハウは最適化スレの方が詳しい。
0923デフォルトの名無しさん
2010/06/28(月) 17:40:310924デフォルトの名無しさん
2010/06/28(月) 17:47:46いまどき四則演算の速度差なんて気にする方が無駄。
>>923
(a.r + b.r)^2の方が、加算1回乗算1回で済むので計算量が少ない。
0925デフォルトの名無しさん
2010/06/28(月) 18:58:20Intelは除算高速化回路を最新のCore iシリーズに入れたわけで
もっともリコンパイルなしのレガシーソフトウェア対策がメインではあるんだろうけど
0926デフォルトの名無しさん
2010/06/28(月) 18:58:42なるほど! スレ違いどうもすみません。最適化スレ読んで勉強してきます。
>>923
そういう工夫はアルゴリズムスレ特有ですね。
>>924
ご忠告ありがとうございます。無駄なところに拘らないように気をつけます(`・3・´)
0927デフォルトの名無しさん
2010/06/29(火) 03:21:50当たるまで調べでもしない限り、確実にあるといえるのは16バイトのときだろう。
確率の話をするなら、普通はもっともっと早い段階で見つかる。
ていうか、なんで「誕生日のパラドックス」の話が出てこない?
0928デフォルトの名無しさん
2010/07/03(土) 16:37:47適当なアルゴリズムってありますか?
具体的な用途を言うと、USB-HIDキーボードのキーバッファです。
Nキーロールオーバーに対応させるため待ち行列で管理します。
今の実装は単純な配列とmemcpyです。
リンクリストやリングバッファにすることも考えましたが、
待ち行列とはいえキーを離したときにデータの不特定箇所の
削除が発生するので微妙でした。
0929デフォルトの名無しさん
2010/07/03(土) 20:42:37これを0000.....を基点として円を描きたいのですが
つまり0000....とfffff....は同じ点になって
ある中間のハッシュαがあったときにこのαの角度を計算したいのですが
なんか簡単に出来る方法ってありますかね?
0930デフォルトの名無しさん
2010/07/03(土) 21:04:100931デフォルトの名無しさん
2010/07/03(土) 21:19:28もっと簡単に普通のdoubleとかだけ使ってやる方法はないかなと
0932デフォルトの名無しさん
2010/07/03(土) 21:23:09どうせグラフにしたら1度単位くらいでしか見えないだろうし
0933デフォルトの名無しさん
2010/07/03(土) 21:24:49上位32bitで分割すればいいだけでしたw
0934デフォルトの名無しさん
2010/07/03(土) 21:32:17上位 32bit を取り出して 0x00000000 から 0xffffffff を、0 から 2π(ラジアン)に
マッピングすればいいんちゃう?
0935デフォルトの名無しさん
2010/07/03(土) 21:33:270936デフォルトの名無しさん
2010/07/04(日) 00:08:05double d=0.0;
for(i=0;i<160;i++){ d*= 2; d+=hash[i] }
ってすれば、と思った。(仮数部の数の51回でいいと思うが、まぁ今時あんま変わらん)
doubleの性質上、2の掛け算だと誤差も最小限で済むよ。
Pythonで1000....0をdoubleと任意精度整数で比較してみたら
整数: 730750818665451459101842416358141509827966271488
小数: 7.3075081866545146e+47
と、かなりいい感じになった。
0937デフォルトの名無しさん
2010/07/04(日) 16:39:13キャッシュ効率考えたらそれでいいんじゃないの?
0938デフォルトの名無しさん
2010/07/05(月) 11:16:108バイト単位にした方が(CPUにもよるけど)若干効率いいかも知れない。
0939デフォルトの名無しさん
2010/07/05(月) 22:32:18待ち行列(キュー)の実装方法によって挙動がかわるのが理解できないんだが…
普通はリングバッファでやるのが効率的だが、なぜまずいの?
0940デフォルトの名無しさん
2010/07/06(火) 12:24:57[0,1)の実数乱数から、かたよりなし、棄却なしに[0,1]と(0,1)の実数乱数って作れる?
0941デフォルトの名無しさん
2010/07/06(火) 14:02:440と1の間の数は非加算個といって無限より一杯あるんだぞ。
その中の1と0が当たる確立なんて0としかいいようがない。
0942デフォルトの名無しさん
2010/07/06(火) 14:27:24不可能。コンピュータだから所詮は整数だと思うならどうマッピング
するかだけの問題。
0943デフォルトの名無しさん
2010/07/06(火) 19:34:200944デフォルトの名無しさん
2010/07/06(火) 21:54:47連続でなくても全単射があればいいわけで(ないけど)
0945デフォルトの名無しさん
2010/07/06(火) 22:41:500946デフォルトの名無しさん
2010/07/06(火) 22:57:42棄却なしだからだめ
可能性があるのは、毎回、値を少しずつずらすくらいだな
無限回試行したときに均等になればよい
0947デフォルトの名無しさん
2010/07/06(火) 23:03:370948デフォルトの名無しさん
2010/07/08(木) 22:54:01有限精度の浮動小数点を仮定する。
以下のようにしたら一応棄却はしてない乱数が作れる。
十分な大きさのbool配列を固定小数点として使い、それぞれのbitを
rand( [0,1) ) が0.5以上
→ビットを1に
それ以外
→ビットを0に
のように計算する。その結果を浮動小数点に直す。
0949デフォルトの名無しさん
2010/07/08(木) 22:57:39浮動小数点の精度をちょうど満たすところで止めるようにしないと。
まぁ、どうせ揚げ足取りみたいな回答だけど...
でも有限精度の小数点なら、かたよりなしって考え方そのものが若干微妙だし、
有限精度じゃないのなら表現がまず難しい。
0950デフォルトの名無しさん
2010/07/09(金) 02:26:48指数が0.5で仮数が全部1な奴
0951デフォルトの名無しさん
2010/07/09(金) 12:45:370952デフォルトの名無しさん
2010/07/09(金) 21:47:09割り算が決定的な限り、かならず偏る
0953名無しさん@そうだ選挙に行こう
2010/07/10(土) 13:15:05そもそも[0,1)の一様乱数自体が存在しない。
存在したとしても、ちょうど0, ちょうど1が出る確率はないから、そのまんま[0,1],(0,1)として使える
有限精度実数の場合:
float, doubleなどのIEEE 754形式を使う場合:
[0,1)と[0,1]と(0,1)はそれぞれとりうる「場合の数」が違うわけだから、
情報量を勝手に補う、勝手に捨てる、をしないといけない。
独自形式で構わない場合:
形式を
struct{
int type;
unsigned int val;
};
とする。
type == 0のとき、val * deltaなる実数と解釈する。 ただしここでのdeltaは1/(UINT_MAX+1)なる有理数。
type == 1のとき、val * deltaなる実数と解釈する。 ただしここでのdeltaは1/UINT_MAXなる有理数。
type == 2のとき、val * delta + deltaなる実数と解釈する。ただしここでのdeltaは1/(UINT_MAX+2)なる有理数。
[0,1)の一様乱数は、typeを0, valを0〜UINT_MAXまでの一様乱数として表現できる。
[0,1]への変換は、typeを1にすることで実現でき、(0,1)への変換はtypeを2にすることで実現できる。
0954名無しさん@そうだ選挙に行こう
2010/07/10(土) 18:05:530955名無しさん@そうだ選挙に行こう
2010/07/10(土) 22:54:01そりゃ、そうならざるをえないだろ。
0956名無しさん@そうだ選挙に行こう
2010/07/11(日) 13:48:44>存在したとしても、ちょうど0, ちょうど1が出る確率はないから、そのまんま[0,1],(0,1)として使える
いやそれを言ったらちょうど0.5が出る確率もちょうど1/πがでる確率もないことにならん?
0957名無しさん@そうだ選挙に行こう
2010/07/11(日) 14:35:14無限精度だから
lim(x→∞) 1/x=0
になる、んじゃね?
0958名無しさん@そうだ選挙に行こう
2010/07/11(日) 16:04:00両方が(1.0-delta)だと(1.0-delta)+(1.0-delta)って、四捨五入で2.0になっちゃうの?
0959デフォルトの名無しさん
2010/07/12(月) 09:31:22だからその論法だと0と1の間の任意のxについて出る確率が0って
ことになるだろ。測度とか確率密度とかでぐぐって勉強するといいよ。
0960デフォルトの名無しさん
2010/07/12(月) 13:04:43確率も一緒ってことだよ。
0961デフォルトの名無しさん
2010/07/13(火) 17:16:43有限のリソースで記述できない数はいくらでもある。
>>959
任意の特定の値が出る確率は全て0だよ。当然。
0962デフォルトの名無しさん
2010/07/17(土) 01:59:32xからyまでの間の値が出る確率を求めないといけないんじゃないの?
ここで何を言おうが、メモリが無尽蔵にあろうが、コンピュータでは連続値を扱えないけど。
0963デフォルトの名無しさん
2010/07/18(日) 23:57:16有効な方法はありますか?
一度p_nを座標からハッシュして有限の領域にマップしようと思ったのですが、
矩形qを成すそれぞれの座標軸の区間[x_1, x_2], [y_1, y_2]内の点q_a, ..., q_bをまとめて得る方法が分からず、頓挫しました。
0964デフォルトの名無しさん
2010/07/19(月) 00:14:160965デフォルトの名無しさん
2010/07/19(月) 20:41:13kD木
0966デフォルトの名無しさん
2010/07/24(土) 14:22:40http://marupeke296.com/COL_2D_No8_QuadTree.html
これが恐らく最速
0967デフォルトの名無しさん
2010/07/24(土) 15:16:330968デフォルトの名無しさん
2010/07/24(土) 20:08:150969デフォルトの名無しさん
2010/07/25(日) 04:13:36実は催促なんだろ。
0970デフォルトの名無しさん
2010/07/25(日) 04:36:210971デフォルトの名無しさん
2010/07/31(土) 01:40:52正解
>>969
間違っています
0972デフォルトの名無しさん
2010/07/31(土) 06:18:09実際の所、kD木で解決したから問題なし。
妄想で出鱈目を書かないように。
0973デフォルトの名無しさん
2010/08/04(水) 11:09:48画像を圧縮する時に単純に左のピクセルとの差分にしてから圧縮する場合
日本で特許に触れるんでしょうか?
DPCMなんて古い枯れた技術だから大丈夫かと思ってたら
関連特許が山のように出願されてるみたいで怖いです。
ttp://www.jpo.go.jp/shiryou/s_sonota/map/denki14/1/1-3-1-2.htm
0974デフォルトの名無しさん
2010/08/04(水) 18:52:000975デフォルトの名無しさん
2010/08/17(火) 13:28:56図形はひょうたんの様に10%程度重なってるものから鏡餅の様に80%重なってるものまでを対象にしています。
円の直径は可変です。できれば2-5程度の複数円を抽出したいと思ってますが、2個すらできてません。
今日午前中潰して考えたんですが、なかなかいいアイディアがでません。
よろしくお願いします。
0976デフォルトの名無しさん
2010/08/17(火) 14:44:31その間の中点を二つの円で求めれば、半径と中心が出る。
f'が0な点がfで2つしかないなら二つの円の中心を結んだ点がy軸に並行で上の方法ができない。
その場合はx軸とy軸を交換して処理すれば良い。
0977デフォルトの名無しさん
2010/08/17(火) 15:37:00>>975はビットマップ画像から中心座標と半径を求めるということじゃないかな
とりあえずこんな感じでどう?
1. 輪郭線を抽出
2. それぞれの円毎に輪郭線を分割(輪郭線の傾きが急激に変わる箇所で分割)
3. 輪郭線ごとに輪郭線上の任意の2点で接線に垂直な線を求める
4. 求めた2本の線の交点が1つの円の中心点
5. 円の中心点と3.の2点までの距離が半径
0978デフォルトの名無しさん
2010/08/17(火) 21:16:580979デフォルトの名無しさん
2010/08/18(水) 03:43:392010年08月17日 14:41 発信地:ワシントンD.C./米国
http://www.afpbb.com/article/environment-science-it/science-technology/2748734/6083818
【8月17日 AFP】米グーグル(Google)の支援を受けた国際研究チームが、
人気立方体パズル「ルービックキューブ(Rubik's Cube)」の全パターンを調べ上げ、
どんな状態からでも20手以内で全面の色をそろえることができることを突き止めた。
これを突き止めたのは、米オハイオ(Ohio)州立ケント大学(Kent State University)の
Morley Davidson氏、グーグルのエンジニア、John Dethridge氏、ドイツの数学教師の
Herbert Kociemba氏、米カリフォルニア(California)州のプログラマーのTomas Rokicki氏ら
を含む数学者チーム。
数学者チームによると、「(ルービック)キューブを解く人は手順をまとめたアルゴリズムを使う。
さまざまな種類のアルゴリズムがあり、複雑性の度合いや必要な手数などが異なっているが、
人間が記憶できるアルゴリズムは、最小手でも40手以上を必要とする」のだという。
「しかし神であればもっと効率的なアルゴリズム、常に最短の手数で済むアルゴリズムを
用いるだろうと人びとは考える。これは『ゴッドアルゴリズム(神のアルゴリズム、
God's Algorithm)』と呼ばれている。また、このアルゴリズムで解くために最大で必要な手数は
『ゴッドナンバー(神の数、God's Number)』と呼ばれている。そしてついに、
ゴッドナンバーは20であることを突き止めた」(数学者チーム)
研究チームは、グーグルが提供した同社内のコンピューターの空き時間を用いて、
膨大なキューブの状態のそれぞれの解法をすべて突き止めた。それにかかった時間は
「わずか数週間」だった。グーグルは研究に提供したコンピューターの詳しい仕様などは
明らかにしていない。(c)AFP
0980975
2010/08/18(水) 09:35:03>>976
後出しで申し訳ありませんが、図形はビットマップなので最初の式が作れません
>>977
テスト画像でやってみました、いい感じで求まりました。
ありがとうございます。
実際にはビットマップの解像度が悪いせいで2の抽出が困難ですが
それは別問題なので解決とさせて頂きます。
どうもありがとうございました。
0981デフォルトの名無しさん
2010/08/18(水) 09:43:08これでも求まりそうです、
特にビットマップの解像度が低い輪郭に相当量のノイズが混入してる場合は
むしろベストかもしれません。
まだ未挑戦ですが、これも一案として試行錯誤してみます。
0982デフォルトの名無しさん
2010/08/18(水) 09:56:52問題の性質上、円は作業面に対して完全に内包されていて、全体が1つのオブジェクトを
構成しているんだから、2値化して、左上からラスタスキャンかけて、最初に見つかった
オブジェクトの要素から、右方向へ輪郭を追いかけていけば細線化する必要はないんじゃないか?
次の点が今まで辿ってきた要素から予測される方向以外へ向いているときその点を弧の接点と見なす。
最初の点は弧の頂点のはずだから以降の判定は容易だよね。
多少先読みすれば、同じ半径の円が少しだけずれて接しているような場合でも切り分けられるんじゃないかな。
ずっと追いかけ続けて、元の点に戻ってくれば走査終了。後は接続点から少し離れた充分にこの一部である
2点を使って計算すれば、誤差もすくなくなるかと。
0983975
2010/08/18(水) 10:25:27細線化ってのは別にビットマップとして線を出してるわけではないです。輪郭点の配列です。
ビットマップ上の円は上下左右方向でドットが一列に並んでしまうという宿命があるんです。
ある程度小さい(解像度の低い)円になるとそれが無視できなくなるんです。
その辺の判定をした後でないと、半径探しの為に必要な適切な点が判定できませんので
細線化したデータはメモリに保管しておいたほうがベストと判断しています。
0984デフォルトの名無しさん
2010/08/18(水) 11:12:19残りの12000個は必要なく、また安定でなくても良いです。
どのようなソートが適しているでしょうか?
ソート後の小さい方から一部だけしか必要でない場合には速くなるような方法があるのでしょうか?
0985デフォルトの名無しさん
2010/08/18(水) 11:25:04普通に考えるとソートを途中で止めるだけでいい気がしますが
データに特に特徴がなければクイックソートでいい気がします。
0986デフォルトの名無しさん
2010/08/18(水) 11:26:59なんか面白そうな話だな。
最初の3000個だけ旨く得ることができたら爽快だろうな。
クイックソートを途中で止めると出来ると思う。
0987986
2010/08/18(水) 11:27:470988デフォルトの名無しさん
2010/08/18(水) 12:03:270989デフォルトの名無しさん
2010/08/18(水) 12:14:570990デフォルトの名無しさん
2010/08/18(水) 14:42:14STL でいえば nth_element()。
上位 3000 がソートされている必要があればヒープソートを途中まで。
>989 にあるように STL の partial_sort()。
0991984
2010/08/18(水) 15:01:38現在クイックソートでやってますが途中で止めてみます。
>>988
それはちょっと…
>>989-990
partial_sort()試してみます。
ありがとうございました。
0992デフォルトの名無しさん
2010/08/18(水) 15:03:31の「k個の最小・最大要素の選択」
レス数が950を超えています。1000を超えると書き込みができなくなります。