1 :
デフォルトの名無しさん :
2008/08/03(日) 23:23:35 言語の雑談・質問スレはあるのに アルゴリズムのスレが無かったので立ててみました。 自作アプリ作成に於けるアルゴリズム指南、 基本情報レベルの幼稚園児用鈍足アルゴリズムから 高度な数式が必要な大学院生用神速アルゴリズムまで 語りませう。
MSがIMEに手を加えたせいで プログラマ板(マ板)⇒プログラマー板(マー板) プログラム板(ム板)⇒プログラムー板(ムー板) になるんじゃね
>>2 は?2ちゃんは昔から『プログラマー板』なんだが?
アルゴリズムと関係ないかもしれないけど質問です。 ツーちゃんねる用テキストエディタを作りたいのですが レス番号はどうやって把握させればいいのでしょう。 3番の人の書き込みで、『4 名前:デフォルトの名無しさん 投稿日:2008/08/03(日) 23:25:26』という文字列の書き込みをされると 判断が出来なくなるような・・・
いっぽすすんでまえならえ いっぽすすんでえらいひと ひっくりかえってぺこりんこ よこにあるいてきょろきょろ
Pen4-3GHz,DDR・SDRAM1200MBのノートパソコンでも 現実的な時間で駒を打ってくれる最強のオセロCPU(AI?)は作れますか? ここでいう最強とは、全部の組み合わせを探索できる最適なCPUです。
7 :
デフォルトの名無しさん :2008/08/03(日) 23:32:21
8 :
デフォルトの名無しさん :2008/08/03(日) 23:33:38
12 :
デフォルトの名無しさん :2008/08/03(日) 23:38:27
大学生なら The Art of Computer Programming Introduction to Algorithm は必須。 〜のアルゴリズム事典みたいな本は 稚園児向け。
13 :
1 :2008/08/03(日) 23:39:29
すみません。このスレは終了です。 どうもありがとうございました。
14 :
1 :2008/08/03(日) 23:39:58
15 :
デフォルトの名無しさん :2008/08/03(日) 23:40:17
〜再開〜
ソートのような単純な処理は標準ライブラリに限る。 ぶっちゃけ仕事で使うプログラミングなんて アルゴリズム知らなくてもいい。 それよりコミュニケーション能力のほうが大事 研究者は例外だからさっさと氏ね。
GOOGLE検索の核となるアルゴリズムを教えてください。
>>1 しょぼいな
俺なんかジンバブエ問題を多項式時間で解くアルゴリズムを発見したぞ。
でもそれを記述するにはこの余白はあまりにも少なすぎ
最も真の乱数に近くなるな種の求め方。
言語を習得する順序の話題は異常に盛り上がるけど、正直、ぜんぜん実のないスレになりがち。 本当はアルゴリズムのほうが大事なのに・・・
メニィコア上で高速なソートとか
言語で苦戦しているやつはスタートラインにも立てていないわけで アルゴリズムで苦戦して初めて入門者
>>22 そんなのはどうでもいいんだ。
アルゴリズムの話をするんだ。いいな?
25 :
デフォルトの名無しさん :2008/08/04(月) 05:01:11
悪いんだけど、まとめサイトを作る話は無期限延期にさせてくれ。 入った会社が求人票と全然違う会社でとてもとても。 年休65とかwww
>>12 > 〜のアルゴリズム事典みたいな本は
Springerから出てるぞおい。Encyclopedia of Algorithms
お高いぜ……。
共立のアルゴリズム辞典だってぜんぜん幼稚園児向けじゃないけどな
幼稚園児の段階でそれぐらい理解する頭を持ってるやつ以外死ねって事ですね、わかります
ドミノとか畳とか、1×2の格子で敷き詰められる格子を 任意の敷き詰め方で敷き詰めるアルゴリズムがわっからん いいかげんにやらせると隅とかで詰んでしまう
>>29 何となく言ってる事はわかるけど例題出してみてくれる?
>>29 ソースとかじゃなくて悪いけど
効率を求めないのであれば、
X*Yの範囲におけない場所を任意に作る
おける場所の個数をNとして2の倍数でなければエラー
N/2個のブロックを用意、位置と縦か横かのパラメータを持つ
ブロックを左上から積めていき詰まったらブロックを戻して再検索
>>31 トライアンドエラーでいけるのかな…
>>30 こんな感じ
┌┬┬┬┬┬┬┬┐ ┏┓
├┼┼┼┼┼┼┼┤ ┃┃
├┼┼┼┼┼┼┼┤ ┗┛
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
└┴┴┴┴┴┴┴┘
>>32 はずしてたらすまんけどゲームとかでランダムに敷き詰めた
ものが欲しいのなら、こういう形で必ず敷き詰められるから
┌┬┬┬┬┬┬┬┐
│││││││││
├┼┼┼┼┼┼┼┤
│││││││││
├┼┼┼┼┼┼┼┤
│││││││││
├┴┼┴┼┴┼┴┤
└─┴─┴─┴─┘
これから
┌┬┐┌─┐
│││├─┤
└┴┘└─┘
をランダムに90度回転するというのはどうだろう。
敷き詰められたという条件だけでなく (特に乱数が擬似で無いならば) 乱数の機嫌がよければどの敷き詰め方も得られる可能性があるアルゴリズムが欲しい
本題とは関係ないけど疑似乱数というものをわかってない気がする。 (理想的には)ブラックボックステストでは疑似かどうか判定できない ものが疑似乱数列。 本題 あらゆる敷き詰め方を網羅できるアルゴリズムを考えてみる。 左上から順番に空きを探して、空きがあったらまず横向きに置いて、 その先を置いていく。その先のパターンを全て網羅したら、縦向きに 置く。つまったらバックトラック、というアルゴリズムで、あらゆる 敷き詰め方が網羅できる。 まず横向きに置く→次に縦向きに置く、この順序を乱数で決定 するようにすればランダムになる。
敷き詰める空間が矩形と言う前提があるなら、バックトラックのいい練習台になりそうだ。
C++かなにかで再帰使って実装すれば一日もあればできそうだね。
>>29 勿論、隅で詰まったら手を戻して詰め直してみるだけ。
ファイル管理ソフトでファイル内文字列まで見て該当ファイルを見つける という検索がありますが、 あれは文字列の形式やフォーマットあるいはエンコードなどをすべての ケースで調べているのでしょうか? たとえばExcelやワードなどのファイルの場合は、それをテキスト形式 で取り込んで調べるのでしょうか? よろしくお願いします。
そりゃファイル管理ソフトによるだろ・・
すまん、図形描画アプリみたいなものを作ってるんだが・・・ 次のようなもので悩んでます。 1.複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか? 場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。 総当たり以外でエレガントな方法というとどんなんざんしょ? 2.同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。 教えてエロイ人・・・
ごめんなさい。別スレの方が人いそうなのでそっちにかくです・・・ すれよごしすまんそ。
全くの初心者が参考書を買うに当たってお勧めできるものなど教えていただけますでしょうか。 アルゴリズムは分かっても、それをうまくフローチャート化できなかったりします。 あとソートに関しても前述の理由でうまく説明が出来ない場合があります。 初歩以前の質問かもしれませんが、どなたかご教示願います。
そういうのってなんとなくできるようになるもんだと思われてる感じで、 ちゃんと説明してくれるのは少ないよね。 英語で良ければHtDPがいいよ。
>>42 ありがとうございます。
書籍だと1万円するようなのですが、とりあえずwebサイトも見つけたので書籍購入までで時間が取れる時はそちらを参照してみます。
どなたでも、日本語の書籍でも何か参考になるものがありましたら、お願い致します。
可変長のバイナリデータをファイル名に変換する単射の写像を作らなくてはいけません。 ただしファイル名が長すぎて使えないことは考慮しないとします。 UnixならBase64、WindowsならBase32を使っておけばとりあえずOKですが。。。 UnixはスラッシュとNUL以外は何でも使えるようなので、Base64は非常にもったいない気がします。 なにかいいアイディアはありますか?
>>44 > UnixはスラッシュとNUL以外は何でも使えるようなので、Base64は非常にもったいない気がします。
だからといってマルチバイト文字列でもなしに
printableでないバイトを使うのは非常に愚かだと思うがどうかね。
使えない文字だけURLエンコードみたいに %xx にする
47 :
デフォルトの名無しさん :2008/10/24(金) 21:57:47
二つの折れ線グラフが似ているものかどうかを確かめるアルゴリズムってありますか? 詳しい書籍、HPなどがあれば教えてくださると助かります。
>>44 使っていい文字n個を全部使ってBase<n>エンコードすればいいやん。
49 :
デフォルトの名無しさん :2008/11/18(火) 12:10:38
あっちむいてふたりで前ならえ こっちむいてふたりで前ならえ あっちむいてふたりで前ならえ こっちむいてふたりで前ならえ 手を横に あら危ない 頭をさげればぶつかりません 手を横に あら危ない 頭をさげれば大丈夫
>>29 アホだね「詰んだ」らそれを回避すればいいだけだろう
とアホが申しております。
52 :
デフォルトの名無しさん :2008/11/18(火) 14:08:12
今ちょっと有根系統樹という有向グラフについて調べてるんですが、 2つの同数の葉を持つ木構造のデータの類似性を比較するアルゴリズムってなにかないでしょうか? データの文字列に対して編集距離を使って計算を行ったのですがそれではあまり差異が出ないので他の方法を探してます
今日久しぶりにゲーセンでグラディウスUをやってきた。やっぱ改めてすごいね、当時 のコナミは。何がって、1面の竜!1本の竜に見えるけど、よーく見ると複数のパーツが 組み合わさってできている。多関節キャラの範疇に入るのかな? 他のギミックを見ると、どうやら回転機能は使ってないようだ。(カニの脚の上(膝より上って 意味ね)は一見すると回転機能を使っているように見えるが、よく見ると使ってない) ということは、少しずつ回転させた絵をいっぱい用意してあるんだろうな。普通に蛇型? 竜型?のキャラを作ったらR-TYPEの蛇みたいに各パーツが別れて見える。それをきれ いにつながっているようにデザインしているのがすごい!
54 :
デフォルトの名無しさん :2008/12/10(水) 21:45:28
多角形を四角形に分割するアルゴリズムってありますか? 参考になる情報をお持ちでしたらご教授のほどよろしくお願いいたします。 凹凸組み合わせた図形を考えると難しそうです。 入力:多角形の頂点座標リスト 出力:四角形(rectangle)のリスト
三角形でなく四角形なのはなぜ、とかふと疑問に思ったり。
無責任思考垂れ流し 1.三角形に分割する 2.三角形をノード(節点・頂点)、辺をエッジ(枝・辺)とするグラフ理論に置き換える 2B.ただし辺を共有していても合体して三角形になる場合は 合体三角形でまた別のグラフを作る (そもそも2Bの条件に引っかかる場合はそもそも合体三角形をなぜ分割したのだろう? ということはこの処理は要らない?) 3.グラフを共通のエッジを持つ2つのノードの組に分解する どうやるんだろう…市松模様のように塗れるのだろうか?
57 :
デフォルトの名無しさん :2008/12/10(水) 22:26:00
斜めの辺が存在しないので、□の方が扱いやすいという特殊事情です。 (ディグダグ2みたいな感じ) 三角形の分割から入るということですか
>>57 要は、水平線と垂直線だけ? 単に長方形に分割すればいいって話?
# だったら最初からそう書けよ。
… 四角形じゃなくてrectangleか 道理で
60 :
デフォルトの名無しさん :2008/12/10(水) 22:34:42
そうです。 言葉足らずですみません。
そもそも元は癖のないポリゴンか、それとも最初から 水平垂直矩形の組み合わせ(ドット絵の影絵?)なのか そこまで気になってきた
ドット絵の過去ゲーを今時の3Dライブラリ(DirectXか?)で再現しようとしていると見た。
63 :
デフォルトの名無しさん :2008/12/10(水) 22:54:47
必ず90度の角ができていて、立ち止まったり、引き返したりはないです
64 :
デフォルトの名無しさん :2008/12/10(水) 23:13:58
そんなところです。
映画トロンみたいな感じか
計算アルゴリズムIIスレはこのスレに併合されました
67 :
デフォルトの名無しさん :2009/01/19(月) 03:40:23
age
68 :
デフォルトの名無しさん :2009/01/19(月) 09:17:06
ユビキタス情報環境って便利そうな言葉があるんだが 総務省のu-Japan政策が余りにも現実離れしてる件
アルゴリズムIIスレで > 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万計算できたとき、何年で計算が終わるかだれかちゃんと計算してくれ
N=2, N=200, N=2^32とか具体的な数値が問題じゃないんでないの?
計算量がO(2^n)だったとき、計算機の能力が10倍になってもnはたかだか3増やせる程度というのがわかってないんだろうな。 だから指数時間かかるアルゴリズムは実装がどうこうよりもアルゴリズムとしてO(1.7^n)とかO(1.4^n)に緩和することが大事だということがわからないんだろう。
>>70 そうなんだが、アルゴ君はその具体的な数値を出してたから、アルゴ君なんだ。
何だアルゴ君て? 美味い棒か?
>>69 なーんにも経験したことないおまえの方が無能ってことだな。
>>75 簡単に説明すると、次世代Javaスレでアルゴリズムをアルゴという人があらわれ、アルゴリズムIIスレでアルゴという言葉を使う人が現れたと思ったら次世代Javaスレのときと同じように逆切れしてたのが、アルゴ君なんだ
みんな気付いてるかな? このスレには既にアルゴ君が居る事に
>>77 なんだかよく分からないが粘着してるのはおまえの方でないのか
キモイからそろそろ消えてくれないか?
平均情報量(エントロピー)って正の無限大に発散する?
高校の体育で アルゴリズム体操やらされてる 私が通りますよ
或るプログラムで今.NETのDictionaryクラスを使っているんですけど、 プログラム起動時にキーと値を読み込んだり終了時に書き出したりしないといけない上、 データが増えてきてメモリに収まらない程になってきたので、 ハードディスク上にデータを置いたままキーの検索などが行えるように改造しようとしています。 ググったらB+treeやB*treeや赤黒木なんかが見つかりましたが お勧めのアルゴリズムとその理由を教えてください。 ちなみにキーは8バイトのハッシュ値で、値は16バイトの構造体です。
1.データーベースソフトや同ライブラリを探してきて丸投げ 2.ハッシュ値の上位8ビット〜16ビットごと+キャッシュ、つまり257〜65万くらいに データを分割する。十分な性能を持つハッシュならキーは十分平均的に分散するはず なんて方法がさくっと浮かんだが、間違ってるかもしれない
87 :
デフォルトの名無しさん :2009/02/18(水) 15:17:49
俺なら確実に1.
ハッシュテーブルはどうだろう。 HDD上でのシーク回数が木構造よりも減るんじゃないかと。
つうか、Dictionaryクラスを継承して、値をHDDに置くようにすればいいんじゃね?
1以外にする強い理由が無いなら1だな。
前から気になっていたのですが、逆行列を求めるアルゴリズム(消去法など)と行列式を 求めるアルゴリズム(数学どおりの余因子による方法)ではどちらが実用的なんでしょうか。 行列式の方法が効率的だと、逆行列は余因子展開で求められてしまうんですが・・・
n次正則行列に対してガウスの消去法はO(n^3)、余因子展開はO(n^5)のような気がする
93 :
デフォルトの名無しさん :2009/02/20(金) 15:16:53
n^2.8位の計算量のアルゴリズムなかったっけ
>>91 余因子展開のときの行列式はどうやって計算するの?
>>93 逆行列の計算と行列積の計算は同じオーダーでできるので
現在最速の行列積がO(2^376)なので,これが現在最速.
ただし定数部分がでかすぎて実用的には使い物にならない.
>>94 余因子を使ったdet値の導出は、公式自体は線型代数の教科書に普通に載ってるんですが。
たぶん、主要部分はいれご(再帰)になるだけでプログラムはかなり簡単になるんじゃないかな。
ピボットとかの職人技法的なことを考えることなく、機械的なプログラムのほうがいいかなっと思ってまして。
n^5は一見遅いけど頑張ってもn^3, n^2なので激遅いってことじゃないみたいですね。
それに通常の使い方では、逆行列は一度計算して変数に入れておくことが多く、det値を再計算しないで再利用して使いまわすので、
やはりプログラムが簡単なアルゴ(笑)のほうが言いかなって思うんですけど。
64bit用のlock-free link-listで 一番良い実装ってどれですか?
>>96 64bit が atomic にロード/ストア出来る CPU か否かによって変わってこないか?
なので64ビットだからと言って特別なことは何もないと思う。
>>95 何を聞かれているか理解できてないみたいね.
(1) 逆行列を余因子行列を用いて表す方法がある.これには O(n^2) の行列式の計算が必要.
(2) 行列式の計算に余因子展開を用いるものがある.これには O(n!) の四則演算が必要.
(3) 行列式の計算は巧くやれば O(n^3) 以下でできる.逆行列を余因子行列で計算する方法が O(n^5) というのはこれを用いた場合.
ちなみに O(n^5) は十分遅いレベルで,実用的には使い物にならない.
逆行列の使いまわしも,数値線型計算では逆行列の形では陽に持たないのが常識で,LU分解の形で持つ.
話がそれて聞きたいこととずれてしまったのですが、行列式detの値を出すアルゴリズムはあるんでしょうか?が本題です。 もしあるなら、余因子展開で逆行列も高速に出ますよねってことです。 今やってるのは、行列式の値は逆行列(消去法などで)出すときに付随して出てきます。 detだけを出すのは、数学定義通り余因子による方法しか知らないので他にないんでしょうか。 といっても実際は線型打数のパッケージ使うので、アルゴリズムの練習程度なのでこだわってるわけじゃないんですが。
奥村先生の辞典でやってるんですけど、行列式をピンポイントで出すアルゴ(笑)は載ってませんでした。 次は従来の算法など数値計算用(ソルバー)と、文字列・グラフ理論なども含む探索用(ファインダー)とかで2冊ぐらいに分けて出してくれませんか? そろそろぼろぼろになってきたし、先生の本は解説は個人的な偏りがなくソースは素直で読みやすいから次も買うんで。
っていうか、逆行列そのものってほとんど必要ないよね
>>100 行列式を計算するアルゴリズムは存在する.
効率的なものと非効率的なものがあり,余因子展開によるものは非効率.
効率的なものでも,行列の積や逆行列よりも小さなオーダで行うことはできない.
逆行列と同じオーダでやるのは簡単で,行基本変形で上三角形にして(ガウス消去),
対角成分の積を取ればよい.これも行列式の定義の1つとしてよく知られている.
>>102 アルゴリズムでは直接求めたりはしないけどね。
>>103 やっぱり消去法とか三角行列になるんですか。参考になりました。
>>101 そこまで大規模な改訂は多分行われないので諦めよう.
現代的な項目を追加しようとか,ソースが汚いので直そうとか,
何度か意見は出てるけど,結構な大仕事で,人材不足だとさ.
行列の積が遅いのは結局 for と内積 a*x + b*y で掛け算と足し算を一度にやってるからだと思います。 もし掛け算のパートと足し算のパートを並列化できれば別の手法が考えられるし、作業配列を当然に仮定するので演算は前後演算に影響はなく、並列化どころかストリーム処理でもできそうな感じですかね。 そうすると、FFT乗算やカラツバ法とかと同等になるんじゃないでしょうか。といっても、パッと浮かんだ程度で専門でもないんで・・・
行列演算回路でググってみた。研究はいくつかされてるのね
>>106 FFTとかと同等ってどういう意味か分からないけれど,所謂Strassen系のアルゴリズムは
先に「後に使いまわせる和の項を作っておく」方法なので,その着眼点は良いよ.
ちなみに,昔から行列乗算の最適計算量は Θ(n^2) だろうと信じられていたんだけど,
2005年くらいの結果で,組合せ論と群論における2つの未解決予想を認めると,
実際に O(n^2) が達成できることが示されている.
着眼点というよりも、カラツバ法の発想そのものなんですが。 例えば多倍長で1−100桁目の加算と、これと同時に別スレッドで101−200桁目を計算できます。 したがって、掛け算パート用の配列、足し算パートの用の配列をいくつも用意して、スレッドで並列計算すればいいだけです。 配列やスレッド生成のコストとか、配列ではスレッドローカル変数、スレッドは予め行列演算用のスレッドをクラス定義しておけばいいので主要コストとは考えられません。 100x100以上だとしても、結局はやってること(演算)は画像のブレンドと同等になっていくので考え方次第ではストリーム処理が可能となり、よって「同等」です。100x100の行列は普通使わないんですけど。 シングルスレッドにこだわるなら、確かにO[n^5]は遅いんですが、実際使うのは10x10とかテイラー級数で15桁程度の多項式係数を求める程度(20x20程度)なんで、 マテマテカ使って式展開させて行列式と逆行列をハードコーディングでもいいかなって思います。 他にはO[n^5]でも10x10程度だと、今のPCリソースからすれば遅いって実感は全くないのでプログラミングが楽な再帰による方法(つまり余因子行列)でもたいして問題は生じないってところです。 プロジェクションなどの用途なら4x4程度だし、そもそもDirectXとかになるからソフトウェア上のアルゴリズムとは関係ありません。 ただ、逆行列と行列積は球根と数値計算の要なんで速いに越した事はないですけど。
>>109 で,君は何を主張したいの?
間違いだけ指摘しておくと,余因子展開で行列式を計算すると O(n!) 掛かる.
これは既に
>>99 ,
>>103 でも指摘済み.
相手とのレベル差が見えてないのは無残だな
確かにO[n!]は分かるんですが、それは数学上定義を愚直に一般化したアルゴリズムのときでしょ。 10x10程度まで良く使うなら式展開すればよいって書いてあるので、例えば2x2で行列式を展開した方法 a d - b c もO[n!]なんですけど、これ以外に他に方法はあるんですか?
>>112 どう式展開するつもりか知らないけど,行列 A の成分をすべて不定元だと思って
行列式を書き下したものをハードコーディングするつもりなら,止めたほうがいいよ.
項の数が O(n!) になるので,結局四則演算の回数は減ってないから.
>>113 やめたほうがいいじゃないくて、他に方法はないのかと聞いてるようですが?
そのようなアルゴリズムは知りませんと答えるのが正しいんじゃないですかね。
いつまでも計算量にこだわってるようじゃあなたの人生、先に進みませんよ。
何に牙剥いているのかわからないけど > PCリソースからすれば遅いって実感は全くない みたいな色々な主観を全部記述するほうがアホみたいだと思われ そんでもって,そんなの書いて人に聞くより試しにやってみればいいんじゃないの? 俺にはサッパリわからんが
実際に測ったことがないからないから > いつまでも計算量にこだわってるようじゃあなたの人生、先に進みませんよ。 みたいなことが言えるんだろうな
ハードコーディング(笑)しようが何しようがQR分解の方が速い件 せいぜいn=4か5までだろ、計算量的に考えて…
>>118 普通は行列式の計算はQR分解じゃなくてLU分解を使うことが多い気がする.
実際,LUのほうが精度的に良いケースが多いはずで,LAPACKはこちらを推奨している.
>>118 行列は結局n=4,5ぐらいが一番使うんだけど。
どうせ誰かが実装したアルゴリズムを使うだけで自分で実装なんかしないんだし、ハードコーディング(笑)でなにか問題でもあるのか?
普通は大学や研究所に依頼してやってもらうことが多いから、アルゴリズムを日々研究してるのなんかほんの数人しかいないよな。
なんとか自慢のアルゴリズムで特許とったところで、組み込みとかでブラックボックスにされちゃ確認のし様がないし。
>>117 言いたいことは分かるが、10マイクロ秒単位を気にして生きてかなければならない人生なんて哀れだな。その研究は幾らになるんだ?
>>121 ( ゚д゚) ・・・ (つд⊂)ゴシゴシ (;゚д゚) ・・・ (つд⊂)ゴシゴシゴシ
_, ._
(;゚ Д゚) …!?
>>120 誰かが実装した"ライブラリ"のtypo?
あと、ハードコーディングの意味は分かってる?
QRでもLUでもべた書きしたらいいじゃない
>>121 行列演算で10マイクロ秒って驚異だろ
何回呼ばれると思ってんだ
いや・・・ある意味・・・現実って厳しいかも・・・
>>120 > 行列は結局n=4,5ぐらいが一番使うんだけど。
ご冗談をw
>>121 オーダーの違いがマイクロ秒単位でしか現れないという認識が残念すぎる
オーダー1つ落としたおかげで実社会で使われるようになったアルゴリズムがどれだけあると思ってるんだ
アルゴ君だから仕方ないよw
>>123 行列の話などしてないし、誰かと勘違いしてないか?
ところで、最近 sin/cosを効率的に求める CORDIC というとんでもないアルゴリズムを知ったのですが、
いまではこれら超越関数は普通にテイラー展開することが多くてすでに見捨てられるようです。
http://en.wikipedia.org/wiki/CORDIC このような有用なアルゴリズムがあっても結局見捨てられてしまうわけで、どうして計算量にこだわるんですか?
上にもありましたが並列化など全く別のアプローチを取れば、一気に計算量が減らせることもあるわけで、
計算量を評価の指標とする考え方は全くずれてるに思うんですが。
例えば行列なら、Strassen法のように速度(計算量)を稼ぐために全く意味不明な実装になっているなら、 それは既にアルゴリズムというよりも粒度が大きいプログラム、というか逆行列を解くための専用のアプリケーションじゃないでしょうか。 つまりifなどの分岐だらけになるようなアルゴリズムは、既に汎用のアルゴリズムではなくてその問題に特化したただの「プログラム」じゃないでしょうか。 アルゴリズムの複雑な組み合わせとなっているような大きいアルゴリズム(プログラム)などに計算量による評価とか全く意味ないと思うのですが。 実装がしやすい理解がしやすいかどうかで評価するべきじゃないでしょうか。
アルゴリズム至上主義の人は、10年以上前の計算機性能を考えてみてはいかがでしょう。 当時、スパコンと呼ばれていた計算機は、現在のパソコン並か、それ以下です。 無駄な計算量の向上に時間を費やすよりも、使いやすくて読みやすいプログラムを書くことに時間をつかうべきですよね。 優れたアルゴリズムを考えても、すぐに廃れてしまうのです。 優れたプログラムを書けば10年後も使えるんです。
>>125 行列はn=2,3,4,5ぐらいが一番多いけど、他に何に使ってるの?
まさか測定点を全て通る多項式とか出してないよね。
あまりにひどい.勉強不足にも程があり,ほぼ全ての行が突っ込みどころだよ.
>>128 > いまではこれら超越関数は普通にテイラー展開することが多くてすでに見捨てられるようです。
現在でもCORDICが使われている場面はある.あなたが知らないだけ.
> このような有用なアルゴリズムがあっても結局見捨てられてしまうわけで、どうして計算量にこだわるんですか?
本当に,テイラー展開など比べて有用なのか評価したのかい?
特に,計算量はどういう測り方をして,どちらがどうなるのか分かってる?
> 並列化など全く別のアプローチを取れば、一気に計算量が減らせることもあるわけで、
並列計算機上の計算量にはそれなりの測り方があり,台数効果は計算量減少にカウントしない.
>>129 > 例えば行列なら、Strassen法のように速度(計算量)を稼ぐために全く意味不明な実装になっているなら、
Strassen程度で意味不明というのは力不足.
既にメジャーな数値計算ライブラリにおいてStrassen法は実装されており,
それまで時間が掛かりすぎていた問題が,解けるようになったという報告がある.
> それは既にアルゴリズムというよりも粒度が大きいプログラム、というか逆行列を解くための専用のアプリケーションじゃないでしょうか。
あなたの「アルゴリズム」と「プログラム」と「アプリケーション」の定義は何?
> アルゴリズムの複雑な組み合わせとなっているような大きいアルゴリズム(プログラム)などに計算量による評価とか全く意味ないと思うのですが。
なぜそう思うの?
> 実装がしやすい理解がしやすいかどうかで評価するべきじゃないでしょうか。
そういう評価があってもよいと思うけれど,これは定量的に量れるもの?
とりあえず、十分に並列化したLU分解かQR分解かそのへんの
計算時間(計算量ではなく)を見積もって
余因子並列をぶちのめせたら解決、のような気がしないでもない
と下書きしていたら
>>130 に噴いた、どういう宗教だろう
その考え方はアルゴリズムスレじゃなくてプログラムスレで論ずるべきだな
で、君は優れたプログラムを書いているのかね?
>>130 > 当時、スパコンと呼ばれていた計算機は、現在のパソコン並か、それ以下です。
> 無駄な計算量の向上に時間を費やすよりも、使いやすくて読みやすいプログラムを書くことに時間をつかうべきですよね。
例えば巡回セールスマン問題で,アルゴリズムを変えずに100倍のサイズの問題を
同じ時間で解こうと思ったら,計算機性能は何倍になればいいか知ってる?
何を言いたいのか不明だけど、PCで測るなら普通はミリ秒単位なわけで、ある特定の問題についての解法を自分で実装して、少しベンチとって終わりじゃないのか? 別にその報告や論文書くわけじゃないし。 おまえはそんなに凄い「世の中を変えちゃうような壮大な」研究でもしてるか?(脳内でw) 組み込みとか4ビット8ビットの貧弱CPU向けのアルゴリズム(というかすでに特化プルグラムだけど)の議論なら分かるけど、 PCやスパコンwとかだと、結局カッコいいこといってるけど実際は実装が面倒だからハードでごり押しじゃないの? 大金もらってるから面倒とか言うことは無いだろうけど、もしくは断念して誰かが作ったライブラリを使うとか。 つまり時代が流れて、ハードが進化したから、実社会で採用されたと考えられなくもない。 例えばインタプリタや中間コードは当時70年代は研究目的で全く見向きもされなかったけど、今は見直されたというよりもハードが進化したから普通に当たり前になってるとかのこと。
んでだな、
>>128-130 は同一人物だと思うけど、彼のほかの書き込みはどれだろう。
書き込みの同一人物判定が苦手な俺。
ちなみに俺は
>>92 >>107 >>122 >>133 で、身分は素人ね。
間違ったことかなり言ってしまってると思うけどごめん。
でも興味が出たんで、LU・QRの具体的な方法について勉強して
十分に並列化した場合の計算時間コストがどんなものか見積もってみたくなった。
これと余因子並列時間コストとの比較が焦点っぽいけど、それでいいのかな。
>>136 なるほど
139 :
デフォルトの名無しさん :2009/02/22(日) 14:53:39
アルゴリズムの件はな。 全体の速度をまず見るんだ。 arctanがいくら高速でも全体が速くならなければ意味なし。 実装してバグでるほうが問題。 使いたいやつが使えば良いんだ
140 :
デフォルトの名無しさん :2009/02/22(日) 15:01:41
あと、CORDICは、近年ハードウェア乗法が高速化された為に、効果が薄いみたいだぞ。 近年=十数年
141 :
デフォルトの名無しさん :2009/02/22(日) 15:04:42
>>132 あまりに酷いのはあんたの方だな。勉強不足とは失礼な奴だし、そもそも世の中のことを知らずに自分の研究だけに情熱を注ぐだけだろう。
あんたがどれほど勉強不足か、少し突っ込んで議論してみようか。
当然アルゴリズムなど君の専門分野を知ってるわけではないが、君は2chの分際で少々生意気だな。
自分の傲慢を原因として、人様を怒らせるもんじゃないし、そのうちIP抜いて不幸の手紙でも送ってやろうか?w
CORDICが使われてるのはあるだろうが、それではなぜCORICは廃れたんですか?
当時のハードで実用的なわけで、非常に有用なアルゴリズムのはずですよね?
テイラー展開と比べて有用かどうかを評価しましたが何か?
計算量云々について君に報告する必要はありませんが、いくらなら報告書買いますか?
・・と、お前の暇つぶしに付き合ってるほどヒマじゃないんだよね・・どうせお前なんか誰も相手してくれない禿げオッサンだろうしww
>>132 なんか一気に吹き出したって感じだな。このオッサンはww
なぜ?どうして?定義は何?とかどこの哲学版だよ
お花畑版ってのが2chにあるから、君は早いところそっちに引っ越した方がいいよw
>君は2chの分際で少々生意気だな。 >そのうちIP抜いて不幸の手紙でも送ってやろうか?w 受けるw もっとやれ
>>141 うわあ、礼儀飛び越えて中傷脅迫してるなり…
>>142 定義が大事な話してるのに、それを蔑ろにしては何も語れないかと
というわけでお花畑はあなたが行くべきっぽいんだが
145 :
デフォルトの名無しさん :2009/02/22(日) 15:21:21
Strassen程度とかも別に難しくはないけど、もっと理論的な裏づけ、例えばルンゲクッタ法みたいなのが欲しいよね。
奥村センセの本でも「複雑すぎるし、たいして性能向上ないから省略」とか書いてあるし。
>>132 君はアルゴリズムの深みにはまりすぎてんじゃないの?w
一番理解できないのは、
>それまで時間が掛かりすぎていた問題が,解けるようになったという報告がある.
それもO[n^3]やO[n^2]で影響が出るほどの行列(想定できないが10000x10000とか)のことでしょ。
実社会やビジネスではそんなの大きい行列は使いません。
ベンチャー企業や研究機関でもこの行列を必要とするところは考えにくく皆無なため、結局その報告は「これは実用的です」って言う宣伝(サクラ)じゃないの?
誰かが論文にあるサンプルコードどおりに実装してライブラリにすれば終わりだから別にStrassen法程度を否定するつもりはないけど、壮大な話を聞いて君は騙されちゃったんだねw
>>135 というか、このスレは同じ人がレスしてるっていう前提を持ってる時点であなたの妄想じゃないの?
たとえば「計算機性能は何倍になればいいか知ってる?」について知ってる・知らないと答えたところで、議論についてあなたに何か変化があるんですか?それはあなたの傲慢から生じるあなたの偏見じゃないですか?
よく読んでみると、「ハードが進化すると当時遅いっていわれてたアルゴリズムも遅くないよね」って書いてあるようですけど。
行列で計算量云々についての議論をしたとしてもn=1000なら、
8バイト*1000^2で8メガぐらいあるんですが、いくらO[n log[n]]となったとしても常時8メガの演算(それもメモリ間コピー含む)が実用的だと思いますか?
結局現在でもn=100ぐらいが実用の限界でありアルゴリズムの制約条件じゃないですかね。
つまりアルゴリズムの計算量の議論は既にお花畑なんでしょう。もっと実社会に即した評価の目をもってみてはいかがですか。
>>125 あのー
>>131 に答えてもらえないんですか?
どうせ線型代数の教科書も読んだことないんでしょうけどw
148 :
デフォルトの名無しさん :2009/02/22(日) 15:40:29
超文かくやつは吟味して短くおねがいします
アルゴリズムなんて、クヌースが本を書き始めたときにはもう終わっていたんですよ。
妄想ってのは肯定であれ否定であれ まじめに相手にする人がいると激しくなっていくものだ 霊が見えるって人もこのたぐい
謝れ! 数百次元の疎4階テンソルを扱ってる俺に謝れ!
152 :
デフォルトの名無しさん :2009/02/22(日) 15:48:54
ごめんなさい。
あの・・・どうでもいいんですが、計算量は定量的に見積もることが目的みたいですが、何を定量化してるんですか? 普通は速い・遅いは時間ですが、オーダは計算量で、式のステップ数というか計算回数とでもいいましょうかもしくはリストの個数とでもいましょうか どちらにしても計算量というのは時間ではないようなので、全く速い遅いの指標になってないんじゃないでしょうか。 そうすると、計算量が多いアルゴリズムO(n^3)でもスレの流れにあるような議論のように、速いとか実用とかは実際はアルゴリズム自体ではなくてハードによるってことだけなんですけど・・・ それでも観念しないのはアルゴリズム職人としてのポリシーか何かあるんですか?アルゴリズム研究とは一種の宗教なんですか?
とりあえず2次〜6次くらいまでの正則行列について 並列的な余因子展開で逆行列を求める速度と 並列的なQR分解または並列的なLU分解で逆行列を求める速度を それぞれ算出するんだ 一般的なCPUでの実測とベクトルプロセッサでの実測と四則演算等の段数両方考察するといいぞ ちなみに俺に任せるとQR分解の勉強からはじめなければならないから 演算の段数数えるだけでたぶん一ヶ月はかかる、ひゃほーい
アルゴ君絶好調だな
>>145-147 構造計算や大規模偏微分方程式に使うFEMのソルバについて軽く調べてみるといいよ
nが数万とかの(疎)行列の固有値救解や連立方程式計算をすることになるから
んで、その為のスカイライン法とか、マルチフロンタル法とか、
効率のいいアルゴリズムを見つけた上で更に並列計算に持っていこうとするんだよ
やってることは結局のところ全てLU分解(正確にはコレスキー分解)なんだけどね
そういう行列計算の世界もあるんですが、知らなかっただけですよね
追記すると、FEMじゃなくてBEMなら疎行列じゃなくて密行列になるので お望み通り、「nが数万の行列」になるね FEMやらBEMやらがビジネス(笑)で実用化されてないとはまさか言われないだろうしね
アルゴには理解も実装も何もかも無理だって随分前に俺が指摘したじゃん…。
>>145 Googleのページランクの計算は結局のところ行列の計算なんだけど,
どれくらいのサイズの行列を使ってるか知ってるかい?
数値計算の分野では 10000×10000なんて「十分小さい」行列だよ.
で、実際問題余因子展開によるクラーメルの公式って並列化できるのか? 行列をプロセッサ数に効率よく分割できなくね?
>>160 シッ!そういう言い方すると
>議論についてあなたに何か変化があるんですか?それはあなたの傲慢から生じるあなたの偏見じゃないですか?
とか言われちゃうよ。どうせ知らないのにね。
で、どんぐらいなの?
>>162 凄い勢いでデータが増えているので今現在ではもっと増えてるかもしれないけど,
2008年の末で大体数百億くらい.ちなみに2002年くらいで数十億だった.
ただし,もちろん疎行列で,非ゼロ成分もこのオーダーくらいしか存在しない.
>>146 > よく読んでみると、「ハードが進化すると当時遅いっていわれてたアルゴリズムも遅くないよね」って書いてあるようですけど。
逆だ逆w 具体的に何倍になるか答えてみろよw
165 :
デフォルトの名無しさん :2009/02/23(月) 01:31:58
8ビット時代のメモリが4kBくらいでCPU駆動周波数が 2MHzの頃のアルゴリズムを後生大事にしてる愚か者っているよなw。
超大量にループぶん回す必要のある箇所は 今でも極限までアルゴリズムや実装をチューンナップするものだ もっともプロセッサの配線やライブラリと化したものが多いだろうけど
>>165 > 8ビット時代のメモリが4kBくらいでCPU駆動周波数が
> 2MHzの頃のアルゴリズムを後生大事にしてる愚か者っているよなw。
誤字?
×アルゴリズム
○プログラム
>>165 おまえはアルゴリズムの評価に コンニチハ セカイ みたいな文字列の出力まで考慮するタイプの人間なのか
花壇の叩き台としてイージーに計算段数を考えてみた #まじめに読まないこと推奨のような気がしてきた (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段があれば逆行列は求まる とりあえずべらぼうに回路の面積食いそうな点とか 検証が怖いので考えない方向。 何で俺、こんな時間にこんなこと考えてるんだろ。 そして絶対どっか豪快に間違えてるぜ、眠いし。
LU分解による逆行列 3次正則行列を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の右上隅が一番、そして派手に段数食いそう。
>>160 それって、よくわからんけどグラフ理論にある隣接行列のことじゃないか?
要素が1か0とかほとんど固定パターンのやつ。それを愚直に演算してるとでも思ってんのかよ。
「行列サイズは数億になるんだ!」とか偉そうにするな。お前は一生知ったかのカス野郎のくせにww
>>171 要素が0と1じゃ情報少なすぎだろjk
おまえの頭はどこまで真っ直ぐなんだよ・・・
>>156-157 そういのは研究所や専門の工務店がやるもんで、あまりビジネス(商売)って感じではないですね。
今ではベンチャーが調査の受注を受けてレポートして報酬を受けるわけで、その何とか法のアルゴリズムは、
汎用(一般用)というよりもその分野に特化したアルゴリズムなんじゃないですか?
この算法は、「キーボードのキーピッチは13-17が最適解でありこのれを求めるアルゴリズムである」といわれても、
「そんなの知らんわ!」じゃないですかね。
つまりそういう特化した分野のアルゴリズムを出してきたり、その分野の計算量がどうとか全く意味がない議論です。
大事なことなのでもう一度上げておきますが、1000^2*sizeof (double)サイズの計算を常時必要とするなら、800万画素の画像を常時フィルター処理しているのと同じですよ。
そもそもここでいう「高速」とは時間ではなくて計算回数が少ない(1000^2か1000^2.78)ってことであって、体感では2−3秒は待たされることかわりありません。
行列の積について言えば、ユーザー入力や初期値まちを求めるifなどの分岐がアルゴリズムにないため(単純な演算上は定数の内積なので)、
ストリーム・プロセッサ用のアルゴリズムにすれば一気に変わると思うんですけど、それはソフトウェア上の計算量(アルゴリズム)とは関係なく、ハードの機能によるものです。
どうしてもアルゴリズムや計算量にこだわるなら、数学上の証明や理論的裏付け(積分シンプソン法などのように)をちゃんと示してもらえませんか?それがないのに、ただ「やはくなった!」というのは学問じゃないでしょう。
174 :
デフォルトの名無しさん :2009/02/23(月) 05:51:51
>>156 たぶん極端に言ってみただけだと思うんですけど、そんなにパラメータ(n=10000以上とか)必要なんですか?
もっと細かく区分にして各区画を評価すれば足りると思うんですけど。最終的には各区分の計算結果を「人間」が評価するんじゃないですかね?
それとも、その構造や系の全要素の変化を評価したりする、「神にでもなった」つもりのシミュレーションなんでしょうか?
どちらにしてもPCでやるというよりは、PCを並列にしたりより特化した計算機でやるんでしょうし、汎用的なアルゴリズムとは関係なく、その問題に特化したアルゴリズムことを話されても興味ありません。(実装が複雑でそのCPU用のコールだらけなので)
175 :
デフォルトの名無しさん :2009/02/23(月) 05:58:54
>>173-174 よくわからないけど,ユーザ体感のサービスのクオリティと,サービス時間を比べられても困るという点で,一切交じり合う気がないんですねわかります
176 :
デフォルトの名無しさん :2009/02/23(月) 06:31:03
さすがに朝からしゃぶしゃぶはないわ
自分が使わないから他でも使われないという思い込みはアルゴ君の特徴 もう放っておけ
179 :
デフォルトの名無しさん :2009/02/23(月) 07:20:00
>>172 誰が書いたか知らないけど、行列で言えばn=3万つまり、
30000^2 * 8バイトは6ギガで既に32ビットのメモリアクセスの限界を超えてるってことは分かってる?
>>160 で戯言が書いてあったけど、「小さい行列」とか知ったかもそれぐらいにした方がいいよ。
アルゴリズムが200^3か200^2かなんて実質関係ないし。
2次関数のグラフで見てもその値は両者ともはるか上のほうでしょ。
結局そのアルゴwで解を得られるかどうかでしかないんじゃないのかな…
計算量を指標とすることで、学問・理論とは関係ないお花畑の議論に持ち込まれちゃって騙されちゃってるんだろうなwww考え直した方がいいよ
じゃあお前はどんなに大きな配列でも バブルソートでソートしとけや
メモリに載んないから色々工夫が必要なんだよ。 その都度再計算したり、0でない要素だけ保存したり、ディスクに保存したり。
というか6ギガのメモリを使う行列の演算について、アルゴリズムが早い遅いとか全く無意味な議論だよね。 そもそも、普通に買える計算機では1000x1000の行列なんかは普通はOSに叱られて作れないし、オーダーでそれぞれのアルゴリズムを比較するって言う思考自体が理想論なんだろう。 6ギガの配列は32ビット環境では確保できないし、「6ギガ^3 と 6ギガ^2 では計算効率が全然違うんです!」とか夢の話をされてもな・・・(笑)
1000x1000の行列が作れなかったら 画面のキャプチャもできないよwwww
バブルソートは遅いけど、遅いってことが問題になることは無い。もう一回アルゴリズムの目的とはなんであったかを勉強したほうがいいんじゃないかと思う。 速いか遅いかではないよ。 君だって、文字列検索とか結局は線型サーチ使うでしょ
そりゃデータによってアルゴリズムは使い分けるさね。 文字列検索が遅いと感じる大きさのデータを扱う場合は 他のアルゴリズムを使う事を検討するさ。
>>184 じゃあ Google も線形サーチを使えば満足するんだねw
突っ込みどころしかなくて吹くわー。トヨタ他の車の強度シミュレーションが数百節点でできるかよ。て言うか、800万画素のフィルタリングなんてデジカメのASICレベルの話じゃん。 アルゴリズムの話で何で評価基準ガユーザビリティなんだw
1000×1000が巨大とかwww たった8メガwww
>>169-170 仮定は「無限に大きな回路を用いる」ことかな?
行列式をハードコーディングした際の計算段数は大体
log(項の長さ) + log(項の数)で, n log n くらい.
LU分解(ガウス消去)による方法の計算段数は,
各行ごとの掃き出しが 3 段(並列的に b - (a/u) v を計算)なので 3n くらい.
b - (a/u) v で計算したものを次々と使いまわすことで,段数の爆発を抑止してる.
>>182 > 1000x1000の行列なんかは普通はOSに叱られて作れないし
どんなOSw
>>182 それ書いたの自分だけど、メモリマップドファイル知らないの?グーグル先生に聞いて。
で、ディスクからの読み出しは線形時間の処理で、行列の処理はO(n^3)だから、行列がでかいほどアルゴリズムの改善が優位になるんだけど。
むしろ、小サイズ行列ってどこに使われるか例が欲しい。同次変換以外には?
192 :
デフォルトの名無しさん :2009/02/23(月) 08:31:17
HDDにデータおいて、固定長なら値取り出せるだろ
193 :
191 :2009/02/23(月) 08:43:35
ん、違うな。 「数千数万行の行列を使うのはそういう需要があるから」ってのが答えなのか。PCやスパコンの記憶容量の発達(と十分な処理速度)でそれが近年ようやく現実的になっただけで。
>>189 ありがとうございます、やっぱり私のLU分解の理解おかしいですよね
あとご指摘の通りハードウェア実装なら回路の広さはべらぼうに必要でしょう
ガウスの消去法でやります
(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分解のとき何の理解を間違えてるんだろう…
>>169 と
>>194 の計算段数を比較すると
クラメール(てかクラーメルじゃないやん)の公式が優位なのは
4次以下の行列に対してで、5次以上の行列に対しては
ガウスの消去法のほうが有利
ただもちろん加減乗除それぞれで速度違いそうなところとか
一番致命的と思われるのは、そんなだだっ広い贅沢な回路できるかーいなところ
とはいえガウスの消去法ならパイプライン方式諦めてレジスタ使うようにすれば
異なった段数で回路使いまわしできそうなんで…というかたぶんまんま
ベクタープロセッサが求められた理由の多くをこれが占めてるような
という夢をみたので、ここから壮絶な袋叩きが始まるか華麗にスルーされるのであった
いや俺は何を言っているんだ クラメールの公式で行列式や余因子の値求めるときに ガウスの消去法が効率的な場合はそっち使えばいいじゃないか
…ガウスの消去法で行列式の素を計算した時点で 逆行列まであとたった2段やん… 一方、行列式の素はn項あるんで、掛け合わせるだけでlog(2)nはかかるし そして余因子に掛け合わせる1段も必要 余因子による行列式計算の段数が nが1増えるごとにlog n のペースで増えてしまう余因子展開法と nが1増えるごとに2のペースでしか増えない上に逆行列まであと2段まで迫る ガウスの消去法、か。
悪いけど10000の書き間違えなんだけど・・ 1000x1000の行列の書き間違いのレベルだとやっとついてこれると思ったのか、反応するゴミが多いなっておもった・・・・ 2chでそれもこんな糞スレでゴミのあいてしてもね・・・
というか、書き忘れたけど1000の行列よりもグラフ理論のこと知らないと思ってたのか、隣接行列があるからn=10000は「小さい行列だ!」とか言っちゃた奴はゴミでしょ。 そういうこと言っちゃうと後々責任問題になるから、もしまっとうに生きていきたいなら、自分の発言には責任もっていたほうがいいよ。あまり世の中のこと知らないだろうけど、警察とか怖いからw
200 :
デフォルトの名無しさん :2009/02/23(月) 15:36:13
名前: 92他 ◆DRdCZDy4PY [sage] うざいだけどチラシの裏でやってくんない?
201 :
デフォルトの名無しさん :2009/02/23(月) 15:47:57
>>191 >列の処理は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 みたく勘違いしちゃうゴミが多いけど、「速くなった」「バブルソートは遅い」などの表現はアルゴリズム評価の参考にすらならない。
結局は実際に動かして体感で判断するんだろ。これが計算量のマジックだけど、何の指標なんだかちゃんと理解し解かないとな。
>>201 > n=100の行列では(100^2)^3で
何で n^6 してるの?w
>>201 > 関数の形(指数関数)
n^2 とか n^2.22 とか n^3.12 って指数関数なの?
だからさ、計算量なんかどうでもいいけど、実装が簡単なもの、メンテナンスしやすいもの、図を書けば誰でも理解できるような「算法」にするべきじゃないか? 多少複雑なアルゴリズムなら、たいては他のアルゴリズムの組み合わせでしかないし、そうでないなら数学による証明などの理論的裏づけがないと全く理解できない。 アルゴリズムが速いかどうかなんかどうでもよくて、解が出ればいいよ。それよりも理論的な不備や実装によるバグ探しの方が数十倍恐ろしい。
>>204 最悪のアルゴリズムでもそこそこ速い小さな問題も数多く
そういう場面では多少遅くてもバグの少ない実装を心がけるべきという主張はわかる
が
全ての問題がそうとは限らない
巨大な行列の計算なんかはモロにそういうチューンアップが問題になるケースでしょ、と
20兆年かかる計算を2秒にするアルゴリズムを捨てることはできない。
>>201 > 950ミリ秒が95ビリ秒になればそれは速い
えー
209 :
デフォルトの名無しさん :2009/02/23(月) 20:36:44
コムソートって本当に速いの?
「速くは無い」という結論が出てるよ。
ちょーはやいよ
>>201 指数時間じゃなくて多項式時間な。根本から間違ってるぞ。
あと、形が問題になるのはnが大きいと言う仮定をおくから。お前はnが大きい方がいいのか小さい方がいいのかどっちなんだ。
>950ミリ秒が95ビリ秒になればそれは速いが、この「速度」による評価はアルゴリズムではなくて、ハードによるんじゃなかったか?
ハードを変えて実行速度を10倍にするのがどれだけ大変だと思ってんだ
問題の評価は同ハードでやるに決まってんだろアホ
コムソートが終わる時間ってどうやって見積もればいい?
リソースを全く消費しないという点で考慮に値するよ>コム(r
安定じゃないと使いにくいよね
アルゴ君、元気だな。
>>205 そんないきり立って主張するのもいいが、バグのほうが怖いな。
ちゃんと動いてたのに2年後に動かなくてバグ探しとかどうする?
そのアルゴリズムの仕様や制約が原因で。
今あるハード以上のことを考えて、限界を突破しようと、人より先に行こうとしても苦難の道なだけじゃないか?
それで報酬はいくらもらえるんだろう。windows95の時代はメモリ16-32が標準だったけど、今じゃハードの進化は10倍どころじゃないよな…
所詮ソフトウェア上での実装でしかなく上にはハードによる制約があるから、そんなにこだわっちゃうとストールマンみたいな一種の宗教になっちゃうよ。
オレはFF10で「全てを超えしもの」をもらったけど、結構大変だったぞw
こいつ高校生か中学生?
220 :
デフォルトの名無しさん :2009/02/24(火) 03:29:10
>>212 なんかカッコつけて書いてるようですけど、多項式と関数の違いを区別できてますか?
「多項式の形が重要だ!」とは普通言いませんよね?
あなたは関数との違いを書きたいようですが、多項式というからには「+」による連結を想定してるんですか?
根本的に間違ってるのはあなたの脳味噌の方でしょう。あなたの脳味噌はとっても臭そうですけど。
>>218 ストールマン程度で宗教なら、アンドリュー・ワイルズとかペレルマンとかどう評価するんだろう…
>>221 書き直し
ストールマンの行列の積の計算の省力方法程度で宗教なら
アンドリュー・ワイルズのフェルマー最終定理の証明とか
ペレルマンのポアンカレ問題解決とかどう評価するんだろう…
223 :
デフォルトの名無しさん :2009/02/24(火) 03:36:17
名前: 92他 ◆DRdCZDy4PY [sage] なんでこいつはこんな時間にこんな糞スレに張り付いてるんだ? どうせニートだろうし。一回切腹してみた方がいいんじゃね?w
>>222 評価?おまえには一生謎のままの方がよさそうだな。一生悩んで自分なりのアルゴを出してみたらどうよ?アルゴ君w
アルゴ君って俺のことだったのか! 丸っきり気付かんかったぞ
>>212 根本的に間違ってるのはお前の方じゃないの?
nに何かの仮定おくなら、nは定数であってn^xの指数関数という考えのはずが、お前の文章ではそれを「多項式」と書いてあるけど。
多項式というのは、2^x, 3^xではなくて、x^2 + x^3とかのx^nじゃないの?それもこの指数は普通は正数限定で、多項式ではn^3.11などありえない。
それに大きいという仮定ってのがまた理論的な表現ではないが、例えば行列なら5x5以上は既に大きいと言われて否定できないが、お前の感覚ではまだ小さいのか?
例えば5x5はxmmレジスタに入らない。
オーダーのマジックとはこういう風に、お前の感覚を麻痺させちゃうんだろう。これもまた宗教だろうな。
お前は早いところ自分の巣に帰ったほうがよさそうだ。
227 :
デフォルトの名無しさん :2009/02/24(火) 03:53:57
>>212 ださ
おまえは早く巣に戻ってさ、もう巣から出てくんなよww
ダサいからw
228 :
デフォルトの名無しさん :2009/02/24(火) 04:40:21
釣りえさもつけずに釣りとな
>>222 ブルーバックスを読みすぎると、あなたのように頭がおかしくなっちゃうんで今度から気をつけたほうがいいですよ。
俺はいいけど、ブルーバックスへの中傷じゃね?
>>212 同ハードで評価するのは当然ですけど、その報告書や論文・ベンチマークで使ったハードが、スパコンとか店で普通に買えないようなハードだと全く意味ないってことじゃないの?
それに、ベンチのプログラムなんかいくらでもそのアルゴリズムが有利になるようなコードを書くことができるんだけど・・
ハードの進化も
>>218 にあるようにとんでもないし、今のゆとり世代にwindows3.1や95の時代でも「この性能は旧式のスパコンと同等だ!」とか宣伝されてたなんて信じられないだろう。
脳味噌ゆるゆるの奴はすぐ引っかかるみたいだけど、ま、騙されないようにしてよww
>>231 なんで最初と最後に言ってる事がちがうの?バカなの?
>>232 バカはおまえだろw
早く働いた方がいいと思うよ
まずは
>>212 が妄想で言ってないというなら、「大きい」というのはどれぐらいからなのか、
実行速度を10倍にするのがどれほど大変なのか明らかにしてくれないか?
そうじゃないならおまえの妄想か、創価学会への勧誘にしか見えんよw
おまえが高校生で、ブルーバックス読みすぎて頭おかしくされちゃってるっていうなら見逃してやるけどww
>>231 > それに、ベンチのプログラムなんかいくらでもそのアルゴリズムが有利になるようなコードを書くことができるんだけど・・
なんて言っちゃってる辺りは確かにバカに思うよ
>>237 そんなこといってる余裕があるなら早いところハロワで職探せ。おまえのお母さんは泣いてるぞ。
239 :
デフォルトの名無しさん :2009/02/24(火) 06:12:30
公務員のほとんどは基本年収500万で、住宅手当とかつけて700万以上なんだよね。 どっかの市長がブログで公務員給料を公開してた。 いくら難しい勉強しても、いくら資格をいっぱい取っても年収がこれにも満たない底辺(ITドカタ)は多いだろ。 民間よりも公僕のはずの公務員の方が給料多いってのはおかしな話だけどねぇ こんな糞スレで傷の舐めあいなんかしてないで早く働いたほうがいいんじゃないの?ww
とニートが申しております。
241 :
デフォルトの名無しさん :2009/02/24(火) 06:29:52
公務員はこうやって高年収だから実際はニートとかIT派遣とかの生活なんてどうでもいいんだろうな。
政治家が悪いというよりも公務員のニート・派遣への偏見の方が問題は大きそうだ。
基本給は年収100万!のバイトとか年収300万の派遣ぐらいにして、後は成果主義なら公務員も世の中の厳しさを気がつくかもな。
>>222 おまえは年収100万の分際で、「フェルマーの定理バンザイ!」とか哀れな奴だ・・・
>>240 ニートの君には実感沸かないだろうけど、早いところ仕事探して世の中に出ればこれに実感が湧くようになるんじゃないか?かなり大問題だよ。
>とニートが申しております。 こんな単発レスしか出来ないゴミに何言っても無理。 一生2chと一緒に生きていくって宣言してるようなもんだろw 確かにこういうのは自民党が言ってたけど自業自得だよな・・・自己責任だったか?w
アルゴ君大活躍だなあ。なんか詳しそうな人が数人居るのに勿体無い。
↑やーい無職無職wおれと同じだw
247 :
212 :2009/02/24(火) 08:01:31
色々アンカついてて面倒だな。 多項式時間、指数時間、ランダウの記号の意味ぐらい調べてきてからもう一度釣りに来てくれ。 この流れでnなんて問題の大きさ以外に何があるよ…。
アルゴ君ってのは誰だか知らんけど。 このスレの奴らは、各種アルゴリズムに詳しいだけで自分でアルゴリズムを発案するようなタイプではないな。 いつまでも計算量による評価を過信してばかりで、ただの安月給のオッサン(それもアルゴリズムは趣味なんです!とか)でしかないんじゃないかな。 その詳しそうな人という奴らの書き込みをよく見ると、ググればすぐ出てくるようなことを少し難しく偉そうに言ってるだけってことに気がつく。 各種アルゴリズムを知っていても、ここのオッサンも所詮はハードでごり押ししかできなだろうしなぁ・・・ 「行列式のハードコーディングはO[n!]だから絶対ダメ!」とか 「O[n^5]のアルゴリズムは遅くて使い物にならないから使ってはだめだ!」とかアホだろ。 もしちゃんと勉強してる奴とか専門家ならこういう表現は使わない。 信用すのは勝手だけど、n=無限大みたいな何の具体例もないお花畑の説明は、上のレスには層化がどうとかあるけど宗教の勧誘と同じ
>>248 計算量評価でなく、段数評価やってみたんだけど…
クラメールの公式のハードコードなんてわかりやすさもメンテ性も0だと思いますが 如何お考えでしょうか
>>245 おまえさ、アルゴ君ってだれよ?ウザイよ。
グラフ理論とかNP困難とかに関心持ってるんだろうけど、おまえの脳味噌じゃ時間の無駄だから止めとけ。
そもそも関数とか多項式の違いとか分かってないんだろ。
そのていどの奴がアルゴリズムに関心持っちゃうのはブルーバックス(もしくはウィキ)の読みすぎ。はよ働けw
>>250 おまえがこのスレで偉そうにしてる奴か。2chごときでいきがる。
2chばっかりみてると研究所のPCにウイルスが入しちゃうかもな。
研究所のPCから2chへのアクセスには最新の注意をしておいた方がいいぞ
>>253 おまえがアルゴ君か。2chのやりすぎで頭おかしくなっちゃってんだろ。
アルゴ君探検隊の大冒険
257 :
デフォルトの名無しさん :2009/02/24(火) 09:58:05
>>250 専門家ということですけど、アルゴリズムの分類が仕事でしょ。
分類以外に他に仕事あるんですか?
「例えば行列式は数学的定義どおりにコーディングしたらダメ」って言うのは、いいすぎですよ。
あなたがだれか知りませんが、計算量と実測速度の違いぐらい分かってますか?
それで、本当に専門家を名乗るつもりなんですかね…
>>257 他のスレでフルボッコされてこのスレを住処にしてんだから悪口言っちゃダメ
このスレが一番の楽しみなんだしとっても可哀想な人なんだから、お山の大将が気に食わなくても黙っててあげて
自演乙w
260 :
デフォルトの名無しさん :2009/02/24(火) 10:40:39
>>257 ニートのようですが、何かお仕事はお持ちなのでしょうか?
(ry
>>250 あれ?レスないね。
「準教授」とか言ってみたけど名前負けだよねw
>>226 「それもこの指数は普通は正数限定で、多項式ではn^3.11などありえない。」wwww
アルゴ君ってここまでバカだったのか
はぁ?
アルゴ君、つっこまれても意味がわかてないから、はぁ?としか返せないのか
ストールマンを別人と勘違いしてた…
あんまり他所で暴れてやるなよ
268 :
デフォルトの名無しさん :2009/03/01(日) 01:31:23
マリオRPGにあるマジカルスイッチのようなパズルを解くアルゴリズムを考えているのですが、誰か教えてください。
考えているんですか。 では考えてください。
>>268 そのパズルを知らないし、○○のような〜では尚更わからないよ。
誰が読んでも理解できるようにルールを書けるかな?
271 :
268 :2009/03/01(日) 02:23:52
ルールは 5×5にボタンが配置されていて、 ボタンを押すと自身とその四方のボタンが押される。 周りにボタンが無い場合、そこは無視して考える。 すべてのボタンが押された状態になるとクリア。 これを解くアルゴリズムを考えたい。 (例:一番左上のボタンを押した場合) ■■□□□ ■□□□□ □□□□□ ■押された状態 …略… □押されていない状態 僕の考えでは 一回で押せる可能な数は、3,4,5個なので 3*X + 4*Y + 5*Z = 25(5*5) のように最適なX,Y,Zの組み合わせを考えて、無駄なくボタンを押せばいいのではと考えている。 ここでは5×5での場合を考えているが、任意の個数でも可能なアルゴリズムを考えたい。よろしくお願いします。
>>271 オレ流解法のヒント:
最上段の押すパターンAを仮定 → N段目を■■■…■にするようN+1段目で調整
→ 最下段にパターンBがあらわれる
ので、AとBの組み合わせを幾つか調べておく
ちょうど昨日スーパーマリオRPG(VC)をやってて、それをやったよ ちなみに ・プレイヤーが押すことが出来るのは、押されてないスイッチだけ ・スイッチを押すと、上下左右の4つのスイッチの状態が反転する ・全部押した状態にしたら勝ち ~~~~~
>>273 反転するのか。てっきり押したものはひっくり返らないのかと思って、
それならほぼ自明な解があるかなと思ってた。
>>271 >>273 のルールなら,多項式時間で解けるね.方針は次の (1), (2) による.
(1)「押されているスイッチも押せる」というように問題を緩和して解く.
これを解くと,最終的に押すべきスイッチの一覧が得られる.
(2) 押すべきスイッチ一覧を適当な順番で押していく.
(1) はライツアウトの変種なので,連立方程式を立てて解けばいい.
詳しくは「ライツアウト 連立方程式」あたりで検索すれば分かる.
(2) は,押し方によっては手詰まりになるのが怖いのだけれど、
実はどんな順番で押していっても,手詰まりにならないことが証明できる.
よって (1) で作った一覧から押せるものを見つけて押す,を繰り返せばよい.
解を知っているなら簡単なんだけどな 解を知っていなければn×nの一時方程式(ただし変数は全部bool型)になるかな? 踏まれた状態: 1 0 0 0 0 1 0 0 0 を考えると,床の状態は 1 1 1 1 1 1 0 0 1 ってなるから…わからん アルゴ君たのんだ
>>276 アルゴ君じゃなくてごめんね.
マス目に対応する 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 個の条件式を適当な方法で解けばよい.
うひー 私をもっと踏みつけて〜
279 :
268 :2009/03/01(日) 11:24:23
25x25正方行列の対角化問題に帰着するのか アルゴ君のコメントが欲しいな
アルゴ君じゃないけど、mod 2でしかないから行列(というか実数量)でやるほどでもない。 そのアルゴのルールだとグラフ理論が一番効果あるんじゃないか?
282 :
268 :2009/03/01(日) 23:20:37
ライツアウトで解けた。 順番は関係ないらしい。 後は連立方程式を解くアルゴリズムを実装するだけ みんなサンクス
>>280 対角化ではなく,連立一次方程式だよ.
mod 2の計算だと対角化問題は解けない.
>>281 mod 2の計算をわざわざ実数ではやらないよ.
グラフ理論って,具体的には何?
驚異のライツアウト解法ロジックいまごろ知った そういうことか
>>281 素数位数の有限体 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 上での連立方程式だから単純だがな、
こういう場合に実数を持ち出さなくて済むということは知っておくといいぞ
データ構造・アルゴリズムに関する問題なのですが。どなたかお手伝いお願いします スレチなら申し訳ないですが誘導お願いします。長すぎるみたいなので分割投下させていただきます ---------------------------------------------------------------------------------- 以下の事柄に注意し各問題に答えなさい ・与えられた文字列等のデータについては問題の指示に合うように事前処理が必要な場合がある。 ・木等を表記する際に、 ダミー接点であるheadとz(外部接点)は表記する必要はない。 ・同一キーについては後から挿入される方を大きいものとして扱う。 1.文字列「ASORTINGBYPOLYPHASEMERGINGEXAMPLE」に対し、3ウェイ併合を用いたポリフェーズ法による外部整列を行うこととする。 このとき、整列が始まる直前のランが配置されたテープの姿を現しなさい 条件)・主記憶の容量は文字3文字分とする。 ・使用できる磁気テープは4本。 2.文字列「BINARYSEARCHQUESTION」について 1)「H」を2分探索で行うとキーの比較は何回必要か。 2)内装探索を行った場合はどうか。 ただし、比較対象文字が確定しない(文字を示すポインタアドレスが整数でない)場合は ポインタアドレスを切り上げ後方の文字を比較対照とせよ。 ソートしたもの「AABCEEHIINNOPQRSSTUY」 3.文字列「BINARYTREESEARCH」について赤黒木を作成せよ。なお、黒リンクは1本線、赤リンクは2重線で表記せよ。
4.2重ハッシュ法を用いて、サイズ19の空の表に「HASHINGEXAMPLE」を順に挿入した結果得られるハッシュ表の内容を示せ。 なお、ハッシュ関数は 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つずつ 格納できるものとする ---------------------------------------------------------------------------------- 連投・長文お目汚し本当に失礼しました
ワロタ 少しは自分で考えろ
>>280 線形代数でライツアウト
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通りの解がある。
ORじゃなくてXORだった
293 :
デフォルトの名無しさん :2009/03/19(木) 20:46:38
アッカーマン関数というネタか?
トライ木 特に基数木なんかの扱いに強い本ってありますか? 5ページぐらいでさらっと流されてもよーわからんのです 頭の悪い子ですいません
296 :
デフォルトの名無しさん :2009/04/05(日) 03:25:03
A* search
双方向リストのprev(前)、next(次)のポインタってしごく当たり前なんですが どうしても、前後のポインタが2個ずつ必要になり前1、前2、次1、次2のポインタを持たせた、ダブル双方向リストなるものを考えいるのですが、こういうアルゴリズムって、皆さん使ったことありますか?
前2と次2って何? node->prev->prevとnode->next->nextってこと?
>>299 >>298 です、どうぞよろしく
node->prevlhs
node->prevrhs
node->taillhs
node->tailrhs
こういうイメージを描いていましたが、この方が良い気もします
node->prev
node->taillhs
node->tailrhs
if(true) node->taillhs else node->tailrhs if句で、次のノードを選択するような、振る舞いにしたいので、入力に2つのポインタ 出力に二つのポインタが必要なのですが、いかがなものでしょう? (入力側は1つでもいけそうです)
>>300 なんで毎回前2つと次2つが必要なの
スキップリストでいいじゃん
なんでなんでなんで?
言えよコラ
>>302 そうなんです、毎回前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*);
};
ようは、ダイナミックバインドに対応した、双方向リストが欲しいんですよね、変ですか?
変です
訂正です ×このように、コンストラクタで生成しようと思ってるんですが ○または、コンストラクタで生成しようと思ってるんですが
>>303 どんなデータ扱うために
そんな変体データ構造必要なの?
>>303 です
▲if(a == 1)
┃・処理1
┣
┃・処理2
▼
このような擬似言語ってしってますよね? これをフローチャートに展開しようと
思ったんですが、最初、2次元のvector配列で考えたんだけど、単純なif旬やfor旬などは
簡単に出来たんだけど、ネストが深くなったり、構文が複雑になると、
頭がごちゃごちゃになり、分からなくなって、混乱しました、
そこでリストポインターで、連結して、動的に連結させたほうが、
すっきり理解できると思って、思い浮かんだ発想なんです、
他に、良いアイデアがあれば教えて欲しいのですが。
そんな擬似言語たくさんあるからどれのことかわからんが、 そういうのは普通は多分木でやるもんでしょ。
そっか、木の方が簡単ですね、こんな感じでいけそうだね、サンクスでした。 struct node { const char* name; int depth; struct node* child; struct node* next; };
if旬
ふぉおしゅん?
「句」だろうな。
ダメ
仕分アルゴリズムを考える 適当に抽象的に言うと、年賀状が束であると思いねぇ。 束を解いて、あて先ごとに束にし直す。 この時、最も早く仕分を終えるにはどうすればいいか?
>>314 もっと仕分けの条件を具体的にplease
普通に宛先毎なんじゃないの。
>>314 結局、あて先でソートするだけじゃねぇの?O(n log n)よりは速くならなそう。
ソートする必要すらないからO(n)じゃねーの?
HashでO(1)じゃだめなの?
年賀状の束が大きくなっても時間は変わらないと申すか
問題が曖昧だからにんともかんとも 仕分けとかちゃんと定義しとくれ
意外と反応あってビビッタリ。 年賀状の束というのは、1つのファイルだと思ってください。 ファイルの中にはある形式で、宛先が埋め込まれており、 プログラムは宛先だけを見て、 宛先毎のファイルに分割する ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ これが想定している「仕分」です。 アルゴリズムの言葉だとどういうのかな。こんな感じか? ええと、 「宛先、a,b,c,…の 任意の組み合わせの列(長さ:可算個無限)から、 宛先毎の列を求めなさい。」 つまり、入力される列によっては、出力される列が、{a,a,a} {b,b}
になったり、{a,a}{c,c,c,c,c} {d}になったりする。 率直には、最初に出現した宛先だけを抽出する手続きがあって、 それを空集合になるまで繰り返せばいいような気もするが、 並列度を上げると早く終わるかというと、 宛先の数と関係して非効率的に思えたりするし、どーなのかなと思い。
>>323-324 与えられた文字列(ストリーム)を適当な条件(宛先毎?)で分割せよ,ということ?
入力のフォーマット,特に宛先の形式と出力の形式が分からないのでなんともいえんが,
普通に考えれば.宛先の形式を受理するオートマトンを作って入力を流すだけ.
あとすんません、 想定してる問題が、順序を持っているので 入力 (a, b, d, a, a, c, b) =>答え{(a,a,a)、 (b,b)、 (d)、(c)} の、列の集合かなと思ってるけど、 宛先aの(a,a,a) について、宛先は一緒だけど中身は異なるので、 aの出現順序は保存しててもらいたいです。
>>326 入力フォーマットの説明が全然足りんよ。
その入力と書かれてる a ってのは、アルファベット小文字の a じゃないんでしょ?
仕様うpれよw
無いものはうpできません
単に O(N) の走査にしか見えんが
どう読んでも、単なる逐次処理で全走査だろ。 その部分に工夫の余地はなさそうだけど・・・
lispのmapで高階関数にするしか ないとおもうのじゃが皆の衆
何を知りたいのかについてなかなか口を割らない質問者じゃのう
ゴールドバッハの予想というものがあります。 「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を出力して停止 流れ図を描いたりしてみたのですが、 入力を偶数と定めて無かったり無限ループになったりで 正しくないことは分かりますがどこを直せばいいかが良く分かりません
[6]を実行し[7]でチェックをする際にbの値はどうなってる?
>>334 「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] に相当するわけだ。
>>336 > N = x/2
これは「x/2 <= P[N] となるような N」だな。
24ビットや32ビットのビット列に対して、1の立っているビットの数の総和が 奇数か偶数かを最短時間で判断するようなアルゴリズムってありますか? 現状、各ビット全ての排他的論理和を計算して、奇数、偶数判定をしています。 Population Count の結果の最下位ビットを見るのが最速?
>>338 最短時間の意味とか、どんなCPUを対象にしてるか知らんけど、
スーパースカラとかパイプラインとか考慮しつつ最短を保証するのは難しいよ。
少なくとも、現行CPUにおける(最悪判断時間が)最短のアルゴリズムは知られていない。
ありがとうございます。 CPUは16ビット〜32ビット程度の組み込み用途で想定していました。 CPUの命令セットに、ビット毎の排他的論理和を計算する専用の命令があったので、 よく知られているPopulation Count のアルゴリズムでカウントした結果の最下位ビットを 取り出すよりは、早く奇偶判定が実装出来ています。(特殊な巡回符号で符号化されたデータの復号化処理) 何か特殊なアルゴリズムがあって、総当りで排他的論理和をやるのが非効率だと困るなぁと 思って質問してみました。
>>340 まさしくそのCPUのパフォーマンステーブルが無いと答えられるわけがない質問だったな
342 :
デフォルトの名無しさん :2009/04/25(土) 14:43:57
アルゴリズムの話するときの「最短」って当然最適性の意味だろ CPUの処理時間とか持ち出す奴ってアルゴリズムわかってないだろ
このスレずっと追うとわかるけど、ひとりいるんだよ。 「アルゴリズム」がわかってなくて「現行CPUにおける最短のアルゴリズム」とか言っちゃうやつ。
アルゴリズムの計算時間モデルでは、計算機モデルを考えるのですが… 理論的には、計算可能と不能の2種類しか存在しません。 解ける問題は、定量的解釈により多項式か指数関数は、計算機モデルには依存しません。 しかし、異なる計算機モデルではその枠内で計算量が異なるのはごく当たり前です。 nビットランダムアクセスメモリモデルと、シーケンシャルアクセスメモリモデルでは、 求まる計算量が違うのです。 その場合、最短計算時間を出すことのできるアルゴリズムも変わってきます。
345 :
デフォルトの名無しさん :2009/04/25(土) 17:54:15
いや、今世に出てるCPU全部ランダムアクセスモデルだから
346 :
デフォルトの名無しさん :2009/04/25(土) 18:07:23
>>344 「頑張ってグーグル先生に聞きました!」て感じのレス乙
>>344 前段は正しいが、計算機のモデルに合わせて計算量が変わるというのはアルゴリズムの問題ではないので後段は前段と矛盾している。
計算量はそのアルゴリズムに所属しているものですが、30年前O[n^3]で30分のものを今の計算機で行うと1秒で完了するって事は、計算量は多いが完了するのは超高速というアルゴリズムによくあるマジックです。
>>340 要ははパリティだよね。組み込みという事なら符号化/復
号化も含めてハードでやった方が良い気もするけど、
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);
}
ってところか。
>>349 いまだに開眼出来てない人なのでほっとしておいてください。
この人たちは
>>348 をいくら読んでも理解できず自分で考えることが出来ない人たちなんで。
たとえば「このアルゴリズムは速い!遅い!」とか考えてる人たちですよ?
>>348 344はアホっぽいからどうでもいいんだけど、
計算機のモデルにあわせて計算量は代わるんじゃない?
極端な例だと、「ソートがΘ(n log n) 」というのは代数決定木モデルなどの話で、
O(n) になる計算モデルもあるよね(例えば実数を持ちまわれるモデル)。
そこまで極端に変えなくても、基本演算のコストが変われば
O(...) に隠れた定数が変わるのは当たり前だと思うんだけど?
353 :
デフォルトの名無しさん :2009/04/25(土) 21:05:33
計算モデルが量子コンピュータに変われば、巡回セールスマンは早くなる
厳密に言うと、多項式で解けるようになる
当然計算モデルによって計算量は変わるぞ
>>348 は計算モデルをわかってなさすぎ
CPUの処理時間とか言いだす奴は論外
354 :
デフォルトの名無しさん :2009/04/25(土) 21:13:46
>>353 です。よーーーーーーーく考えたら自分間違ってるのに気づいた
スマン
計算量はアルゴリズム固有であって、計算モデルが変わったらアルゴリズムは通用しないことが抜けてた
>計算モデルが変わったらアルゴリズムは通用しない 何が通用しないって?
356 :
デフォルトの名無しさん :2009/04/25(土) 21:18:15
357 :
デフォルトの名無しさん :2009/04/25(土) 21:20:10
アルゴリズム=計算モデルに依存した計算の手順 ってこと。 クイックソートは単一のチューリングマシン上ではO(NlogN)だが それを並列計算機モデルや量子コンピュータモデルでは動かせないからO(logN)にはならないってこと
量子コンピュータとか実際にあるんですか。 それもチューリング何とかと同じ空想の産物つまり実現不可能なモデルでアルゴリズムを作るとことでは? このスレはSFネタスレなんですか?
鼻糞は早く死ね
>>357 量子チューリングマシンでも通常のクイックソートは動くでしょ。
もちろん、計算量は O(log n) にはならないけど。
361 :
デフォルトの名無しさん :2009/04/25(土) 21:33:58
動かんだろ 量子コンピュータはアルゴリズムもまともに検討されてない段階
>>361 実体としての量子コンピュータをどうするかという問題はさておき、
数学的な概念としての量子チューリングマシンははっきりしてるし、
それが古典的チューリングマシンと計算可能性の意味で等価であることは証明されてるから
どちらか一方でしか本質的に動かないアルゴリズムは存在しないよ。
量子計算理論は、いくつも論文や重大な理論が発表されてて、
あとは実際の計算機ができるのを待っているような状態。
>>362 のいうように、実際の計算機で計算可能かどうかはともかくだが。
アルゴリズムに絶対的な時間のものさしってあるの? というかオーダー決めるときに使う”ステップ”って何?
365 :
デフォルトの名無しさん :2009/04/25(土) 23:25:17
>>364 理論計算量の人のいう「ステップ」はチューリングマシンで実装したときの
状態遷移のこと(これは明確に定義可能)。
ただ、普通のアルゴリズムの議論では、ここまで戻ってステップ数を見積もることは無くて、
アルゴリズム中で支配的な演算の回数を数えるのが普通。
たとえばソーティングだったら「比較が O(n log n) 回」とかいう言い方をするし、
行列計算なら「乗算が O(n^2) 回、加算が O(n^3) 回」とかいう言い方をする。
ある程度共通認識として何に着目するかが分かっていたら、「○○が O(n) 回」を
「計算量が O(n)」とか言ったりするけど、何が O(n) なのかは意識しないといけない。
あと、言うまでもないことだけど、計算量とオーダーってのは、全く別の概念だよ。
歴史的にも別物だし、オーダーで計算量を表記しない分野もあるしね。
アルゴ君てやっぱり頭いいんだな・・・
♫
369 :
デフォルトの名無しさん :2009/06/06(土) 21:04:42
phpで単語をイロハ順に並べる物を作ってるんですけど 漢字が出てきたらどうすればいいんだろう? 漢字はあくまでデフォルトの並びをします しかできないのかな
IME 読み仮名 取得
371 :
デフォルトの名無しさん :2009/06/06(土) 21:10:30
読みが複数ある場合はどうするのだ
373 :
デフォルトの名無しさん :2009/06/06(土) 21:48:50
IMEか ATOK入れたときに、なんとなくうざいから消しちゃったんだよね IMEから漢字の読みのデータをテキストファイルか何かに移せるの?
Windows? MS-IMEでもATOKでもそれ以外でも基本的なAPIは OSの段階で共通だから、そんな心配は要らないよ。
375 :
デフォルトの名無しさん :2009/06/06(土) 22:26:35
その前にphpなんで、OSのAPIにアクセスするのは無理かと
376 :
デフォルトの名無しさん :2009/06/06(土) 23:14:25
C言語でDoubly Linked Listsを作っています。 リストの任意の位置に新たにデータを挿入するときにリストの先頭からポインタを辿っているので次第に遅くなっていきます。 10万件くらいまでならまだ実用的ですが、100万件になると実用に耐えられなくなります。 キャッシュすれば速くなると思い256個のキャッシュを作ったら100万件でも十分実用的になりました。 キャッシュ以外に速くする方法を探しています。
377 :
デフォルトの名無しさん :2009/06/06(土) 23:18:27
phpってこんなにウザイ奴しかいないんだ・・・
>>376 任意の位置が与えられるなら(表現が変か?)、O(1) だよね。
知りたいのは、挿入すべき位置を高速に探索する方法でいいの?
どうしても双方向リンクリストじゃないと駄目な理由があるの?
ソートされてるの?
ソートされてる必要があるなら平衡木とかどうよ。
ソートされている必要が無ければハッシュリストはどうよ。
たしかに理論的にはO(1)ではありますね。 >挿入すべき位置を高速に探索する方法でいいの? その通りです。 リンクトリストでないとダメな理由は、汎用データのデータ構造のライブラリを作っているからです。 汎用データといってもgeneric pointer(void *)を回しているだけですが。 ソートは、使う側が任意のタイミングで呼び出すことが可能です。 よって、常にはソートされている保証はありません。 ハッシュリストですか。 たしかに検索O(1)ですね。 すでにライブラリに含まれていますので考えてみます。 ありがとうございました。
380 :
デフォルトの名無しさん :2009/06/07(日) 12:05:26
プロジェクトオイラーの問題でアルゴリズムが解らなくて解けません。 Problem 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) を求めよ。 解き方が解る人 教えてくだせい。
>>379 自分で作ってたんじゃなかったの?
嘘はいかんよ
>>381 どこかの誤爆であることを祈るが、勘違いしているようなので言わせてもらう。
汎用なDoubly Linked Listsを作っていて、任意の位置に挿入する関数で時間がかかっている。
理由はポインタを辿っているからなので、それを解消するためにキャッシュ領域を作ってみた。
結果、100万件くらいまでは実用レベルに達した。
もっと効率が良い方法はないかと尋ねる。
リストの挿入はO(1)だよね。<あたりまえだろ
データ構造として平衡木やハッシュはどう?
ハッシュをリンクトリストにコンポジットすればいいのか。
既に作っているから考えてみよう。
リスト作っていたんじゃないの?ハッシュ使うのかよ<勘違い
統合失調症の臭いがする
>>382 なんかまったく分かってないみたいだね
そんなことより勉強しなおしたほうがいいよ
>>380 検索して驚いたんだけど、そこまでは自力で行ったのか?
愚直にやるだけで、なかなか大変だと思うけど。
ちょっと説明してたら小冊子が書けそうだけど、どこが分からないか分かる?
六十度角を挟んだ三角形(二辺)の列挙はできる?
整数比になるかは調べられるよね?
外接円ってのは外心ってのを出すんだけど、これは検索してね。
あと、正三角形を弾くのを忘れないように。
楽しみを奪ってやるなよ
387 :
デフォルトの名無しさん :2009/06/08(月) 00:06:27
人工知能のアルゴリズムを教えてください
つ 中国人の部屋
389 :
デフォルトの名無しさん :2009/06/08(月) 00:31:46
中国人がアルゴリズムを考えるのですか?
検索しろ。 てかアルゴリズムでもなんでもないが、人工知能関係では有名な思考実験。
検索したけど、「中国語の部屋」じゃないのか
部屋に入ってるのは中国人じゃないんだよね
六畳間に中国人を大量に詰め込んどくと チーとかウォ言うのが組み合わさって他国語話者が空耳アワー出来るな人口無能 な研究。
中華政府が移動したのは台湾であって、本国にいるのは旧ソ連の 共産主義者じゃん
なに言ってるの?
「中華政府が移動したのは台湾であって、本国にいるのは旧ソ連の 共産主義者じゃん」と言ってるの
うん、で、なんでここで?
そういうアルゴリズムなんじゃないですか?
そか。特にアルゴリズム的な改善の余地はなさそうだな。
非同期キューってどうやって実装すればいいのですか?
キューを作ってmutexなどで保護しとく
>>402 えーとそのーあー
書き込んでる最中だけど、読み込みブロックと重ならないなら
同時に読み込みもできるキューってどうやって
書けばいいのですかね?
ソースコード見ればいいんじゃない?
>>403 > 書き込んでる最中だけど、読み込みブロックと重ならないなら
> 同時に読み込みもできるキューってどうやって
各ブロックに read-write-lock 設定すりゃええんちゃうの?
>>403 lock-free queue あたりで探せば色々見つかると思う
ノードは単方向リストで、headとtailに番人を入れておいて、 ・enqueue -> tail.nextとtail に新しいノードを挿入 ・dequeue -> head.next が空ならreturnまたはブロック、あればhead := head.nextとして、nextを新たな番人とする で、どうかな?だめかな?
あ、deqeue同時も許さなきゃならないのかorz
多角形や円形の範囲内からある座標1点をランダムに選ぶには、どのようなアルゴリズムで実現できるでしょうか。 数学的知識が乏しいので易しめでお願いします。
paint
円の範囲なら角度と長さで出せるね 多角形はしらね
数学的知識がないなら点をランダムに選んで範囲内じゃなかったらやりなおせ
範囲内の全pixelを採番して一つ選べばいいんじゃねえの
>>409 任意の多角形は三角形分割できるので,三角形分割しておいて
(1) 三角形を、各三角形の面積に比例する確率で1つ選択
(2) 選択した三角形内からランダムに選択
とすることで(一様)ランダムサンプリングすることができる.
前処理の三角形分割は O(n log n) ででき,各サンプリングは O(1) でできる.
その図形を囲むサンプルしやすい領域があって(外接長方形など),
図形がその領域の中の大きな面積を占めているなら
>>412 の方法でも良い.
幾何的データ構造を前処理しておけば内外判定は O(log n) でできるので,
O(log n × 1/(1-r)) でできる.ただし r は図形の占める面積の比率.
415 :
414 :2009/06/24(水) 21:42:04
>>414 最後の式が O(log n × 1/r) の間違い.
r が 1 に近いほど早く終わらないと変だ.
ございます。
>>418 客先の実装は
奥村晴彦「C言語による最新アルゴリズム事典」
のコードかな?違っていたら試してみたら?
ネットにもソースが転がっているはず。
420 :
418 :2009/07/01(水) 09:42:40
>>419 情報THX。
それで正解、奥村本の引用でした。
# つーか、一つのプロジェクト内に奥村本の引用とNRの引用とまた違う実装の三種類も混ざっているのが何とも……_/ ̄|○
これで出自がはっきりしたので心置きなく参考にできる。
引き続き、情報あれば宜しく。
# こちらで最適化した最終版は、問題がないようなら公開しますんで。
今日、ダチョウアルゴリズムなるアルゴリズムらしからぬアルゴリズムをしった 私はこの事実に関してダチョウアルゴリズムを適用することにした
どうぞどうぞ
>>421 wikipedia見たらマジであるwくだらねーw
よし、おれもプロジェクトで採用するわ
ダチョウが先かニワトリが先か
すみません、数学に強い方いましたら教えてください。 敵(x1,y1) プレイヤー(x2,y2) ・求めたいもの プレイヤーを中心にした半径50pixelの円周上で、敵と一番近い座標 数学嫌いな私には難しくて・・どう計算すれば良いでしょう?
>>426 距離R
R^2 = (x1-x2)^2+(y1-y2)^2
敵とプレイヤーの位置を通る直線を考えると…。この直線と円の交点は?
R = √(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) x = x2 + (x1 - x2) * 50 / R; y = y2 + (y1 - y2) * 50 / R;
アルゴリズムスレもレベル落ちたな
解決しました 回答してくれた方ありがとう
435 :
デフォルトの名無しさん :2009/08/18(火) 20:44:27
上げ
フィボナッチ数列 ( a_n = { 1 (n = 1, n = 2) , a_(n-1)+a_(n-2) (n >= 3) } ) を計算する関数を、 漸化式 (再帰) と一般項 ( a_n = ((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)/sqrt(5) ) の両方で作って、 各々の計算時間を計ってみた。 n = 46 のとき、 漸化式だと 28.968 秒、 一般項だと 0.000 秒、 だった。 ちなみにどちらで計算しても a_46 = 1836311903 だった。
>>436 さすがにその漸化式の計算は O(2^n) かかってるからなあ。
普通にDPすりゃ n = 46 程度一瞬で終わる。
あと、その一般項の計算はきっと結構危うくて、
通常の実装だと浮動小数点の打ち切りが計算途中に含まれている。
sqrtなんて持ち出さずに行列のn乗に落としたほうが安全。
行列の n 乗にしたら n = 46 で 0.000 秒になった。 漸化式は相変わらず 27.734 秒だった。 プログラムの見た目が単純なら計算が速いと思い込んでたが、 実際に作ってみると行数が多くてもアルゴリズムがいい方が計算が速いんだな。
ていうか、オーダーで考えようよ。
440 :
デフォルトの名無しさん :2009/08/24(月) 18:30:18
1000000秒かかるO(1)だってありえなくはないような 実測値出せるならそのほうがよくない?
#include <stdio.h> #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; }
>>440 実時間と理論計算量では計測の目的が違うので
どちらが良いとか比較できるものじゃない。例えばこの例だったら、
「計算量が違うと実際これだけ差が出るんですよ」
と主張したいのならば実時間を出すべきだし、
「こんなに時間が違うけど、その原因はアルゴリズムですよ」
と主張したいのならば理論計算量を出すべき。
438の書き込みを見る限り前者っぽいので、
わたしはこの例なら実時間を出すのが適切だと思う。
ちなみに、実問題への応用のあるアルゴリズムの論文では
計算量をオーダーとかで見積もりつつ、さらに
計算機環境を明らかにして、実時間を出すのが普通。
>>441 >>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;
}
>>443 元のレスに合わせて、あえて再帰で書いたんでしょや
数学板より
http://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);
}
}
>>445 これ、n が奇数の時しか b が更新されてなくて
最後に b を返してるけど、n = 8 とか駄目じゃね?
試してないけど。
n=8 t=? a=1 b=0 x=0 y=1 スタート時 n=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 であってるかな
あそっか、奇偶じゃなくて 2^n の位置になるのか。 失敬失敬。
>>445 これどうやって導き出したの?
一般項の計算を整数で行うようにしたぽ、とか、そういう感じ?
数学ワカラン俺にもわかる説明をたのむ
行列のN乗と等価にみえる
>>449 450のとおりだけど,もう少し詳しく言うと,
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 は最終結果が入るように使ってる.
任意の数値の、onになっているビットを数え上げるアルゴリズムで 数値をn進数とみなして(n-1)の剰余を求めるとできますが なぜですか?理屈は
>>452 Kernighanの方法のことを言ってるつもり?
>>454 > ビットカウント演算はビット演算命令の組み合わせで
> ハードウェア回路を用意した場合 以上の速度が出せ
> るのでまったく無駄である
これに発奮したのかわからないが、Core-i7 には
population count 命令 POPCNT が追加された。
>>454 5はBeautiful Codeに載ってたな
十進数で言うと、格ケタの数字を足すのに
12,345 -> 10305 + 204 = 10509
10,509 -> 109 + 5 = 114
114 -> 11 + 4 = 15
ってやってるだけ。見た目はアレだけど、実は難しくないぽ
16進数表現になってる部分を二進数表現に置き換えると分かりやすい
現代の集積度ではなんでものっけてしまえという方向にあるだろうな。 PowerPCにはnlzもあるんだっけ。 ビット反転のみハードウェア化して、ntzと組み合わせてもいいよね。 Intelってビット反転は追加してたっけ。
>>457 bsf(bit scan forward) と bsr(bit scan reverse) があるっぽい。
いやーアルゴリズムって本当にいいもんですね。
一歩 二歩 算法
ttp://d.hatena.ne.jp/rsakane/20081013/dijkstra このページを参考にして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},};
462 :
461 :2009/09/02(水) 09:42:33
すいません。質問を書いているうちにその原因に気付きました。 スレ汚し失礼しました。
ダイクストラとカナを当てるのが定番だと思うが...
固有値・固有ベクトル全部求めたいんだけど, 200次元程度の実対称行列がターゲットだと, ヤコビ法より,QR法+LU展開で固有ベクトル求める とかのほうが速度出るのかな?
>>464 200×200程度だったら何やっても大して問題にならない。
けど、一般的にはヤコビ法はあまり良い方法じゃない。
>>465 そうなんだ・・・
一応両方実装してみたんだけど,
QR+LUのほうは,なんか収束しないパターンみたいなのがあるみたいで,
無限ループしてる・・・。
467 :
466 :2009/09/08(火) 11:31:47
追記,収束しないところは,LU分解で固有値に対する固有ベクトルを求めていくところ。 70万回くらい200次元くらいの実対称行列の固有値・固有ベクトル全てを求めるから,少しでも早いほうがいいんだよなぁ・・・
>>466 収束しないのはきっと実装が悪いんだよ.
それにしても,70万回も固有値固有ベクトルを求めるのは
用途にもよるけど,筋が悪い気配を感じる.
本当に全行列の全固有値・固有ベクトルが必要か,
各行列に関係はないか(同時に前処理,Warm startなどはできないか),
などは検討済み?
469 :
466 :2009/09/08(火) 19:00:46
>>468 ありがとう。
>収束しないのはきっと実装が悪いんだよ.
もう一回見直し,組み直しするかぁ・・・
>本当に全行列の全固有値・固有ベクトルが必要か,
>各行列に関係はないか(同時に前処理,Warm startなどはできないか),
>などは検討済み?
分析のプログラムだからそういうわけにいかないんだよねー・・・
>>469 固有値問題のアルゴリズムを実装するのが目的でないならLAPACKなどを使うべき
アルゴリズムの問題集的な本でおすすめのってない?
Puzzles for Programmers and Pros
最小公倍数を求めるアルゴリズム 俺が考えたのはこれ 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; } 実測してみると、下のアルゴリズムの方が速かった。 テラ難しいけど、より速いアルゴリズムというのがあると嬉しくなるよね。
最小公倍数は LCM です 最大公約数は GCF と言わないこともないが普通 GCD だな あとアルゴリズムを知りたければユークリッドの互除法でぐぐるとよろしい
>>437 つまりあなたは、小学生にも理解できるユークリッドの互除法が「テラ難しい」のですね?
それって要は、頭の使い方も忘れているってことだな。
# 元から知らないで来てしまったのかも知れないが。
>>474 やべ、間違って最小公倍数って書いちゃったorz
最大公約数です。
ユークリッドの互除法っていうのか。
ありがとう。
>>475 そこまで言う資格があるのはユークリッドの互除法を自分で考え出せた人間だけだと思うが
罵倒レスで安価ミスる奴がそんな頭いいのかなぁ
小学生に理解できるかというと厳しいものがあるし 昨今では知らない奴がいるのも仕方ないし 何事もきっかけだから喜んでる奴に水を差すのもどうかと思うが ごめん3行越えたからやめる
ユークリッドの互除法って高校でやらなくなったのかねえ 知らない人が多いことを想定しているような書き方のサイトばかりだ
互除法自体は小学校で教えても充分理解できるだろ。名前は難しくてもね。
>>477 私は小学生自分に再発見したよ。
>>480 小学生「時分」か?小学生は自分の好きなことにだけは特異的な才能を発揮するからな。
ユークリッドの互除法を小学生くらいに実質自分で見つけ出す人もいれば 小六で教えてもらっても尚なかなか理解できない人もいるし ただアルゴリズムスレって場所においてユークリッドの互除法が テラ難しいってのはちょっと違和感あるなあ
はげど アルゴリズムの基礎の基礎じゃん
アルゴリズム自体は簡単だけど計算量評価はかなり難しいと思う
総当たりして平均と分布とワーストケース比べりゃ良いだけじゃん。bigintじゃないんだし。
32bit整数だとすると2数の組み合わせは 2^32 * (2^32 - 1) / 2 ≒ 2^63 通り あるね 総当たりできるもんならやってみな
これまたなんか生温く見守りたい論争が…
○○だけじゃん w
こんばんは 様々な周期、振幅の正弦波を重ね合わせた波形があるんですが この波形から短期的なピーク値(っぽいところ)を抽出したいと思っています 元の波形がわかっていれば簡単そうですが、 わからない場合にピーク値(っぽいところ)を抽出するにはどんなアルゴリズムが考えられるでしょうか・・・
幅決めて走査すればいいだろ
492 :
デフォルトの名無しさん :2009/10/04(日) 07:24:21
良い組み合せを求める問題を考えています。知恵を下さい。以下問題です。 様々な価値と重さを持つボールが複数と、様々な重量制限のある箱が複数ある。(ボールと箱の数の関係は任意) ここで、できる限りのボールを箱に詰めたいが、使う箱はできるだけ空きの重量を少なくしたい。 というものです。評価指標は、「使う事になった箱の残重量を最低にする」と「詰めたボールをできるだけ多くする」です。 一つの箱ならナップザック問題になると思っていますが、、、この問題はナップザックも複数あってどうしたものかと思います。 何か良い方法はあるでしょうか。
シミュレーテッドアニーリングとか遺伝アルゴリズムとかでそこそこの解は出そう
価値/重さ がでかいのから順に入れていけばそれなりの解になるさ
>>492 (1) ボールを詰められる数の最大化
(2) それを詰める範囲で空き容量の最小化
という問題でいいのかな?だとすると,
これは multi knapsack problem の多段階バージョンで,非常に難しい.
厳密解法としては
(1) は全ての箱を使う前提でボールに関する multi knapsack の実行可能解列挙
(2) はその解候補について箱に関する multi knapsack の最適化
になるので,それぞれで適当な緩和解法を使うのが妥当っぽい.
496 :
デフォルトの名無しさん :2009/10/04(日) 12:07:57
>>494 ただのナップザックならそれでも良いですが、入れさせるナップザックをどんな順で並ばせるか、も問題だと思っています。
>>493-495 やはり結構難しい問題になるんですね。。。そこで、遺伝的アルゴリズムを使ってみよう、という話になるのですが
では遺伝子をどのように設計したらよいか?と思うのです。
とりあえずボールがn個(B1,B2,B3,...,Bn)(ボール配列)と箱がm個(H1,H2,...,Hm)あるとして、「ボールpはq番目の箱
に入る」を「ボール配列のp番目にqという数字を振る」事とする。
これでボール配列に1〜mまでの番号をでたらめに撃って初期値とする。。。とりあえず使う箱とそれに入るボール、
使われない箱の特定ができますよね。
この配列は自分自身内で順序を変えるのはいいですが、違う遺伝子と交叉とかしてしまうと、破綻してしまうケース
が大すぎてしまう気がしています。。。
>>496 > 「ボールpはq番目の箱 に入る」
「ボールを入れられる箱のうち残り容量の大きい方から
q 番目に入れる」にしたら駄目かな?
> 495 が 1) 箱それぞれについて取りうる状態を列挙 2) 1 の中から題意を満たす組合わせを列挙 みたいになるのなら条件によっては爆発するってことじゃね?
500 :
デフォルトの名無しさん :2009/10/04(日) 23:53:17
>>498 無視なんてことはないのですが、multi knapsackという用語をはじめてみたのでなんともいえなかったのですよ。
結局はっきりしないままなのですが、理論や実装例みたいなものが載っているサイトがあったら紹介してほしいです。
DP みたいなので行けるかと思ったけどボールを一個追 加するとそれまでの最適解で使っていた箱を使わなくな る可能性もあるんだな。
>>492 価値???
多分ボールと箱両方から攻めて数次元の代数幾何学云々で余白が狭すぎる。
504 :
デフォルトの名無しさん :2009/10/05(月) 12:59:29
>503 にリンクしてあるPDFに,n=10^5 の問題を数秒で解く(と主張してる) アルゴリズムが載ってるね
>>503 英語のwikipediaを翻訳すれば良いじゃない?と思ったこともありました。
知ってるんなら書いといてやれよ。 とよく思う。
>>500 multi knapsack でgoogleとかgoogle scholarとかで調べれば山ほど出てくるでしょ
あの〜いきなり関係ないんですが、B-スプラインですが スプライン補間の代表的な応用はベジエ曲線なんでしょうか? 若しくは逆に、ベジエ曲線の数式化がスプライン補間であったってことでしょうか?
>>492 param 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;
>>509 前から興味があった 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,
みたいに出てくる。
ちなみにボールの数を優先させると 15 = (3) x 3, (5) x 1, (7) x 0, になる。
条件間違ってた orz 11 = (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,
>>508 「スプライン(補間)」というのは一般的な語。
「ベジェ」「Bスプライン」というのは特定の曲線を指す。
>>513 確かにそうですね。wiki(英語も)では二項定理の式ばかりだったので勘違いしてましたが、
奥村先生の本だとスプライン補間の実際の方法いくつか紹介されてましたが、二項定理の式を使ったその曲線はスプライン補間といわれる補間の一つなんでしょうか。
ベジエ曲線は端点を何を根拠につなげてるんでしょうか。
515 :
デフォルトの名無しさん :2009/10/13(火) 01:49:32
>>515 中央のカードが配られない時点での勝率も計算できるね
前通りの組み合わせを試して計算するのにそんなに時間がかかるかな?
1 vs 1だとすると、残りのカードは52 - 4 = 48枚だから、
48 * 47 * 46 * 45 * 44通り、205476480通り試せばいいわけだよね。
そんなに大変じゃない印象があるけど…
>>516 素直な実装でやってみたらかなり大変だった
さらに、最終的な7枚のうちから5枚を選択して最強のカードを選択するから
205476480 * 21通り、4,315,006,080回判定をしなくてはいけない。
上のWebサービスでは何かしらのテーブルか何かを持ってるんじゃないかな
まあそのくらいの数ならDBに入れれば一瞬で引けるしな
実際にはデータベース引くみたいなことはしてないらしいね. オッズ計算アルゴリズムで特許が取られてる. 大雑把には,重み付け探索の仲間みたいなことをするらしい.
520 :
デフォルトの名無しさん :2009/10/17(土) 04:45:50
Wikipediaの「Selection Algorithm」(日本語版は「選択アルゴリズム」) を読んでいたら、リストに格納された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するアルゴリズムなわけですが、このアル ゴリズムの利点として以下のようなことが書かれていました。
521 :
デフォルトの名無しさん :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)となるのではないでしょうか。 何卒御教示をお願いいたします。
522 :
なんじゃこりゃ :2009/10/17(土) 20:50:18
それは"list"という名の配列変数≠線形リスト(linked list)
523 :
デフォルトの名無しさん :2009/10/18(日) 00:24:20
>>522 レスありがとうございます。
擬似コードを素直に読めばlist[]は配列ですが、j(>k)番目
に小さな要素が求まった後にk番目に小さな要素を求める
計算量がO(1)でなくO(k)なのと、名前が(A[]とかでなくわざ
わざ)list[]なので、線形リストなのかなあと思った次第です。
listが配列として、上の利点云々の記述はどういうことなの
でしょうか?
何卒御教示をお願いいたします。
そんな派手な間違いがあるわけないと思って真面目に見てなかったが、記事がおかしい。 二番目の "ランダムアクセスを要求しないこと" とゴッチャになってるし、その一文は無視したらいい。 言いたいことは冒頭の "k が小さければ速い" にほぼ含まれてるし。
折角だから、書き換えておいて。
526 :
521 :2009/10/23(金) 15:19:52
>>524 大変遅くなってしまいましたが、レスありがとうございます。
Wikiの記述が間違いということですか。
>二番目の "ランダムアクセスを要求しないこと" とゴッチャになってるし、
二つ目の利点
It can be done with linked list data structures,
whereas the one based on partition requires random access.
とゴッチャになっているとはどういうことでしょうか?
>言いたいことは冒頭の "k が小さければ速い" にほぼ含まれてるし。
これはどういうことでしょうか?
自分は「他の問合せの結果が利用できる」ということ
だと思ったのですが。
御教示どうぞよろしくお願いいたします。
>>526 > とゴッチャになっているとはどういうことでしょうか?
それまでに連結リストをたどる話は全く出ていないのに、ソート済みの部分を飛ばすコストに
連結リストをたどるコストが計上されている。
他にもその一文には問題があって俺の SF 魂を揺さぶるが、そんなことに付き合う必要は無く
無視すべき。
> 自分は「他の問合せの結果が利用できる」ということ
他の方法でソートしても同じ利点は得られる。
あの文で指摘されているのは k (その時には n もだが)が小さくなる場合があるということで、
レアケースだし無理に言及する必要は無いのではないか。
概要に選択ソートを途中まで行ったものだと書いてあるのだから、混乱を引き起こす文章を
追加するよりは、自明とするのが良いと思う。
528 :
521 :2009/10/24(土) 14:37:08
>>527 御教示ありがとうございます。
>ソート済みの部分を飛ばすコストに連結リストをたどる
>コストが計上されている。
O(1)ではなくO(k)となっている箇所ですね。自分もそこで
「あ、連結リストの話なのか」と思いました。
>あの文で指摘されているのは k (その時には n もだが)が
>小さくなる場合があるということで
j番目までのソートが終わっているのであれば、(k,n)では
なく(k-j, n-j)で計算できるということですね。
ともあれO(j + (k-j)^2)は間違いということで、ご説明
どうもありがとうございました。
Merkleツリー ってどんな同期アルゴリズムなんでしょうか?
R. Merkle, “A Digital Signature Based on a Conventional Encryption Function,” Proceedings of Crypto ’87, pp. 369–378. この原論文が参考になります.たぶん
アルゴリズムの考え方がわからない ソートアルゴリズムだの、データ型だの一連のものは読んだ でも、データ型で配列だのハッシュだの、ツリーだの そんなもんはプログラムする上で使うし ソートアルゴリズムで、バブルソートだのクイックソートだのできるようになった でもこれって、ただのFor文の組み合わせだよね。 極論言えば、1〜10まで足しこむのもアルゴリズムじゃね? こんなのやっても、俺が求める 数式をプログラムに落とし込む能力なんかつかねぇし スマートな実装方法なんてものの応えも出てこない。 結局、何かしたいときに そのフロー図書いて落とし込むこと=アルゴリズムでいいの? 誰か教えて。 つか、数式をスマートにプログラムに落としこむのに良い本とか教えて
>>531 アルゴリズムってのは問題に対する解決手続きのこと.
何か問題があったときに,どんなデータ型を使って
どんな For や If を組み合わせたら問題が解けるか,
というのがアルゴリズム.
当然1〜10の和を求める手続きもアルゴリズム.
数式をプログラムに落とし込むのは実装技術で,
アルゴリズムとは普通は呼ばない.
実装に関する良い本は見たことが無いなあ.
経験積むしか無いんじゃね.
>>531 そもそもお前は求めている物が何なのか分かってないだろ
数式が何を指すのか、そして最終的に何が得られれば良いのか説明してみろよ
実装は突き詰めるとターゲットのCPUによってすら変わる話だからなぁ。
国語辞典の「算法」でも引いてみろ。 確か岩波のは、コンピュータサイエンス的にマニアックな説明だったはず。
>>531 > 極論言えば、1〜10まで足しこむのもアルゴリズム
それを for を使わず 10*(10+1)/2 で求めるのもアルゴリズム
>>531 Programming Pearls
Introduction to Algorithms
Algorithm Design
The Art of Computer Programming
この辺が鉄板
あとはDomain Theoryなり、Squiggolなり関数型言語寄りの世界に入ればいいと思う
違う
ハッシュ木ってどんなデータ構造なんですか? Cの実装を見てみたいのですが知りませんか?
取り敢えず"ハッシュ木"で検索して、情報が少ないことは判った。 まぁ頑張って探してくれ。
1〜nまで重複の無い乱数を生成するアルゴリズムを教えろ
●要素数 n の配列を用意 ◆1〜n までの乱数を発生 (a とする) ◆a 番目の要素と (n - a + 1) 番目の要素を交換 ● ◆ を n 回以上(充分シャッフルされるまで)繰り返す ●1 番目から n 番目まで順番に取り出す
全然だめです
pair(id, key) = (1, rand), (2, rand), ... , (n, rand) をkeyの値でソートし、idを順に取り出す。
for(i = 0; i < N - 1; i++) { a = rand(N - i); SWAP(array[i], array[i + a]); }
何やってんだか
現実的な話 各言語に実装されたRAND系を使用する場合は、 十分多い集合からそれよりも大分少ないn個をランダムに選択。重複したらやり直す で殆ど重複せずに取れちゃうよな indexをランダムに選ぶ様な場合は、 nが比較的少ないならn個の配列作ってしまうのが一番楽だろうな
Fisher yatesでググるかヤフるかMSNれ 547が正解
いや、546だ。
取り出すエントロピーが最小なのは547。
>>546 はkeyが重複することがあるので駄目だな
>>549 Windows環境だと RAND_MAX=2^16 しかなかった気がする
>>553 浮動小数点で 0 ≦ r < 1 な r を返すタイプの rand を使えばいいだろうよ
>>554 表現できる数の集合が有限である限り重複しうる。
重複しても大した問題じゃない
>>546 = Schwartzian transform
>>547 = Fisher yates
というんだってな。
へぇ 俺が再発明したアルゴリズムに名前が付いてたのか
Schwartzian transform の一応用というか変種だな。
配列用意しなくてできないかね? メモリに制限のあるオーディオプレーヤーでシャッフルに苦情が出てさ
使わないと無理だろ。 全単射な関数を発見しておくとかならいけるだろうが。 f ( n番目、 総数N、 乱数r)で、一対一対応のある関数。
r=0 N=1000 として、 関数 f(n)がランダムに近い出力だすのも困難だろ。 ランダム、一対一の構築は面倒。運任せに近いと思う。
重複が少しはありでいいなら、ランダム性はカオス理論とか調べたらいいんでは。 ある程度のランダムは確保できると思う。
重複ありだったら、rand()%Nでいいのだがな。
既出かどうかは1ビットでわかるから、配列よりは小さくなるかも あとは、ビットカウントの少なそうなところから埋めていくか
6万個 = 2^16個記録するのに、8Kバイトだな。
「アルゴリズミック」という言葉があるが。 ていうか最適化とかするまでもない手順のような気がするが。
陛下の中の人もボールいちいち大変だな
algorythmic
ミックミクにしてやんよ
PHPでバブルソートを書きたいのですが動書けばいいのでしょうか?
>>572 PHP以外でバブルソートを書くが如くに書けばいいでしょう。
教えてくだせえ。 入力としてNxN のbool型2次元配列が与えられる。 この配列は読み書き可能である。 この配列の内容を次のように書き換えて返したい。 1.入力時にtrueだったセルはtrueのまま。 2.入力時にfalseで上下左右いづれかのセルが入力時にtrueなセルはtrueに書き換える。 3.入力時にfalseで上下左右いづれのセルも入力時にfalseなセルはfalseのまま。 このアルゴリズムをメモリ使用量O(1)で実装できるか。
宿題?
576 :
574 :2009/11/25(水) 21:07:07
宿題ではないんだけども、いかにも宿題っぽいことは否定できないw 一応、囲碁プログラムの一部です。
N*Nを全部やるなら単に順番になめて新しい配列に書いていけばいいだけじゃん
新しい配列用意したらO(1)じゃなくなっちゃう。
O(1)だよ。Nは定数だから。
昔ナノピコ教室で見たことあるな>囲碁の連続カウント でもメモリ使用量O(1)?
囲碁のプログラムとか、1次元配列で表すだろ普通。 そのへんに転がってるプログラムいくつか読んでみろ。
どうしても2N分だけのメモリが要るような…
583 :
574 :2009/11/26(木) 08:12:45
すいません。 もし厳密な証明をしてくれる人がいたら、問題設定がメモリO(1)でできるか?だとちょっとまずそうなので メモリO(logN)でできるか?に変更させてください。
2N は O(1) だな
Nは変数として考えるよ俺は にしてもここIDないんだなあ
Nは変数だとしても計算上は定数だろ それともなにか,碁盤のサイズはbool型の遷移処理中に大きくなったりチッちゃくなったりするのか? フヒヒ
>>586 頼むからオーダーの概念を理解してくれ
585の言う「変数」はプログラム中の変数ではなく
オーダーO(f(N))を決める変数Nという意味だと分かってやれ
>>587 囲碁プログラムという前提がある以上、Nは定数なんだよ。
よしんばNそのものが定数でなくとも、max(N)は定数で押さえられる。
諸般の事情から、最大でも52かそこらだろうからな。
したがってN*Nも定数で押さえられるので、O(1)なんだよ。
頭悪いな
自己紹介の時間がやってまいりました
>>588 頼むからオーダーの概念を理解してくれ
585の言う「変数」はプログラム中の変数ではなく
オーダーO(f(N))を決める変数Nという意味だと分かってやれ
>>587 > オーダーO(f(N))を決める変数Nという意味だと分かってやれ
まあアルゴリズム上,入力はNじゃなくて "NxN のbool型2次元配列" 一つだよなってことなんだけど,分かってやれ
もしかして NxN のbool型2次元配列 だからいかんのか^p^? // メモリオーダーは定数の例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; } こういうことじゃないの?
こういうことってどういうこと?
「定数」と「O(1)」を混同してる人がいるな 「t=O(1)」は、Nによらない定数cが存在してNが十分大きいときに「|t|≦c」であるという意味で tが一定という意味ではない あと Nを変えないのなら(実際に使うときは定数だったとしても)、オーダーを議論する意味はない
>>594 要はこの場合のメモリオーダーは碁盤の目数ではなく碁盤の個数に寄るってこと
碁盤の個数はアルゴリズム上一つだろ
>>574 画像処理の膨張・収縮処理と同じアルゴリズムなので、その辺を調べてみるといいかも。
アフィン変換なら一時領域を固定にもってればできたような
N*NはO(N*N)でO(2)
平衡木 B木 トライ パトリシア 言語はJavaかCで上記の記述が 実装面で強い書籍ってどれでしょうか?
ソース検索エンジンで検索してみたら?
リードソロモン富豪
「O(n) で十分じゃね? O(log(n)) とかマニアックすぎw」 って思ってたけど、 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 だった。
>>604 訂正
× 0.000 ms
○ 0 ms
アルゴリズムを勉強すればO(n)がある意味最低レベルだしな。 検索の最も簡単、というか何も考えないアルゴリズムがリニアサーチ=O(n)だからね。 個人的にはO(log(n))で十分かと
O(logN) は定数とみなしても差し支えない程度に小さい
正規表現のパーサを作ろうと思うんだけど、セパレータの字句にふさわしい記号は 何がいいですか?
£ はJIS漢字コードだから、なんか問題が出そうだな
数字のケタが変わったかどうかチェックするアルゴリズムで良いのないですか? 999→1000 なら真 10000→9000 なら真 みたいな。。。
$a = 100; $b = 1000; $c = $a / $b; if($c != 1) echo "桁が変わってます"; 適当書いたけど言いたいことは伝わると思うのであとは改良してください
私なら文字列化してstrlenで比べるな
10進数以外も扱いたいしな
その場合、-10 と 100 がどちらも 3 になるのが問題かな。
616 :
611 :2010/01/07(木) 14:34:53
>>612 なるほど。ありがとうございました。
>>613 10進数かつ整数範囲ならこれでも楽ですね。
ありがとうございました。
613 のは n 進文字列を作れば 10 進以外も大丈夫。 ていうか桁数を問題にしてるんだから log 使おうよ。
abs(x) … x の絶対値を返す log(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; } -------終わり------- アルゴリズムなのかにゃ? これ
あっ! x == 0 のとき死ぬなorz 桁数 = floor( log( abs( x ) ) / log( 基数 ) ); となっているところを if( x == 0 ) { 桁数 = 任意定数; } else { 桁数 = floor( log( abs( x ) ) / log( 基数 ) ); } って感じにせなアカン。
ふと思い出した、以前書いた美しくないアルゴリズム。 擬似乱数を使って、ランダムで一様な方向を発生させたかったのだが。 rand()を0以上1未満の浮動小数点の乱数を返す関数として。 2次元の場合は、rand()*2*piでいい。 3次元の場合、rand()*2*piで経度を、rand()*piで緯度を発生させてみたのだが、それだと一様にならない (北極/南極あたりは緯線と経線の密度が高くなる) 時間がなかったので、その時は、 while(1){ 単位立方体内に一様にランダムな1点を取る if(取った点が単位球内に含まれている) break; } 逆三角関数で、とった点の角度を求める のようにしたのだが、あんまりエレガントじゃない。 もっとエレガントな方法は、なかったのだろうか。
>>620 単に時間かけてのゴリ押しじゃんね
単位時間あたりの桁数算出ではスパコンが2ケタ弱違いに上
一般的にはガウス乱数を3個発生させてノルムで割ればいいですが 3次元ぐらいなら、もっと良い方法がありそうです 個人的には621も十分賢い方法だと思います 次元数が大きいと外れ確率が増えますが
t=rand()*2*pi; z=rand()*2-1; x=sqrt(1-z*z)*sin(t); y=sqrt(1-z*z)*cos(t);
色々座標変換して頑張ってみたけど結局
>>624 と同じになったっぽいんですが。
極座標(1,θ,φ)から変換してみたが
628 :
625 :2010/01/13(水) 02:20:31
すまん624でよかった 個人的に意外だった……
629 :
デフォルトの名無しさん :2010/01/18(月) 07:01:28
失礼します。 とある(任意の)通貨体系、例えば361、147、75、1円玉なんていう無茶な通貨だとして、 お釣りの値を入力したら最小の枚数で切り抜けるCプログラミングを考えます。 この場合例えばお釣りが150円だったら、147×1、1×3で計4枚でなく、75×2で計2枚となるのが正解です。 通貨体系もお釣りも任意に与えられるので、それぞれがどんな値であっても最小の枚数を出すプログラムなんですが、これを考えるとき、どんなアルゴリズムが考えられますか? すみませんが、言葉でわかりやすく答えて頂けると助かりますm(_ _)m
>>629 今ぱっと思いついたのは次の2通りのやり方。
1) ちょうどお釣り x になる通貨の組み合わせを全てリストアップし、
そのリストを昇順にソートした場合の先頭要素を答えとする。
リストアップしさえすれば後は簡単だろう。
これは両替アルゴリズムで検索すればすぐに分かると思う。
再帰を使用する。
2) 通貨 n 枚でちょうどお釣り x になる組み合わせを探す。
見つからなければ n を 1 つ増やして再チャレンジ。
たぶん、額面が大きい硬貨から試した方が効率が良さそうだ。
>>630 なるほど!わかりやすいですね。
素早い回答助かりました。
ありがとうございます!
AVL木ってバランス取る処理の負荷が 半端じゃないから要素数が1万を越えると 利用に適さないよね?
>>633 追加の頻度が大きければ問題
それが要素数に比例するならともかく
頻繁に追加が発生する場合は 木構造は使えないと 何を使えばいいのだろうか
追加に強いデータ構造に一時的に溜めておいて、 ある程度の量が溜まってきたらAVL木にどばっと入れる、じゃダメ?
木の高さの制約をゆるめて、回転の頻度を落とした AVL を使うんだ!
ならばルートを増やすんだ!
>629
>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
>>629 >>630 のやり方だとちょっと金額が多くなると計算が終わらなくなる
実行時間効率から考えれば金額に対するDPがいいだろう
table[金額] = 必要な最低枚数 になるように table[0] から1円ずつ順番にテーブルを構築する
どの硬貨を使うか知りたければテーブル更新時に
「その金額に到達するために最後に使った硬貨の種類」を覚えておくテーブルも一緒に作ればよい
>>633 要素数Nの木に対して、要素の挿入・削除は最悪でも log(N) 時間しかかからないぞ?
正しく実装していれば100万要素の挿入くらいは一瞬で終わるはずだ
642 :
641 :2010/01/18(月) 22:25:17
OK見事にかぶったな
>629 移動して来たなら元スレにも移動しますと書いた上で、こっちにも移動して来ましたと書いてね。
644 :
629 :2010/01/18(月) 23:03:12
>>632 >>640 >>641 さん
ありがとうございます。しっかり考えて頂いてとても参考になります。
勉強不足の僕の頭ではあとの話はまだ難しいようです。
>>643 すみません。今さらですが移動してきました。
お手数をかけました。
>644 「移動します」って書く理由は元スレでの無駄な(見てもらえない)回答を避けるということと、 情報がちゃんと辿れるようにする(検索で引っかかった人とか元スレで ROM ってた人とかが 辿れるようにする)という意味があると思うので、次があればどこから移動しました、どこに 移動しましたって書いてくだしあ。
金額に対するDPだと多項式時間アルゴリズムにならないよね。 これって多項式時間で解ける問題? NP完全だったりするのかな? なんとなくPartitionあたりから帰着できそうな気はするけど。
擬多項式時間アルゴリズム (pseudo-polynomial time algorithm) と呼びます
>>646 これ自身coin changing problemとかcoin exchange problemと呼ばれる
有名問題で,NP困難.いくらでも何にでも帰着で示せる.
649 :
デフォルトの名無しさん :2010/01/22(金) 00:54:00
651 :
デフォルトの名無しさん :2010/01/22(金) 02:49:53
>650 どーもです クイックソートって言うのか 初めて知った
652 :
デフォルトの名無しさん :2010/01/22(金) 19:02:15
ピジョンホールソートってどうやるの?
適当なスレがここかわかりませんが質問します。 PN9で生成多項式が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 こういう符号理論っていうのですかね? 該当スレってどこかにあったりします?
thx!
優先度つきキューを実装したいのですが 良いサンプル教えてください。
1-1000までの数字からランダムな数字600個をなるべく速く取り出したい。 ランダムさはそれほど厳密でなくてもいい。 1-1000、600という数字はそのときどきで変わる。 ひたすらサイコロ転がすやり方だと、取り出す率が高くなると けっこう遅くなってしまう。 良いやり方もしくは一般的なやり方があったら教えてください。
unsigned *getrand(unsigned *s.unsigned c,unsigned s,unsigned e){ for(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;}}}
Fisher-Yatesの変種で600個のみシャッフルすればいいんじゃないかな
dequeueを固定長配列で実装した場合 データが2個以上含まれている時に 先頭からデータを取得した場合 先頭のインデックスってどう扱えばいいのですかね?
663 :
658 :2010/02/07(日) 01:01:11
皆さんありがとう。 うまく書けそうです。
普通にシャッフルして上から600個とってくるのでいいじゃない
QAlgorithm の質問しても良いですか?
だめです
>>662 deque(Double Ended Queue)ではなく
dequeue(キューからの要素取得)の事でいいのか?
どちらにしても質問の意味がよくわからん。
「先頭のインデックス」とは何の事だ?
それは「先頭からデータを取得した場合」の「先頭」と同じものを指してる?
任意の大きさのマスをランダム移動の一筆書き(斜め移動可)で埋めるプログラムを作っています 例えば3x3マスなら↓のように埋めていきます 123 649 578 ・周囲の黒マスの数が7だったら最優先でそこに進む ・白マスが分断するところには進まない というルールを作ることで10x10ぐらいなら数回試行すれば成功するようになったのですが もっと大きいサイズだとなかなか成功しないのです ランダム移動の奇抜さをなるべく残しつつ、一筆書きの成功率を上げるにはどんなルールを追加したらいいでしょうか? 目標は60x60の一筆書きを自動で完成させることです
ハミルトン閉路、巡回セールスマン、経路に適当な重みを付けて遺伝的アルゴリズム a-b-c |X|X| d-e-f |X|X| g-h-i
ナイトツアーのワーンスドロフのようなものか
>ランダム移動の奇抜さをなるべく残しつつ その奇抜さとは何かをとりあえずでも定義してくれないと、 あなた以外にルールを作りようもないと思うんだが。
>>671 「壁沿いに螺旋状に移動する」みたいに明らかにランダム性を損なうものでなければ何でもいいですよ
何が奇抜さを潰してしまうかは実装してみないとわかりませんから
ワーンスドロフの「次の移動先が少ないものを選択する」というのは参考になりました
奇抜さというものを数値化して評価関数を作る話になると思ってた。 すまん、俺が悪かった、無視してくれ。
uho
yees
ビット並列化手法って具体的に どんなアルゴリズムなのですか? 調べても全然でてこない
SIMDと一緒
これもビット並列化の一種
http://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);
文字列を分割する高速な アルゴリズムってありますか? 正規表現以外で
>>681 あのー教えてください
困ってるんですよ
お願いしますよ
文字列自体は操作しないで部分文字列の先頭位置と文字列長を扱えばいいよ
ありがとうございました 次のかたどうぞ
どういたしまして 次の方どうぞ
組込み向けで効率を考えたBCD変換アルゴリズムにはどんなのがありますか?
A->10
>>668 質問への答えとしてはズレているが、バックトラックって手もある。
「ぴーっぴーっ、ガッツ石松」
690 :
デフォルトの名無しさん :2010/03/03(水) 16:23:27
グラフを書く際に 例えばデータが17521〜18759の範囲の場合 下限を17000、上限を19000ぐらいにみたいなデータ幅よりある程度広い なるべく切の良い数値を求めるロジック見たいなものはないですか? 参考になりそうなヒントでもいいです。
割った後切り上げ切捨て関数呼んで掛けて戻すだけじゃん
自分で頭の中でやる時はどうやって数字を割り出してる?
range = 18759 - 17521
これを適当な幅(これはロジックも糞もないな)で分割して
先頭の値を
>>691 の方法で決める
やはり小学生にはプログラミングは難しいのか
696 :
690 :2010/03/03(水) 19:21:36
なんとかそれらしい形に range取ってその1割を上限下限に足して rangeの桁数を割る数に もっとシンプルにならないんだろうか。。。
697 :
デフォルトの名無しさん :2010/03/03(水) 19:40:50
log10を使うんだ
698 :
デフォルトの名無しさん :2010/03/03(水) 19:54:12
質問です 68円の買い物をして 100円支払い、32円お釣りを受け取るのではなく1 5 123円支払い、55円お釣りを受け取るのは何というアルゴリズムになりますか? わたしは実生活では上記のような支払い方をしていて、 目的は財布を軽くすることです 他にも支払いで使う硬貨の種類選択基準にどのようなものがあるか教えて下さい よろしくお願いします
>>696 ↓随分まえに書き込んだネタ
28 デフォルトの名無しさん 2007/04/13(金) 16:00:45
>>25 ずいぶん昔にやったな、オートスケール。
最小値と最大値の差を有効数字2桁にして、その2桁を元に
目盛りの分割数を 5, 7, 10, 12, 15 から選んで、みたいなことを
してたような…
>>698 財布の中身を全部出せば、財布に戻る硬貨枚数が最小になる
持ち金200円で105円の買い物をすれば残金は95円だろ
持ち金が100円2枚だろうが1円200枚だろうがとにかく全部レジに出してしまえば「95円」返ってくる
この「95円」をレジの人が最小枚数で渡してくれれば財布内の小銭枚数も最小になるってわけだ
質問者は(自分で調べたいから)アルゴリズムの名前を聞いてるんじゃないの?
名前なんて聞いてないと思うが
>>697 log10(x)とか使わねーw
log(x)の方が安定しそうw
値をlog10して整数化すれば、グラフの最大と最小の目盛りに使いやすいってこと。 安定は…よくわからん
>>700 え?
普通手持ちが1円玉200枚だったら1円玉95枚が残るべきでしょ?
>>706 1円玉95枚は両替する
ということを彼が言いたかったのだよ。
知らんが。
>>698 つまらない種類選択基準として「常に十分な額の通貨ひとつを払う」
というのはあるな…。財布をまさぐったり考えたりする手間を省ける。
>>708 それは100円玉一枚とか1000円札一枚という支払い方法ですよね
これやると2万円の買い物とかできなくなりませんか?
あと1円玉とかは使われないで貯まるばっかりですよね
>>709 持っている硬貨を全部店員に渡す
その後帰ってくるお釣りの最小枚数を求める(高い硬貨から払えば最小)
(店員はお釣りをどんな種類の硬貨でも払えるとする)
その時のお釣りのうち、最初から持っていた硬貨と同じものがあれば
最初から渡さなければいいので、
お釣りからその硬貨を引く
そうすればお釣りが最小になるコインの枚数が求まる
木構造があり、親子関係の配列としてが与えられてるとします。 どの要素がrootかはわかりません。 この時元の木構造を復元するにはどうするのが効率がよいですか? 1 2 3 4 5 6 7 ならば、与えられるデータは 1 2 1 3 2 4 2 5 3 6 3 7 ですが、与えられる順番はこの順とは限らず不定です
配列で表現してはいるが 復元するまでもなく、それはすでに木だよ そのまま処理するのがいい場合もあるので 最終的に何をしたいかによるな
rootを見つけなければいけないが データに矛盾がないなら、どこか適当なところから逆にたどって行き止まりを見つければいい
ありがとうございます
>>712 最終的にしたいのは木の同型判定です
4
5 6
7 1 2 3
入力がこんな木なら、これはサンプルの木と同じとみなします
つまりノードの番号に意味はなくて
接続関係が同じなら同じとみなします
なのでノードの接続関係だけを記述した
木が作れれば解けるかなと思いまして
>>713 rootを見つけるだけならどの点からたどっても良いっていう
簡単な事実に気付きませんでした
なんか難しく考えてて、トポロジカルソートとかしないといけないのかと
ちょっとやってみます
>>710 だからそれだと1円玉95枚帰ってくるべきところで50円玉と10円玉x4と5円玉になっちゃうでしょ
それが許されるなら相談するほどむずかしかない
店員に渡す枚数が最も多く
店員から返る枚数が最も少なくなる物を求めたいんでしょ
初期状態を1枚の硬貨と簡単化した時点で破綻してるよ
100円1枚、1円105枚を持っていて105円請求された場合 理論上は1円105枚を出せばいいけど、現実にそんな出し方するのは難しいよな。 「同一硬貨はx枚までしか出せない」って制約も必要だろう。
718 :
デフォルトの名無しさん :2010/03/05(金) 19:15:03
>>710 店員が最小の枚数でお釣りを返すことを暗黙に仮定しているから
ミニマックスではないな
そんなこといったら、極端な話最初のケースでいうならば
123円を払った際、自分が100円1枚と10円2枚と1円3枚で払ったとして
店の人が1円55枚返してきたら、最初から20円は渡さないほうがいいじゃん
そこんところはなんか制約ないの?
710のアルゴリズムはこれね
ttp://www.deqnotes.net/acmicpc/p0006/ 確かに最初に渡す枚数を最大にするっていう条件は考えてなかった
でもそれは支払い枚数が決まった後に
手持ちと比べて枚数が多くなるように等価交換すればいいんでないかね
>>714 木の同型判定は良く知られたアルゴリズムがあるので
車輪を再発明する前に調べるよろし。
>>719 715の指摘は国内模擬予選(の元問題)作問段階で話題になったところで、
支払う金額の部分金額で支払えたら駄目とか色々条件を考えたんだけど、
結局綺麗なルールにならなかったから諦めたところ。
(ルールを書きすぎるとそれを実装するだけの問題になっちゃうので)
ちなみにその解法は「全ぶちまけ」と内輪で呼んでた。
722 :
712 :2010/03/05(金) 22:41:56
>>721 > 支払う金額の部分金額
支払うコインの部分コインでちょうど に訂正
B+木作りたいのですが 参考になるサイトありますか?
はい。
アルゴリスズムの本で初心者から達人まで進化するための本を読む順番を1〜10の順番で教えてください。
パチンコ台のアルゴリズムの裏をかく打ち方を教えてください。
>>725 アルゴリスですか?
1.まずは指2本を使ってアナルを広げます…
アルゴリ涼むが何だって?
>>725 数学の知識があるならアルゴリズムイントロダクションか
アルゴリズムデザインを理解できるまで読むのが第一歩
あとはひたすら実戦
二項分布ってどうやって実装すれば良いのでしょうか? 数値が大きい時、途中式のpowで0が返ってきてしまいます。 boostの実装も見てみましたが、ifでの場合分けが多くてよくわからないです。 数学の関数を実装って、途中式のオーバーフロー/アンダーフローや計算速度を考えると難しすぎる・・・。
>>730 [0,1)の一様乱数をn個作ってp未満の乱数の個数を数えればOK
下手に階乗を展開するよりも正確
>>731 すみませんさっぱり分からないです。
具体的にnやpが何を表していて、「p未満の乱数の個数」がどういう物になるのでしょうか?
>>733 それは何度も見てますが、
>>731 の話と繋がらないです。
その記事のk,n,pの内、
>>731 はnとpしか出てきてないし、
求める数値は0から1の値なのに、「p未満の乱数の個数」は整数に見えます。
>>731 の回答は「二項分布を実装する」=「二項分布に従う乱数を生成する」としたときの答えです
boost::binomial_distribution も乱数を発生させるためのライブラリだから
>>730 2項分布の確率値を求めたいだけならば 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)
このように求めていけば発散しません
738 :
737 :2010/03/09(火) 00:16:32
すみません、まだ問題がありました。 確率密度関数は作れましたが、累積分布関数が作れません。 確率密度関数の返す値が、実数だと小さすぎて0になってしまうのです。 対数のままだと累積(足し算)できないし、どうすれば・・・。
nがそんなに大きくなければ、足し算する最大のもので正規化すればいい L=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に書いてあるように正規分布で近似するか 変形ベッセル関数を何とかして計算するとか 数値計算は奥が深い どんな解析式に対しても安全に計算できる方法はないから
>>739 なるほど・・・。
決定版といえるような方法はなかなかないんですね。
難しい。
ファイルシステム作ったときにやったなぁ
優先順序ソートについて教えてください。 以下のような入力データの場合 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列についてソートした結果がくずれてしまいます。 どのようにソートすればよいのでしょうか?
C列->B列->A列の順にマージソートでソートすればいいよ、たぶん
比較をA列ー>B列ー>C列の順にやればいいのでは A列が同じならB列で比較してB列も同じならC列で比較する
A列をソートした後B列でソート、とするんじゃなくて A,B,C列を同時にみながらソートしないとだめ ソートの種類はなんでも良くて ソートする際の比較関数がちゃんと定義出来てればうまくいく
DBに突っ込んでSQLで
>>743 じゃないけど、sortのアルゴリズムのコードもしくは擬似コードが
たくさん載ってる内容が新しめの本で良いものがあったら教えてください。
セジウィック・整列の前半にあるようなオーソドックスなのはちょっとふれているくらいでも良いです。
>>744 普通のマージソートは、安定ソートじゃないからNG
質問です。 問題自体は、小学生プログラマーでも分かるくらい単純なんですが… 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秒くらいにするような(笑)、根本的に画期的なアルゴリズムってのはありますか? それとも、除算はどうしても遅いものなのでしょうか?
>>750 gmpとかの多倍長整数ライブラリでは、まずニュートン法で逆数を求めてから乗算していると聞いた。
途中に出てくる乗算はFFTを使って高速化しているらしい。
743です。
>>744 、745、746、747、749さんありがとうございます。
安定ソートであれば、そのまま列が維持されるかと勘違いしていました。
比較関数の部分で、すべての要素について考慮した比較を行えばよいのですね。
ありがとうございます。
となると、挿入ソートのようなものを例で考えると、ループの中にさらにループで要素の比較を行うといった形をとるしかないのでしょうか?
>752 こんな感じで、もっとエレガントな方法もあるかもしれないけど 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
要素の比較は一ヶ所でいいでしょ
>>743 A列の {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 推す
>>753 、756さん
ありがとうございます。
>>753 さんのコードをもとに、がんばってみます。
ありがとうございました。
758 :
デフォルトの名無しさん :2010/03/19(金) 14:19:15
配列の要素をランダムに並べ替えたいのですが どうやったらいいでしょうか
シャッフル シャッフル
・先頭から順にループ └─・後ろのデータのうちランダムなひとつと取り替える。自分自身との交換あり
static int[] shuffle(int[] a) { for (int i = 1; i < a.length; i++) swap(a, i, (int)(Math.random() * (i+1))); return a; }
762 :
デフォルトの名無しさん :2010/03/22(月) 19:58:02
C#にてwavファイルを読み込み波形を表示するプログラムを作っています。 今は、全サンプル点を描画しているのですが、それだと時間がかかります。 適当にサンプルを間引くべきかと思いますが、間引き方について案をください。 あるサンプルおきに描画したら、描画は早くなりましたが、間引かないときと比べ表示される波形 が大きく異なってしまいます。
サンプリング定理でぐぐりなさい
765 :
デフォルトの名無しさん :2010/03/22(月) 20:20:42
サンプリング定理を考えると、データを間引いたらサンプリング周波数を落としたことになるので、 ローパスしないとエイリアスが発生するわけですよね。 うーん。じゃあまじめに全点描画するしかないのか・・・?
いや全点でなくてもいいんだが サンプル数が1/2以下にならないようにするのが味噌
767 :
デフォルトの名無しさん :2010/03/22(月) 20:39:23
表示する領域がWなら、W個の点を用意するという発想はダメだということですね。 イマイチどうすればいいのかわからない。。。というか全然
>>767 いやそんな感じの発想でいい
問題は「領域幅/描画点数」について
サンプリング定理がアドバイスしているということに気づくこと
アルゴリズムとは少し違うのかもしれませんが ローカルDBとサーバDBとの同期を行いたいのですが、 同期方法に関して良い文献が見つからず悩んでいます。 一般的な同期の手法など、良い仕組みがあれば参考にしたいのですが、 参考になるサイトなど有りますでしょうか? 例えば携帯の端末など、サーバにあるデータを一度取得するけど、 各々の端末内でもDBの更新や削除などが行え、 サーバと同期することで他人の変更も差分で同期出来る方法を考えています。 そのあたりのルール決めや、差分取得の方法、衝突時の処理などです。 物によって一から考える必要はありますが、 基本的な仕組みの解説があればと思ってるのですが、 よろしくお願いします。
冗長化ってことでいいの
771 :
デフォルトの名無しさん :2010/03/22(月) 23:47:39
>>768 うーん。わかりません。
もうっちょっと詳しくお願いします
>>772 ちょっと本題とは外れるけど試してない気がちょっとするので
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);
}
みたいなのとの速度比較はやった?
すでにやってるならごめん
>>772 こういう密な波形って違うアルゴリズム必要にならないのかな?
画像の一ピクセル幅に当たる時間での最大振幅を求めてその
長さの縦線を書くとか。
775 :
774 :2010/03/23(火) 00:56:36
>>771 で、サンプリング定理のことだけど、これを参考にするなら
間引きでも少なくとも横幅のドット数の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);
}
という風になるかな
さーて、きっとボロが大量にあるぞ…突っ込まれるうう
点の膨大な数の描画処理で遅くなってるだけでしょ 表示エリアのドットと一対一で対応する二次元配列を作成 何も考えずにサンプリングデータから二次元配列にフラグを立てていく 何も考えずに二次元配列のフラグを参考に点を描画していく これだけで実用レベルになる
分岐が大幅に減って実環境での処理効率が圧倒的に上がってるだろ そもそも遅い原因は全く他(描画)にあるはずだから、まずそこを改善しろと どうせ同じドットに集約される所に何万回と描画してるから遅いんだと言う指摘だ まぁスレ違いの領域だけどな
今回の件とサンプリング定理は全然関係なくね
>>776 が経験と確信があって言ってるのか
サンプリングとか良くわかんねーけどこれでいいんじゃねーの?位の感じで言ってるのか
周波数変換について軽くググった程度の俺には分からない
俺は何れの手法にしても全点走査は必須だと思った
そして
>>773 と
>>777 は正しく、
>>776 は間違ってるとも思う
点を打つのではなく線を引かないといけないので
>>777 は要求を満たしてない
>>782 点が並べば線になることから説明が必要か?
A*の高速化について参考になるものはないですかね? とりあえず必要最低限の領域に分割して領域経路を探索しようとしてるんだけど それでも8000ほどの区画に分かれてる だいたい90x90の区画になってるわけだけど 実装はとりあえずVB.Netでやって完全に最適化された時点でC++に移植して 並列処理で更なる高速化をするつもりだけど ただVB状態で端から端の検索に20秒くらい掛かる これはちょっと移植しても実用レベルにはならない遅さなんだけど 90x90で20秒ってのは普通レベルなの?まだ改善の余地が十分にあると思います? これが普通レベルなら根本的に探索アルゴリズムを考え直す必要がある
点だけだと連続にならない、連続にするには膨大なデータが必要になる
786 :
784 :2010/03/24(水) 01:41:55
糞ソース参考にしてたから無駄処理が入ってた 他のソース参考にしてやってみたら3秒に縮んだけどこんなもんですかね? まだ遅い気がする
>>785 >>772 の画像見て言ってんの?
標準的なPCMが1秒間に何万個の点で構成されてるかわかってんの?
実際問題50ms未満の時間をモニタいっぱいに表示して初めてドットが連続しない可能性が出始めるわけだが
拡大時の補間が考えられてないのは
>>773 >>776 >>777 全てで同じ。
話にならない馬鹿は黙るといいよ。
>>776 k_の計算とかバグだらけで意味不明なコードだけど、無理やり解釈すると
graph_size_xが1ならdataを0%から25%間隔で75%の位置まで3箇所だけ読み取ってminmaxで線引くって事でしょ?
で、上手に間引けましたと言いたいわけだ
うん、完全に間違ってる
789 :
776 :2010/03/24(水) 02:16:48
>>776 思いっきり間違ってた、すまん
誤:
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)));
mabiki()の中でなにやってるの? 単純に元データをk_stepずつ飛ばしながら読んでるだけ? 間引いた結果全部の点が偶然同じ値だったらどうするの? 当然元データには振幅があるけど、間引くとそのx座標は点になるよ? k_end==data_size-1になる事が無いのは問題ないの? ここからは仮定だけど、 要はダウンサンプリングすれば計算量が減るよと言いたいの? サンプリング定理は出現する最大周波数の2倍でサンプリングすればエイリアシングせんよーって言ってるだけで、 ダウンサンプリングする際に読み飛ばしはご法度 そもそもgraph_size_x*2にまでダウンサンプリングしちゃったら得られる物はy=0xの直線しかないんでないの
791 :
776 :2010/03/24(水) 03:01:19
> サンプリング定理は出現する最大周波数の2倍でサンプリングすればエイリアシングせんよーって言ってるだけで、
> ダウンサンプリングする際に読み飛ばしはご法度
指摘ありがと、
>>776 は撤回する
なあなあ、単に表示画面のXピクセル数全体とwavのデータ数全体を対比させて、 1ピクセルごとにwavのデータ数を拾ってくるだけでいいんじゃないの? ループの回数をデータ側じゃなくて表示側でやるだけの話なんじゃないの??
>>792 俺まったくの部外者で、音響関連全然知らないけど、たぶんそれだと少し問題があるかもしれない。
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は自然数) のとき、波がまったくなく、平らな状態となった。
たぶん、ピクセル単位で間引くと元の波形とは異なる図になる場合があると思う。
FFTだろう常考
>>784 ,786
俺も遅い気がするが助言は出来ないw
どこか間違えてるんじゃね?
遺伝的アルゴリズムってどのようにパラメータを遺伝子で表現したらいいのでしょうか? 例えばパラメータの1つが0から255までの値だとします。 これをそのままビットで表すと8個の0か1の値になりますが、 交叉した時、10進数にすると親とはかけ離れた数値になってしまう(突然変異と変わらない)気がします。
交差を勘違いしてる悪寒 10万要素の配列を最適化したい時に 10万要素の配列同士を要素単位で適当に交差させる、とか、そういう感じだよ
>>798 なるほど。
パラメータがA,B,Cの場合、子のパラメータは親1のA、親2のB、親1のCみたいになるっていう事ですね。
>>800 なるほど、10進数で近い値がビットでも近くなる2進数のような物があるんですね。
802 :
デフォルトの名無しさん :2010/03/29(月) 11:26:43
a_0....a_n∈unsigned int、 b_0...b_n∈int、 pow(b_0,a_0,)*pow(b_1,a_1)*...*pow(b_n,b_n)∈doubleの ときオーバーフローしないで pow(b_0,a_0,)*pow(b_1,a_1)*...*pow(b_n,b_n)を計算するアルゴリズムを 教えてください。
訂正 a_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)を計算するアルゴリズムを 教えてください。
ちなみに誤差が最小の奴教えてください intとdouble以外は使ってはいけません。
>>803 普通に計算してオーバーフローするのなら、計算結果がそもそもdouble型の値の範囲を越えているのでは?
真に誤差を最小にするのなら、途中の計算をすべて整数の多倍長演算で行い、最後の結果をdouble値に変換すればいいと思う。
そうでなければ、誤差が蓄積しないよう、pow(b_i,a_i)について、値が近いものどうしの乗算となるよう、計算順序を工夫するとか。
doubleの範囲を超えないことは保障されています。
>>806 計算結果がdouble型を越えないことが保証されるとき、計算結果がオーバーフローするような計算方法があるの?
2^33*3^(-1)とか
自己解決しました。
有効桁数が問題なのに言葉を知らないんだろうな。 なんか宿題スレのつもりで使う人がたまに出てくるけど、 自分が問題を理解していない時には、先にくだ質へ行ってからにして欲しい。 不具合の出るアルゴリズムを不具合の出ないアルゴリズムに置き換えるのは、 どちらかというとアルゴリズムの話というよりバグ修正の話だから。 先にくだ質とかで「何でオーバーフローすんの?」って聞いたほうがいい。 とりあえず、不具合の発生する a[] と b[] の具体的な例を書き込んでごらん。
>>808 double型ではなくint型を返すpow関数を使ってオーバーフローしてして、計算誤差を最小にしたいのであれば、
やはり多倍長演算を使うべきでは?
式変形を使う宿題か? いずれにしろスレ違いくさい。
>>810 int 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;
>>813 d*=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 型の最大値を超過するとオーバフローとなり計算結果に意味はなくなる。
前に話題に出てた多角形の三角形分割ってむずくない? ドロネー三角形分割について誰かわかりやすく教えて
むずくない
じゃあおせーてYO
三角形分割であって最小角が最大になるもののこと
>>814 もっと詳しくお願いいたします。
できればコードつきでお願いいたします。。
>>819 double 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; /* 型変換は不要。 */
821 :
デフォルトの名無しさん :2010/04/20(火) 02:21:40
COBOL?のコピー句をツリー状のデータ構造に起こしたいと思ってます。 簡易的に書くと 連番 名前 深さレベル 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`)
>>821 COBOLも満たしたい仕様も俺が何の仮想言語で書いてるのかもよくわからんが
なんとなくこんなものを書いてみる
&push(@data, $start); #番兵
for($seek = $start; $seek++; $start.depth < $seek.depth){
if($seek.depth < $seek.next.depth){
next;
}
&output($seek.name);
}
&pop(@data); #番兵消去
バッファの中身をソートするとして 問題は1次元から始まり2次元、3次元、4次元と対象が増えた場合 再起呼び出しでこういうのって出来る?
>>823 二次元配列(など)をソートしたいの?
適当に一次元参照してソートしたんじゃダメかい?
具体例出すのが早道だと思うお。
>>824 配列が何次元かは不明で1次元の時は1次元で2次元の時は2次元でソート
3次元の時はもちろん3次元で
>>823 data1 = [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]]
こういうことをやりたいのか?
ポインタで結合してるから*data **data ***dataみたいなもんだけど 何階層あるかの情報もあるから for(i=0;i<階層;i++){ sort(dataの階層のポインタ、子の階層の数) } みたいな感じでこのsort関数の中身は固定出来るのかな?
>>825 だから、多次元のデータは一次元に写像できるからソートには関係ないってば。
つ[boost::multi_array]
>>828 言ってる意味が分かった
あらかじめ次元の目印をつけた1次元バッファを用意してそれを並び替えろってことか
そういう方法があるのは分かってる
問題は関数のネストだけでそれが出来るか聞いてるの
>>830 つアルゴリズムスレ
>>831 多倍長って普通ソートには似合わない言葉じゃないかな
結局質問者は多次元データをどういうふうにソートしようとしてるの?
多次元データを辞書式にソートしたいのか、
それとも再帰的にソート(
>>826 )したいのか。
まあ何にせよループで書けるものは再帰で書けるから絶対に書けるんだけど。
C言語もどきを作ってるんですけど、演算子の実装って なんかの本で見たんですが、 式:項の加減算 項:因子の乗除算 因子:数字、または式 みたいに考え、それぞれ関数 foo1() { }
835 :
デフォルトの名無しさん :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(); } みたいな再帰でやるのが普通でございますか?
LISPに触れてみてはどうかと思った
構文解析だよね? 再帰でやるのが普通
再帰でやるというか 再帰になるというか
>>837 ,
>>838 ありがとうございます
そのばあいって、演算子の種類毎に関数作るモノなんですか?
足し算だけする関数とか、引き算だけする関数とか
それとも加減算はまとめて一個の関数とか
>>839 演算子の優先順位でまとめる
薄いのでいいからコンパイラの本を読んだ方がいい
演算子には優先順位があるが、普通はテーブルで 一まとめにする。最初はEBNF通り全部単関数で作っても良い。 二項演算子は右結合、左結合があるからそれぞれ分ける。 ?:の三項演算子もあるから分ける。単項も前置と後置で分ける。 最後に変数名やリテラルや括弧とかを処理する頭を作る。 括弧ならその中の式をさらに再帰的に解析する。
一回ぐらいなら手で再帰下降パーサを書くの楽しいよな。 何回もやると飽きるけど。
844 :
デフォルトの名無しさん :2010/05/06(木) 14:22:19
相手の位置によって発射角度を追尾するように変化させる砲台を書きたい その際、常に相手の位置に合わせるのではなく、 相手が現在の角度より上に居る場合は上に、下に居る場合は下に少しづつ向きを変えたい atan2で取った角度と現在の角度radの値を単純に評価すると、 atan2の角度が30度→-30度となった時にラジアンがPI/6->11*PI/6になって砲台が逆回転し始める。 なんかいい方法はあるだろうか。
取り敢えず、結果のラジアン値に2πを足してmod取ったら?
砲台が原点にあって向き(x軸となす角)がθ 相手の座標が(x, y)とすると -x sinθ+y cosθの符号でいいんじゃね?
現実の砲台には「あそび」がある
θ -= floor((θ+PI)/2PI)*2PI
atan を使わずに内積を使う。 そのとき、片方を90度回転させておく。 すると 846 になる。
二つのベクトルの内積は、ベクトル A に対してベクトル B が前を向いているかを符号で示す。 プラスなら前(同じ方向) 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 で算出した向きに設定しないとブルブルいうことになるので注意。
内積だと理論的ではあるけど、普通は外積を使うかな。
853 :
デフォルトの名無しさん :2010/05/08(土) 14:06:14
>>852 外積は2つのベクトルを右回りにするほうに向くんで、どっち
向きかで判定するってことね。はじめの2つのベクトルが
どちらもxy平面上にあるから外積はz軸方向を向くので
z成分だけ考えれば良くて、結局851が内積で考えたときと
同じ式になる。
他の考え方としては、(x,y)を-θだけ回転させた(x',y')のy'の
正負で判定するというのもある。回転行列を使うわけだが、
これも結果は同じになる。
854 :
851 :2010/05/09(日) 01:10:53
同じ式になるし外積の z 成分で良いのだが、外積の答えはベクトルなので、説明としてはあまりよくないと思う。 丁寧に説明するときには、出てきたベクトルと (0, 0, 1) との内積を取ることになり冗長だ。 個人的には内積での説明が、最もわかりやすいと思う。 それに、回転限界判定の最適化の際に、|A| * |B| * cosθを意識しておくことが役に立つことも、内積推しの理由。
自分の方に向かせたいという目的なら 内積が一番素直かもね
砲台の向きを角度で持っているなら、atan2-現在の角度を-π〜πに 正規化するのが一番素直な実装だと思うけど。
いや間違えた 内積はダメだわ やっぱ外積だ
>>855 1フレーム当たりの回転量よりも、現在のなす角が大きいかどうかの判定の最適化。
小さければ、atan やベクトル正規化で自機の方向に正対させないとブルブルすることになる。
砲台の動く速度は同じなんだろ? 線より左にあったら左に回して 右にあったら右にまわせばいいだけ。
一定速度で回して毎フレームコリジョンチェックすれば良い
配列の中身をソートするためクイックソートでやっています。 A[i][g]の評価値であるAFitness[g]があります。 AFitness[g]を大きい順に並べ替えているのですが、 同時にA[i][g]も並び替えを行いたいのですが、 いまいち考え方が思い浮かびません。 gの中にi=0〜nの値があってiの中身を評価してgの評価値を AFitness[g]に格納->ソート->A[i][g]もAFitness[g]の順に並び変えたいのです。 お知恵を頂けないでしょうか?
>>864 言語が分からんが、C++ならi,g,AFitness[g]を同じクラスに突っ込んで
AFitness[g]で大小を比較する比較関数書けばいい。
今度A[i][g]でなくA[AFitness[i]][g]で参照すれば並び替えたのと同じ キャッシュ等を考慮しなければ
わからないです。
並び替えであるgがg'に移った情報をインデックスすればよいのですが、
クイックソート内で行う必要があり、ややこしいです。
AFitnessの値を追跡してgがどこに行ったかを探索すればいいですが、
AFitnessの値が同じで、[i]の中身が微妙に違う可能性があり、
しっくりこない次第です。
>>866 詳しくお願いします。
qsortは比較に使うものだけを並べた配列のみを扱える、と思い込んでいるような気がする。 もしそうだったなら「qsort 使い方」でググって。 評価値とインデックス(あるいは元データ)の組の配列を評価値でソートすればいい。
土日を経過したし、もう解決してるかもね。 で、qsort() を使っているのか、自前でクイックソートを実装したのかによって回答が違うよね。 自前なら2個 swap() しろってだけの話しだし、流石にそれは無いのかな。
ども。eonet寄生虫だったので、・・・ 実は進んでいません。 qsortがあることを知りませんでした。自前のクイックソートの話でした。 swap() の意味がわからないのがつらいです。 ぐぐってみました。 構造体のやり方が載っていました。 具体的にはGA遺伝的アルゴリズムを実装しています(趣味と実益でです) A[i][g]iには遺伝子がgは個体格納用の配列です。 0からgの個体にそれぞれA[i]の遺伝子があり、その遺伝子の評価値が AFitness[g]となっています。AFitnessの順にならびかえているのですが。 単純なはなしなのですが、 ググった例題では構造体を使った例がありました。 しばらく考えてみたいと思います。
{[評価値, 対象]} を評価値でソートするんじゃなくて {[評価値, インデックス, 対象]}をソートすればおk ってこと?
>>872 いいえ、対象も並べ替えるならインデックスを追加する意味はありません。
対象のサイズが大きいからソートの時に対象自体を並べ替えるとソートが遅くなります。
代わりにインデックスを並べ替えると対象のサイズがソート速度に影響しません。
だから{[評価値, インデックス]}をソートすればOKです。
処理の単純さを選ぶなら{[評価値, 対象]}、
ソート速度を選ぶなら{[評価値, インデックス]}です。
多倍長整数で底10のときの桁数log10を求めたいのですがどのような方法が定番でしょうか。 JavaのBigIntegerで行っていますが、これは底2の桁数log2の整数部まではサポートされていて、 頻繁に使う10はサポートされていません。 少し見た限りだと内部では底は2^31あたりで1e+8で連続div+remして文字列の連結をしてるようです。 底2の桁にlog2[10]をかけたりも出来ますが+/-1の誤差が出るので正確に求めるにはコード(分岐とステップ数)が増えるのでメンテナンスが大変になります。 いったん底10でStringにしてlengthが一番単純だと思うのですが他の方法があればを教えてください。
>>874 底10で文字列にしてlengthが基本.
文字列を必要な分だけ覚えるようにすれば若干速くなるけど
たいしたことはない.
もし本当に早くしたい(=底10を連発する)なら
多倍長整数をそもそも10のベキ底で用意するべきで,
COBOLなんかはそういう風に設計されている.
>対象も並べ替えるならインデックスを追加する意味はありません。 単に、ランク順にならびかえて、その並びになるように評価元の配列も一緒に 並べ替えのよりよいやり方があったらなぁというものだったのですが、 なんかよくわからなくなったので、もうこれぐらいでいいです。 いろいろありがとうございました。なげやりでもうしわけないです。
>>873 いや敢えて”対象”って入れたのはExcelで複数列を選択してソートするような感じ
{評価値, インデックス}だとソート対象に”対象”が入ってないから出鱈目になるっしょ
ああ,でも{評価値, インデックス, 対象}を新たに”対象”として拡張してソートすると,
要素毎の比較でちょっと時間かかるか
対応する対象を追うためのインデックス。出鱈目になどならない。 対象自体をソートしてしまったらインデックスが出鱈目になる。
> 対象自体をソートしてしまったら そうならないように{評価値, インデックス, 対象}をソートする形なん
md5のハッシュアルゴリズムでビット列を辞書順に調べていった場合初めて重複が現れるのって何バイトめぐらいですかね? そういう実験データってどこかにないですかね
日本語で
>>880 それは確率か統計の問題だろ。
馬鹿か、おまえは。
いや実際にどのくらいで出てくるのかなって興味ない? 128bitなんだから16バイト以内で必ず当たるのは 確かだけどさ。
884 :
デフォルトの名無しさん :2010/06/08(火) 09:15:20
昇順と降順で違い出るだろうね 周期的じゃないだろうから
0から始めて最初のが見つかるまでのバイト数と 2つ目以降が見つかるまでのバイト数は違うだろうし 「始めて重複が現れる」ってのは意味がない 要するに素数の出現する間隔みたいなもんで ずっと出ないときもあれば連続して出るときもあるかも知れない 確率でしか評価出来ないと思う
128bitと言うのは簡単だけど手元のPCで3バイト=24bit分の 総当りに30秒かかったから、128bitの総当りには1.15E27年 かかる計算だ。100万台ぐらい用意したって全く追いつかないよ。
何バイト以下ならハッシュが重複しないことを保証できるかってこと
16バイトのファイルのビット数が128bitだからこれだけで終了なので、 それより短い長さのファイルもあることを考えると16バイト以下の条件 でハッシュが重複するファイルがあるのは確か。でもじゃあ15バイト 以下なら重複がないといえるかどうかという問いに答えるのは難しそう。
リーマン予想を証明するよりは簡単なのかな
1 と0 が一緒の場合もあるから決まりはないだろ。
129bit あれば、鳩ノ巣原理によって必ず重複するよ!
892 :
デフォルトの名無しさん :2010/06/09(水) 21:48:18
ボーン変形のプログラムを解説して下さい
純粋に数学的な話しなら、ハッシュ値の出現確率は等価なんだから簡単だろ。 現実問題なら、たとえばテキストファイルならどうよ? 2バイト文字は含むのか? サンプルの規模は? そんなことも考えないで「確率は?」とかバカすぎる。 この手の話題では、自分がバカだと思うヤツは黙ってろ。
>>893 バカと言う自覚がないのがまずバカの十分条件だろ。
バカだなぁw
895 :
デフォルトの名無しさん :2010/06/12(土) 22:41:18
フィボナッチヒープについて調べているのですが wikiを見てもよく理解できなかったので、簡単に教えていただけないでしょうか。
まず、Wikipediaをwikiを略すのをやめるとこから始めようか。
897 :
デフォルトの名無しさん :2010/06/13(日) 09:05:36
何がどう理解できないのか説明できないようならプログラマやめちまえ
899 :
◆dmYlwlD4Tc :2010/06/13(日) 23:49:53
こんなスレみてる奴はプログラマじゃねーから そんな事すらわからないのか
どうでもいい方向に話題を拡げる奴は阿呆
n個の正の整数 それらの合計はm 並び替えて同じものは同一とみなす 上記の条件を満たすすべての並びを 再帰や可変長バッファを使わずに かつスキップ無しで出力することって可能?
m を素因数分解して m = P1^N1 + P2^N2 + ... + Pn^Nn の, N1 ... Nn が取りうる, すべての組合わせを出力すればいいのでは? # そうゆう問題じゃなかったらごめん
goの出番だな
たとえばn = 4、m = 6だとしたら 6 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 が欲しい答えです さらにループで調べて合致していないものを捨てるという方法は無しで 漸化式のように前の解から次の解が求められるようにしたいです
n= 4 m= 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 思いつきで書いてみた。言語は趣味 デバッグ?何それおいしいの?
実行してないけどこれ境界エラーじゃね?
>>904 その例は先頭桁の大きさの順に並んでいますが、
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
なるほどスッキリしました 桁数で並べ替えればよかったんですね どうもありがとうございました
整数1〜n^2で構成されるn次元の魔法陣をもれなく生成せよって問題なんだけど 真ん中の一番上を1と置いて〜みたいな特殊な解を使わないとしたら 方程式解いて変数を減らせるだけ減らしてあとは総当たりでやるほかない?
とりあえず、それはn次元の魔法陣ではなく、全て2次元魔方陣だ
次元と言う言葉には色々あってだな・・・
どちらにしろ宿題は自分でやる事だな
×魔法陣 ○魔方陣
魔方陣って全部一辺が奇数だと思ってたよ。偶数の物も含まれるんだ。
ハァ〜サッパリサッパリィ
>>909 O(n)でやる方法はある。
ただし、答えは尻から出る
二次元の円の重なりを判断するのに、 sqrtを使わない方法ってある? もしくは、少しでも軽い方法。 現状はこういう感じ。 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
>>917 更に処理時間を減らしたいなら、radiusの2乗値をキャッシュ。或いは事前に計算。
>>919 (a.radius + b.radius)^2 ≠ a.radius^2 + b.radius^2
なので、radiusの2乗値は事前計算では駄目。
それほど極端な差はないかもしれないが、除算は値によっても変わる場合があるので要注意。 尤も、整数定数除算は乗算で実装してくれるコンパイラも多い。 それよりも何よりも、float ⇔ double ⇔ int の型変換が遅いのでその辺りも注意。 つーか、この辺りのノウハウは最適化スレの方が詳しい。
dist2 < (a.r2 + b.r2 + 2 * a.r * b.r)かな
>>921 いまどき四則演算の速度差なんて気にする方が無駄。
>>923 (a.r + b.r)^2の方が、加算1回乗算1回で済むので計算量が少ない。
>>924 Intelは除算高速化回路を最新のCore iシリーズに入れたわけで
もっともリコンパイルなしのレガシーソフトウェア対策がメインではあるんだろうけど
>>922 なるほど! スレ違いどうもすみません。最適化スレ読んで勉強してきます。
>>923 そういう工夫はアルゴリズムスレ特有ですね。
>>924 ご忠告ありがとうございます。無駄なところに拘らないように気をつけます(`・3・´)
>>888 当たるまで調べでもしない限り、確実にあるといえるのは16バイトのときだろう。
確率の話をするなら、普通はもっともっと早い段階で見つかる。
ていうか、なんで「誕生日のパラドックス」の話が出てこない?
928 :
デフォルトの名無しさん :2010/07/03(土) 16:37:47
データサイズ1バイト、要素数6の待ち行列を実装してるんですが、 適当なアルゴリズムってありますか? 具体的な用途を言うと、USB-HIDキーボードのキーバッファです。 Nキーロールオーバーに対応させるため待ち行列で管理します。 今の実装は単純な配列とmemcpyです。 リンクリストやリングバッファにすることも考えましたが、 待ち行列とはいえキーを離したときにデータの不特定箇所の 削除が発生するので微妙でした。
160bitのshaハッシュがあります これを0000.....を基点として円を描きたいのですが つまり0000....とfffff....は同じ点になって ある中間のハッシュαがあったときにこのαの角度を計算したいのですが なんか簡単に出来る方法ってありますかね?
2πα / ffff では駄目なの?
言うのは簡単だけど160bitの演算クラスを作るのはかなり大変なことなわけで もっと簡単に普通のdoubleとかだけ使ってやる方法はないかなと
ああちなみに厳密じゃなくてもいいですよ どうせグラフにしたら1度単位くらいでしか見えないだろうし
って書いてて気がついた 上位32bitで分割すればいいだけでしたw
そうとう大きな円でも上位 32bit 以下は誤差なので、 上位 32bit を取り出して 0x00000000 から 0xffffffff を、0 から 2π(ラジアン)に マッピングすればいいんちゃう?
あ、リロードしてなかった
doubleでもループ回して double 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 と、かなりいい感じになった。
>>928 キャッシュ効率考えたらそれでいいんじゃないの?
>>928 8バイト単位にした方が(CPUにもよるけど)若干効率いいかも知れない。
>>928 待ち行列(キュー)の実装方法によって挙動がかわるのが理解できないんだが…
普通はリングバッファでやるのが効率的だが、なぜまずいの?
アルゴリズムスレで聞くほどの問題なのかわからんけどどこで聞けばいいかわからんので聞きたいんだが [0,1)の実数乱数から、かたよりなし、棄却なしに[0,1]と(0,1)の実数乱数って作れる?
[0,1]と(0,1)の区別なんて無意味だろ。 0と1の間の数は非加算個といって無限より一杯あるんだぞ。 その中の1と0が当たる確立なんて0としかいいようがない。
閉区間と開区間は同相写像がないからまともに実数で考えるなら 不可能。コンピュータだから所詮は整数だと思うならどうマッピング するかだけの問題。
ふう
同相写像がないから、という理由は変じゃないか? 連続でなくても全単射があればいいわけで(ないけど)
区間を広げて一部をとる、ではだめかね
>>945 棄却なしだからだめ
可能性があるのは、毎回、値を少しずつずらすくらいだな
無限回試行したときに均等になればよい
棄却なしの場合はと言ってますぜ
>>940 有限精度の浮動小数点を仮定する。
以下のようにしたら一応棄却はしてない乱数が作れる。
十分な大きさのbool配列を固定小数点として使い、それぞれのbitを
rand( [0,1) ) が0.5以上
→ビットを1に
それ以外
→ビットを0に
のように計算する。その結果を浮動小数点に直す。
あ、十分な大きさとってしまったら、下位ビットを棄却してることになるね。 浮動小数点の精度をちょうど満たすところで止めるようにしないと。 まぁ、どうせ揚げ足取りみたいな回答だけど... でも有限精度の小数点なら、かたよりなしって考え方そのものが若干微妙だし、 有限精度じゃないのなら表現がまず難しい。
(1-delta)で割っちゃだめなん?>[0,1] 指数が0.5で仮数が全部1な奴
棄却って何ですか?
本当の意味での(無限精度の)実数の場合: そもそも[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にすることで実現できる。
元が64bitの乱数だとdoubleにする時って、小さい値はデノーマライズされてるの?
>>953 >存在したとしても、ちょうど0, ちょうど1が出る確率はないから、そのまんま[0,1],(0,1)として使える
いやそれを言ったらちょうど0.5が出る確率もちょうど1/πがでる確率もないことにならん?
>>956 無限精度だから
lim(x→∞) 1/x=0
になる、んじゃね?
2つの乱数があったとして 両方が(1.0-delta)だと(1.0-delta)+(1.0-delta)って、四捨五入で2.0になっちゃうの?
>>957 だからその論法だと0と1の間の任意のxについて出る確率が0って
ことになるだろ。測度とか確率密度とかでぐぐって勉強するといいよ。
簡単にいうと閉集合と開集合は長さが一緒だから 確率も一緒ってことだよ。
「[0,1)で一様な実数乱数を生成する」って時点でもう現実に実行することは不可能なのだ。
有限のリソースで記述できない数はいくらでもある。
>>959 任意の特定の値が出る確率は全て0だよ。当然。
連続的な確率密度関数から値求めるときって、ちょうどxが出る確率なんてのは意味が無くて、 xからyまでの間の値が出る確率を求めないといけないんじゃないの? ここで何を言おうが、メモリが無尽蔵にあろうが、コンピュータでは連続値を扱えないけど。
無限の広さを取る二次元空間に存在する点p_1, p_2, ..., p_nを、左上と右下の二点からなる矩形qと衝突判定したいんですが、 有効な方法はありますか? 一度p_nを座標からハッシュして有限の領域にマップしようと思ったのですが、 矩形qを成すそれぞれの座標軸の区間[x_1, x_2], [y_1, y_2]内の点q_a, ..., q_bをまとめて得る方法が分からず、頓挫しました。
矩形なら問題ないんじゃね
「恐らく」=「根拠無し」
脳内最速
適当なこと書けば、誰かが答えてくれる。 実は催促なんだろ。
梅最強
>>966 は空間が固定だから無理。
実際の所、kD木で解決したから問題なし。
妄想で出鱈目を書かないように。
それをやっているPNGが特許にひっかかってないなら平気じゃない?
二つの円が重なったひょうたんの様な図形から二つの円を抽出するアルゴリズムありませんか? 図形はひょうたんの様に10%程度重なってるものから鏡餅の様に80%重なってるものまでを対象にしています。 円の直径は可変です。できれば2-5程度の複数円を抽出したいと思ってますが、2個すらできてません。 今日午前中潰して考えたんですが、なかなかいいアイディアがでません。 よろしくお願いします。
図形がy = f(x)で与えられているなら、f'が0になる点がそれぞれの円に2点ずつあるはずだから その間の中点を二つの円で求めれば、半径と中心が出る。 f'が0な点がfで2つしかないなら二つの円の中心を結んだ点がy軸に並行で上の方法ができない。 その場合はx軸とy軸を交換して処理すれば良い。
977 :
デフォルトの名無しさん :2010/08/17(火) 15:37:00
>>976 >>975 はビットマップ画像から中心座標と半径を求めるということじゃないかな
とりあえずこんな感じでどう?
1. 輪郭線を抽出
2. それぞれの円毎に輪郭線を分割(輪郭線の傾きが急激に変わる箇所で分割)
3. 輪郭線ごとに輪郭線上の任意の2点で接線に垂直な線を求める
4. 求めた2本の線の交点が1つの円の中心点
5. 円の中心点と3.の2点までの距離が半径
中心座標と半径を遺伝子にしてGAするとかどうだろうか?
ルービックキューブは20手以内で必ず解ける、数学者チームが特定
2010年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
980 :
975 :2010/08/18(水) 09:35:03
どもです。
>>976 後出しで申し訳ありませんが、図形はビットマップなので最初の式が作れません
>>977 テスト画像でやってみました、いい感じで求まりました。
ありがとうございます。
実際にはビットマップの解像度が悪いせいで2の抽出が困難ですが
それは別問題なので解決とさせて頂きます。
どうもありがとうございました。
>>978 これでも求まりそうです、
特にビットマップの解像度が低い輪郭に相当量のノイズが混入してる場合は
むしろベストかもしれません。
まだ未挑戦ですが、これも一案として試行錯誤してみます。
>>980 問題の性質上、円は作業面に対して完全に内包されていて、全体が1つのオブジェクトを
構成しているんだから、2値化して、左上からラスタスキャンかけて、最初に見つかった
オブジェクトの要素から、右方向へ輪郭を追いかけていけば細線化する必要はないんじゃないか?
次の点が今まで辿ってきた要素から予測される方向以外へ向いているときその点を弧の接点と見なす。
最初の点は弧の頂点のはずだから以降の判定は容易だよね。
多少先読みすれば、同じ半径の円が少しだけずれて接しているような場合でも切り分けられるんじゃないかな。
ずっと追いかけ続けて、元の点に戻ってくれば走査終了。後は接続点から少し離れた充分にこの一部である
2点を使って計算すれば、誤差もすくなくなるかと。
983 :
975 :2010/08/18(水) 10:25:27
>>982 細線化ってのは別にビットマップとして線を出してるわけではないです。輪郭点の配列です。
ビットマップ上の円は上下左右方向でドットが一列に並んでしまうという宿命があるんです。
ある程度小さい(解像度の低い)円になるとそれが無視できなくなるんです。
その辺の判定をした後でないと、半径探しの為に必要な適切な点が判定できませんので
細線化したデータはメモリに保管しておいたほうがベストと判断しています。
15000個のdoubleを昇順にソートして小さい順に3000個得る作業をできる限り高速に行いたいです。 残りの12000個は必要なく、また安定でなくても良いです。 どのようなソートが適しているでしょうか? ソート後の小さい方から一部だけしか必要でない場合には速くなるような方法があるのでしょうか?
>>984 普通に考えるとソートを途中で止めるだけでいい気がしますが
データに特に特徴がなければクイックソートでいい気がします。
>>984 なんか面白そうな話だな。
最初の3000個だけ旨く得ることができたら爽快だろうな。
クイックソートを途中で止めると出来ると思う。
987 :
986 :2010/08/18(水) 11:27:47
いかん、被ったorz
最初からデータを昇順に格納しておく
STLのpartial_sort()はヒープソートだな
上位 3000 がソートされている必要が無ければ(上位 3000 でありさえすればよいなら)、クイックソートを途中までするのがいい。 STL でいえば nth_element()。 上位 3000 がソートされている必要があればヒープソートを途中まで。 >989 にあるように STL の partial_sort()。
991 :
984 :2010/08/18(水) 15:01:38