計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 477 名前：デフォルトの名無しさん mailto:sage [2007/03/06(火) 21:20:05 ] 空間を分けるってちゃんと図形の配置を考えてやるの? そうじゃないならどこかで打ちきるわけだから計算量は何分の一かになるだけ それに重なってるところは分割できないので結局全探索になる 478 名前：462 mailto:sage [2007/03/07(水) 00:33:13 ] 473氏の方法をちょっと変えた物で、無事実装完了しました。今のところい い感じに動いています。ありがとうございました。 479 名前：デフォルトの名無しさん [2007/03/07(水) 23:42:48 ] 高卒でしかも数II？とか勉強いたことない俺にはまったく理解できないんだが どうすりゃいい？ 480 名前：デフォルトの名無しさん mailto:sage [2007/03/07(水) 23:44:26 ] 絵を描いてみる 諦める 481 名前：デフォルトの名無しさん mailto:sage [2007/03/08(木) 00:10:43 ] >>479 余り気付かれていないが、高校生ではなくても高校レベルの数学を 勉強することはできる。 482 名前：デフォルトの名無しさん mailto:sage [2007/03/08(木) 07:00:17 ] >>477 おまえ他人の言ってる事理解してないよ でしゃばるなカス 483 名前：デフォルトの名無しさん mailto:sage [2007/03/09(金) 00:58:56 ] >>482 理解できてないといって理由を書かない 484 名前：デフォルトの名無しさん [2007/03/10(土) 23:39:52 ] 自然科学なんかだと、実測データをグラフにプロットしたあと、なめらかな曲線でつないだりしますが、 そういう曲線を計算するアルゴリズムはありますか？ 485 名前：デフォルトの名無しさん mailto:sage [2007/03/10(土) 23:47:55 ] つ[Excel] 一般的なところで、一次回帰とその応用である対数回帰指数回帰冪乗回帰、それと二次回帰程度知ってればなんとでもなる。 486 名前：484 mailto:sage [2007/03/10(土) 23:49:18 ] ググってたらcurve fittingと呼ばれている問題だと分かりました。 すれを汚してすいませんでした。 487 名前：デフォルトの名無しさん mailto:sage [2007/03/10(土) 23:50:07 ] >>485 キーワードありがとうございます。 調べてみます。 488 名前：デフォルトの名無しさん mailto:sage [2007/03/11(日) 02:21:41 ] 最小二乗法とかね 489 名前：51 mailto:sage [2007/04/15(日) 21:22:27 ] SHA-1のハッシュを求めるプログラムを作ろうと調べていて ttp://homepage2.nifty.com/bkclass/doc_sha1.html のサイトを見ていたのですが、 他に参考になるサイトはありませんか？ 490 名前：デフォルトの名無しさん mailto:sage [2007/04/15(日) 21:54:51 ] Wikipedia(EN) 491 名前：デフォルトの名無しさん mailto:sage [2007/04/24(火) 04:03:28 ] 計算アルゴリズムには限界があり、結局は全部探索したほうが良いって結論？ 492 名前：デフォルトの名無しさん [2007/04/26(木) 00:56:22 ] そーでもないと思う。問題が大規模な場合はアルゴリズム使わないと無理だね。 でも、ノイズなんかの問題で理論的に最適な解が微妙な場合だったり、 問題が小規模で全探索で十分満足できる結果が得られるなら、全探索が 安定してるし実装が楽だからいいね。木構造はメモリリークよくやっち ゃうし。 493 名前：デフォルトの名無しさん [2007/04/26(木) 01:28:59 ] ２４シーズン�Xで解析に、独自のアルゴリズムを使って出す、とか言ってた。 494 名前：デフォルトの名無しさん mailto:sage [2007/04/26(木) 05:30:17 ] OR 495 名前：デフォルトの名無しさん [2007/05/01(火) 21:40:37 ] 今日専門の方でアルゴリズムの授業が行われたんですがその際この3問だけどうしてもわかりません 何方かこの3問のフローチャートがかける方が居ましたら教えてください 1問目：成績判定１ アルゴリズムの点数を入力して、80点以上のとき「Ａ」、60点以上80点未満の時「B」、60点未満の時「Ｃ」 と出力するフローを答えなさい 2問目：成績判定２ 英語と数学と国語の点数を入力して英語の点数が80点以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力するフローを答えなさい。 なお、数学と国語の点数がどちらも80点以上の時を一つの選択処理にすること 3問目：成績判定3 2-12.成績判定2の選択処理の部分を一つにまとめなさい 選択処理部分 英語の点数が80以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力する 496 名前：デフォルトの名無しさん [2007/05/01(火) 21:50:36 ] アルゴリズムじゃない。 そんくらいのフローチャートは基礎中の基礎だろ。本見ればわかるだろ。 497 名前：デフォルトの名無しさん [2007/05/01(火) 22:19:41 ] それが問題集しかもらってなくてわからないんですよ 498 名前：デフォルトの名無しさん mailto:sage [2007/05/01(火) 22:34:38 ] >>495 ttp://www.cs.takushoku-u.ac.jp/caed/kisosemi/k7/FlowChart.html これみりゃ大体わかるだろ。 いまどきフローチャートを書かせる問題ってのも、どうかと思うけれど。 スレ違いsage 499 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 14:45:41 ] 問題集しかもらってなくてわからないとか言うんだったら、 2chで質問する前にググれよ。っていうか授業ちゃんと聞いた上で わからないのであったら講師や友達に聞け。 500 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 19:47:24 ] ぐぐれる香具師 友達いる香具師 は 2chで質問しない 501 名前：デフォルトの名無しさん mailto:sage [2007/05/04(金) 00:08:57 ] 友達の作り方を教える本でも買った方がいいと思う。 502 名前：デフォルトの名無しさん mailto:sage [2007/05/04(金) 18:07:54 ] おとうさんはネットで調べても作れなかったけど 503 名前：デフォルトの名無しさん [2007/05/09(水) 01:56:23 ] グラフ探索でダイクストラやA*より良いのない？ それはそうとA*探索はぐぐるのが難しい。 504 名前：デフォルトの名無しさん mailto:sage [2007/05/09(水) 10:12:59 ] >>503 「Astar探索」とかでググってみたら？ ちなみにA*の場合、heuristicsがadmissible（各ノードから目的地までの予測コストが実際のコストを決して上回らない）でconsistent（いわゆる三角不等式が成立）なら、必ず最適解を返すよ。 それよりも良いってのは、heuristicsを設計できない場合ってこと？ 505 名前：デフォルトの名無しさん mailto:sage [2007/05/10(木) 07:32:41 ] どんな探索かわからんし、「良いの」って意味もわからんなあ。 506 名前：sage [2007/05/11(金) 04:14:25 ] >>504 そうですね、良いヒューリスティックを設計できない時です。 近似解法含め、良いのを探してます。 >>505 たしかに「良い」ってのはアバウトでした＾＾； 主観的にでも、よさげなアルゴリズムがないかなぁと。 検索してもダイクストラばっかり引っかかるもので。 507 名前：デフォルトの名無しさん mailto:sage [2007/05/11(金) 04:15:48 ] すみません、間違えて名前欄に書いてしまいました・・・ 508 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 10:47:07 ] 最短路探索ってことでいいの？ だとしたら、厳密最短路はたぶん理論的には Dijkstra が最良で、 実用的にはヒューリスティックに頼るってのが現在の理解だと思う。 （現在行われてるコンテストでもそんな調子だよね） 近似最短路はヒープ操作を手抜いたり、三角不等式を気にせずに ヒューリスティックを突っ込んだりするくらいだけど、 グラフが何の性質も持たない場合は性能評価が難しいところ。 509 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 16:40:43 ] ヒルス達がやってる６４個のソート問題ってどんな問題？ 510 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 16:44:37 ] クイックソート問題 511 名前：503 mailto:sage [2007/05/13(日) 18:40:21 ] つまりのところ、厳密解を求めるなら、あまり良くないヒューリスティック を用意した時、A*（と色々な改良版）が最速ってことですか。 というか、授業で習ったダイクストラとA*しか知らない物で＾＾； 近似についても、微妙な改良版くらいしかないって事ですね。 512 名前：デフォルトの名無しさん mailto:sage [2007/05/13(日) 19:42:30 ] >>511 とにかく実行速度をなんとかしたいという実用的な要求なら、 問題にあったヒューリスティックとヒープを設計して A* が たぶんもっとも現実的だと思う。 近似は、微妙な改良版といっても、たとえば幾何グラフとかなら 普通の Dijkstra と比較して一億倍以上早くなるケースもザラなので、 具体的な問題を見ないとなんともいえないところ。 513 名前：503 mailto:sage [2007/05/15(火) 01:35:21 ] ありがとうございます。じゃヒューリスティックに精を出してみることに します。ちなみに問題は経路探索です。 514 名前：デフォルトの名無しさん mailto:sage [2007/05/15(火) 22:13:04 ] >513 ちなみに、カーナビの経路探索だと、ネットワーク側の方を階層的にいくつか持って切り替えることによって高速化してる。 現在地、目的地近辺では全道路のネットワークで探索、それで見つからなければ国道以上のネットワークに移って探索、 さらに探索する場合は高速道路のみのネットワークに移って探索、みたいな感じ。 もちろん最適解は出ないけど、そもそもカーナビの場合、計算で出てくる最適解が、ドライバーにとって最適になるとも限らないしね。 515 名前：503 mailto:sage [2007/05/15(火) 23:00:45 ] あぁ、なるほど、中距離の探索とかで、たまにすごくアホな間違いをするの はそれが理由なんだ。 516 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 01:49:50 ] いや 渋滞回避してるだけだろう 517 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 07:24:16 ] pc11.2ch.net/test/read.cgi/jisaku/1179911252/ 上記スレで強制NaNの計算でインテル不利にするベンチが論争を呼んでますが 極端にAMD不利にする方法を探しています。 では。 518 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 16:03:47 ] 多倍長演算の割り算のアルゴリズムで たとえば521を21で割るとき ↓ まず521が三桁で20が二桁だから答えも二桁だろう ↓ ２桁目を決めよう ↓ 答えは10かな？21*10＝210で521より小さい ↓ じゃ20かな？21*20＝420＜521 ↓ じゃ30かな？21*30＝630＞521（もし90でも超えなければ二桁目は9にする） ↓ 大きくなったからおそらく答えの2桁目は2だろう ↓ 次は１桁目・・・ こんなのを考えたのですが、もっと良い方法はないですか？ 519 名前：デフォルトの名無しさん [2007/07/10(火) 16:04:24 ] age 520 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 17:02:29 ] 何このマルチレス 521 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 20:02:17 ] 10,20,30... だったら時間掛かるだろ 522 名前：デフォルトの名無しさん mailto:sage [2007/07/10(火) 21:23:37 ] 自分で考える前にまず一般にどういう方法が使われているかを知れ せっかく苦労して自分で考えついたとしても それが既にみんなが普通に使ってるものと同じやそれ以下だったら悲しいだろ？ 523 名前：デフォルトの名無しさん [2007/08/15(水) 23:41:39 ] ss.nkk.affrc.go.jp/library/publication/seika/seikajyoho/2003/15/15.html に記述されている、 図４の(a)から(b)の結果はどのようなアルゴリズムになりますか？ 524 名前：デフォルトの名無しさん mailto:sage [2007/08/16(木) 00:12:41 ] マルチうぜえ 525 名前：デフォルトの名無しさん [2007/08/18(土) 19:37:21 ] ウィキペディアでB木の項を参照すると、 B+木やB*木というものが存在するとに書いてありますが、 どういったものですか？ >（厳密にはB木の改良型であるB+木やB*木を使うことが多い) 526 名前：デフォルトの名無しさん mailto:sage [2007/08/18(土) 20:07:24 ] B+ は B であって、キーを葉にのみ格納するもの B* は B で、子の比が 1/2 だったところを 2/3 にしたもの wikipedia の情報は不正確だから参考にすんな ちゃんとした教科書とか論文を参照すれば分かるだろ 527 名前：デフォルトの名無しさん [2007/08/18(土) 22:38:43 ] >>526 ありがとうございました。 ウィキペディアから引用したら怒らせてしまった様で。 たまたま名前が載ってたから出しただけです。 B+木B*木は名前だけは以前から知ってましたが、 ググっても関係しそうなのは引っかからないですね。 本は アルゴリズム事典 はじめてのアルゴリズム入門 アルゴリズムとデータ構造 など持ってますが、載ってないみたいです。 >教科書とか論文 できればこれのポインタ教えてください。 528 名前：デフォルトの名無しさん mailto:sage [2007/08/18(土) 23:24:10 ] >>527 誰が怒っているの? 529 名前：デフォルトの名無しさん [2007/08/19(日) 03:52:13 ] >教科書とか論文 できればこれのポインタ教えてください。 530 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 07:29:10 ] >>527 B-plus-tree とか B-star-tree で検索すればいくらでも出るんだけどね。 教科書については、そんな一般的なアルゴリズムの本には あまり出てなくて、データベースよりの本を見ないとダメ。 R. Ramakrishnan, J. Gehrke, "Database Management Systems", 3rdEd. McGlaw-Hill, 2002 まあ次のサーベイ論文がよくまとまってるので、これを読んでおけば十分だろうけど。 D. Comer, "Ubiquitous B-Tree", ACM Computing Surveys, 1979 (www.cl.cam.ac.uk/~smh22/docs/ubiquitous_btree.pdf) 531 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 18:25:09 ] 便乗だけど、B木と赤黒木どっちがいいか、 って判断はどこら辺ですればいいですか？ 使い分ける時の基準みたいなのが知りたい。 532 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 19:19:15 ] >>531 どんな用途に使おうとしてるか分からないので、普通の設定で一般的な話をする。 赤黒木は、本質的にはブロックサイズの小さな B 木なので、 あなたの質問は B 木のブロックサイズをどう選ぶか、という質問と同じ。 普通の実装では、n 個の要素を格納するブロックサイズが b の B 木から 要素を検索には O(log (n/b)) 回の木上の探索（ランダムアクセス）と O(b) 回のブロック内の探索（シーケンシャルアクセス）が必要となる。 ここで雑な計算をするとブロックサイズは、木上の探索の速度と ブロック内の探索の速度の比くらいに選ぶのがよいことが分かる。 木が丸ごと全部メモリに乗るような場合は、木のアクセスもブロックの アクセスも同じくらいなので、ブロックサイズも小さく選ぶのが良い。 一方、ハードディスクやネットワーク上のデータベースのような 木のアクセスが遅く、ブロックのアクセスが早い場合は、 ブロックサイズも大きく選ぶのが良い。 533 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 19:50:28 ] >>528 参考にすんな→この人怒ってる怖いよぉ 534 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 19:54:51 ] どこぞの園児じゃあるまいし。 535 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 21:04:07 ] なんでそんな偉そうなんですか 536 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 21:04:43 ] どこが偉そうなの 537 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 21:37:32 ] 質問を質問で返すな わかりませんと言え 538 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 21:40:56 ] なんでそんな偉そうなの 539 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 21:41:29 ] そういうのは質問の体をなしてから言え 540 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 22:26:02 ] 順序付きコンテナは、どうもトライが最強っぽいんだけど、 メモリが・・ なんとかなりませんか？ 541 名前：デフォルトの名無しさん mailto:sage [2007/08/19(日) 22:59:51 ] つ パトリシア 542 名前：デフォルトの名無しさん mailto:sage [2007/08/28(火) 05:58:02 ] 2Dの多角形ポリゴン2個(n個)を合成して1個(?)の多角形にするアルゴリズム ネット上にこれを実装したソースコードが公開されてない(見つからない・・・)のでどなたか教えてください。 ＿＿ ＿|＿ | | |＿|＿| |＿＿| ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0) ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1) 　↓ ＿＿ ＿| | | ＿| |＿＿| ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0) というような感じです。 中抜き( 合成後のポリゴンの内側に穴が開いている )まで考えると、結構むずかしそうで・・・ これでやりたいことは、国土地理院の市町村別のポリゴンデータを県ごとに合成して、県別のポリゴンデータにすることです。 Excel VBAで精細な都道府県地図を描きたいなーと思って、 都道府県の無料のポリゴンデータを探したけど市町村別しか見つからなかったので じゃあ合成して作ろうか、と思ってたんですが・・・詰まりました。 Java の awt パッケージでポリゴンの合成をしているクラスのオリジナルのソースコードを見ればアルゴリズムがわかるかも とも思ってみてみたけどソースコードは入っておらず・・・orz 宿題とか課題とかではなくて、あくまで趣味的なものなので急ぎません。 VBでもcでもc++でも良いので、どなたか、お知恵を拝借させてください。 543 名前：542 mailto:sage [2007/08/28(火) 06:00:14 ] >>542 図形ずれちゃった・・・ 　　＿＿ ＿|＿　 | |　|＿|＿| |＿＿| ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0) ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1) 　↓ 　 ＿＿ ＿|　　| |　　＿| |＿| ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0) こうです。 544 名前：デフォルトの名無しさん mailto:sage [2007/08/28(火) 09:44:30 ] >542 悪いこと言わないから別の方法考えたほうがいいと思う。 塗り分けるだけなら市町村別のデータでも構わないわけだし。 で、 コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277X の第 2 章にアルゴリズムは載ってる。でも、ここから実装まで持っていくのもそう単純じゃないと思う。 あと、オープンソースライブラリの CGAL にそういう機能はある。 www.cgal.org/ Reference Manual の VI Polygon and Polyhedron Operations 辺り。 545 名前：542 mailto:sage [2007/08/28(火) 21:33:57 ] >>544 コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277Xの第2章 早速読んできました。 例題に挙げられてるのも地図でよさそうだったけど、 プログラミング言語を限定してないアルゴリズムとしての本なんで、 やろうとしていることを実装するには、どういうプログラムを書けばよいのかまでは踏み込めなそうです。 せめて i ← S1 と S2 の交点 みたいなのがあればなぁ。 CGALのマニュアルも読んでみました。joinあたりのコードか数式が出ていればVBAでも実装できそうなんですが・・・ >悪いこと言わないから別の方法考えたほうがいいと思う。 そうですねー。 ただ、ポリゴンをくっつけるのはもうちょっと粘ってみます。考えるのも楽しいので。 市町村同士は重ならないので、 ・辺と辺が重なっている（隣り合っている）ところを見つけてくっつけていく ・中抜きはこの際無視 というように簡単なものを作る方針で考えてみます。 重なりまで考えて汎用的なアルゴリズムにしようと思ったけど、結構しんどそうですので・・・ どうもありがとうございましたー。 546 名前：デフォルトの名無しさん [2007/08/29(水) 01:21:12 ] 今日から専門学校のほうで授業アルゴリズムが始まったんですが 時間計算 分時間を入力して○時○分に変換して出力するフローのaとbに該当する処理を記述しなさい。 なお、計算結果は整数部のみとし、小数部は切捨てとなる。 余り（X%Y)で除数の余りを求めることができる。[例、余り（100%3）は1となる] 例：117分の時　1時間57分 （開　始）　何方かa bに入る答えがわかる方いましたら教えてください 　　↓ （データ）・・分時間を入力 　　↓ （処理）・・a 時を求める 　　↓ （データ）・・時を出力 　　↓ （処理）・・b 残りの分を求める 　　↓ （データ）・・分を出力 　　↓ （終了） 547 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 01:28:01 ] aとbに入るのは数字？式？言葉？ 548 名前：デフォルトの名無しさん [2007/08/29(水) 01:39:28 ] 式です＾＾； 549 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 01:54:03 ] a・・・分時間/60 b・・・分時間%60 550 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 03:31:39 ] >>546 宿題はスレ違い しかも回答もらって礼も無しかよ 551 名前：デフォルトの名無しさん [2007/08/29(水) 19:38:32 ] 三角関数はマクローリン展開して計算しますよね。 単純に考えればsinθのθが何であれ計算時間は変わりませんが、 速度面でチューニングが施されているであろうライブラリではどうなんでしょう？ 552 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 23:22:57 ] >三角関数はマクローリン展開して計算しますよね。 ここで間違ってる 関数近似の教科書読むべし 553 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 23:30:11 ] >>552 すみません、悠長に教科書読んでる暇がないので結論をお願いします 554 名前：デフォルトの名無しさん mailto:sage [2007/08/29(水) 23:36:55 ] CPUのアーキテクチャ等やライブラリ作った奴の腕に依存して色々な可能性がある ただ，どれもθを0〜π/2の範囲に正規化してるだろうから その範囲なら少し速いはず これ以上は本嫁 555 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 01:07:36 ] ぶっちゃけ、今時の単精度演算アクセラレータはテーブル参照プラスリニア補間で済ませている希ガス。 556 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 07:24:15 ] >>554 絶対的な速度が問題なのではなく、速度のむらを気にしているのです。 たとえばsin(0.1)を計算するのに1μsかかったとして、sin(0.2)では5μsかかったりするのか？ということです >>555 ターゲットはマイコンなのでそういう容量食いな方法は取らないような気がします。 ターゲットはSH7145 ルネサスのコンパイラを使ってます。 ただ、ピンポイントでこのコンパイラに通じている方がいるとは考えにくいので VCやgccだったらどうなのかという意見でもいいのでお願いします。 557 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 09:28:07 ] 後出し多いな 558 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 10:04:11 ] 5倍の差はないだろうけど，1〜2割位なら充分あり得る 実測するのが手っ取り早いかと 559 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 17:45:37 ] >>556 マイコンの方がむしろテーブル変換使用すると思うが 560 名前：デフォルトの名無しさん mailto:sage [2007/08/30(木) 17:47:40 ] >>554 いっそπ/8に正規化するとか 561 名前：デフォルトの名無しさん mailto:sage [2007/09/09(日) 14:05:26 ] >>553 ＞悠長に教科書読んでる暇がないので そうか。残念だったな。 562 名前：デフォルトの名無しさん [2007/09/12(水) 02:03:16 ] 差異のアルゴリズムでレーベンシュタイン距離を求めていますが、 結局これ求めてどうなるんですか？ 馬鹿でも分かるようにく教えてください。 563 名前：デフォルトの名無しさん mailto:sage [2007/09/12(水) 08:42:09 ] >>562 そんな限られた分野でしか使わないようなものを さも誰もが知ってるかのように聞かなくても。 自然言語処理とかで使う。 Google 先生とかがよくやってる もしかして: ○○ を出したりとかに使える。 564 名前：デフォルトの名無しさん mailto:sage [2007/09/13(木) 00:02:29 ] >563 レスどうも。 2つの文字列を比較して"n文字違います"とかは想像できるんだけど、 diffみたいに異なるものを表示するとかの処理にはどうやって組めばいいんだろうと思って、、、 565 名前：デフォルトの名無しさん mailto:sage [2007/09/13(木) 00:05:36 ] >>564 ja.wikipedia.org/wiki/Diff 566 名前：デフォルトの名無しさん mailto:sage [2007/09/15(土) 23:51:51 ] 今、ロバスト解について勉強しています。 ロバスト解発見手法にはシックスシグマ法のDesign For Six Sigma[Brue 03]やDesign For Multi-Objective Six Sigma[Shimoyama 06]、またはガウスノイズがあるということが分かりました。 しかし、上に述べた手法の利点・欠点がほとんど分かりません。 どなたか他の手法と比べた場合の利点・欠点を教えてはいただけないでしょうか? 下に今分かっていることを書きます。 ---------------------------------------------------------------------- Design For Six Sigma[Brue 03] ロバスト解を1つ発見する場合に有効。 Design For Multi-Objective Six Sigma[Shimoyama 06] Design For Six Sigma[Brue 03]を拡張したもの。複数のロバスト解を同時に発見する場合に有効。 ガウスノイズ アルゴリズムは簡単。 ガウスノイズは上に述べたシックスシグマ法を使ったときよりもすばやく収束できる。 吸収現象などのせいでロバスト解からずれた位置に収束するかもしれない。 567 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 03:20:29 ] 質問させてください． y=Ax （x,y:ベクトル， A:マトリックス，大きさ数百〜数万） に対し， x = inv(A) * y を解く問題を考えています． ここで，逆行列演算inv(A)がO(N^3)のコストが掛かり，ネックになっています． いま，Aは疎な帯行列（しかも対称）という条件があるので， 大幅な計算削減ができるのではないか？と考えております． 例えば，計算コストをO(N^2)にするといったことは可能でしょうか？ キーワードだけでも良いので，知恵を貸していただけると幸いです． 568 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 03:49:22 ] つ[特異値分解] 569 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 07:22:57 ] >>567 LU使っているのか？ 対称行列だと、LDL分解でOK 帯行列だとさらに、0要素を見ないことで、さらにスピードアップ 570 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 17:36:11 ] そんな話，数値計算の本見ればいくらでも載ってるだろ 571 名前：567 mailto:sage [2007/09/20(木) 01:53:07 ] >>568 キーワードありがとうございます！ 調べてみます． >>569 LU分解→直接法で逆行列としていました． LDL分解というものがあるのですね． 解法は反復法に持って行くのですかね・・・調べてみようと思います． 反復法は精度の面が少し気になりますが，勉強含めて試してみます． 多謝！ >>570 数値計算の門外漢なもので・・・勉強してきます． 572 名前：デフォルトの名無しさん mailto:sage [2007/09/24(月) 22:11:26 ] kd木で、近い領域を何度も連続して調べたい時、毎回根から辿らないようにショートカットするような技法ってありますか？ 573 名前：デフォルトの名無しさん mailto:sage [2007/09/28(金) 09:44:52 ] 二つの整列済みリストのマージで 要素数が一方がk個,もう一方が2個の場合, n回の比較でマージできる最大のkをanとすると a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号 で与えられるらしいのですが これがどういうアルゴリズムでマージしたときの物なのか, またこれが最良値なのか知りたいのですが, 誰か知りません? 574 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 14:28:02 ] >>573 a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号 この式を見るとnが1増えると√2倍でa[n]は指数的な増加。 ソート済みk個と2個のマージは 2分探索を2回使えば2logk回。 詳しくは見てないが、2logkの係数の2が√2になりそうだし、 kが指数的に増加して比較回数が線形増加もa[n]の式とオーダーは合っている。 575 名前：573 [2007/09/30(日) 13:03:48 ] >>574 考えてくれてありがとう. 2分探索だけだと最良値にはならないみたい. 573の式だと最初の10個位までは最良値になってるのは 確認できた(虱潰しで) さらに知らべて,もう一方のリストが3個の場合みっけた. Optimal Merging of 3 Elements with n Elements っていう論文のAbstructで f3(1)=0, f3(2)=1, f3(3)=1, f3(4)=2, f3(5)=3, f3(6)=4, f3(7)=6, f3(8)=8 r >= 3 f3(3r) = [(43/7)*2**(r-2)]-2 f3(3r+1) = [(107/7)*2**(r-3)]-2 f3(3r+2) = [17*(2**(r-3)-6)/7]-1 との事. 576 名前：デフォルトの名無しさん mailto:sage [2007/10/30(火) 01:16:41 ] 各データの値がかなり近い時に ハッシュのみだとデータの衝突回数 多い場合ってどうやってみんななら解決する？ あとね、kd木で何の本に詳しく載ってますか？ 577 名前：デフォルトの名無しさん mailto:sage [2007/10/30(火) 01:55:31 ] 値近くてハッシュが衝突するって、どんなアルゴリズムだよ

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef