5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

アルゴリズム総合スレ in ム板

1 :デフォルトの名無しさん:2008/08/03(日) 23:23:35
言語の雑談・質問スレはあるのに
アルゴリズムのスレが無かったので立ててみました。

自作アプリ作成に於けるアルゴリズム指南、
基本情報レベルの幼稚園児用鈍足アルゴリズムから
高度な数式が必要な大学院生用神速アルゴリズムまで

語りませう。

2 :デフォルトの名無しさん:2008/08/03(日) 23:24:53
MSがIMEに手を加えたせいで

プログラマ板(マ板)⇒プログラマー板(マー板)
プログラム板(ム板)⇒プログラムー板(ムー板)
になるんじゃね

3 :デフォルトの名無しさん:2008/08/03(日) 23:25:25
>>2
は?2ちゃんは昔から『プログラマー板』なんだが?

4 :デフォルトの名無しさん:2008/08/03(日) 23:28:12
アルゴリズムと関係ないかもしれないけど質問です。

ツーちゃんねる用テキストエディタを作りたいのですが
レス番号はどうやって把握させればいいのでしょう。

3番の人の書き込みで、『4 名前:デフォルトの名無しさん 投稿日:2008/08/03(日) 23:25:26』という文字列の書き込みをされると
判断が出来なくなるような・・・

5 :デフォルトの名無しさん:2008/08/03(日) 23:29:20
いっぽすすんでまえならえ
いっぽすすんでえらいひと
ひっくりかえってぺこりんこ
よこにあるいてきょろきょろ

6 :デフォルトの名無しさん:2008/08/03(日) 23:31:38
Pen4-3GHz,DDR・SDRAM1200MBのノートパソコンでも
現実的な時間で駒を打ってくれる最強のオセロCPU(AI?)は作れますか?

ここでいう最強とは、全部の組み合わせを探索できる最適なCPUです。

7 :デフォルトの名無しさん:2008/08/03(日) 23:32:21
オセロの話題はリバーシ専用スレでやれよ

おまいら最強のリバーシプログラムしてみろよ part3
http://pc11.2ch.net/test/read.cgi/tech/1173784074/
C言語で素晴らしいオセロを作らないか?
http://pc11.2ch.net/test/read.cgi/tech/1087979678/
【思考】オセロのAIを作りたいのだが【難問】
http://pc11.2ch.net/test/read.cgi/tech/1180430969/

8 :デフォルトの名無しさん:2008/08/03(日) 23:33:38
推薦図書/必読書のためのスレッド 41
http://pc11.2ch.net/test/read.cgi/tech/1215510861/


9 :デフォルトの名無しさん:2008/08/03(日) 23:35:11
>>6
序盤は無理
終盤は可能

10 :デフォルトの名無しさん:2008/08/03(日) 23:35:54
>>1
沢山あるんだが・・・

アルゴリズムオタク
http://pc11.2ch.net/test/read.cgi/tech/1141740363/
計算アルゴリズム【U】
http://pc11.2ch.net/test/read.cgi/tech/1129376543/
<集大成>アルゴリズム大辞典
http://pc11.2ch.net/test/read.cgi/tech/1086272325/
3Dアルゴリズム全般
http://pc11.2ch.net/test/read.cgi/tech/1164171086/

11 :デフォルトの名無しさん:2008/08/03(日) 23:37:27
>>1
あるよ
少しは探せよゴミ
http://pc11.2ch.net/test/read.cgi/tech/1129376543/
http://pc11.2ch.net/test/read.cgi/tech/1086272325/
http://pc11.2ch.net/test/read.cgi/tech/1141740363/


12 :デフォルトの名無しさん:2008/08/03(日) 23:38:27
大学生なら
The Art of Computer Programming
Introduction to Algorithm
は必須。

〜のアルゴリズム事典みたいな本は
稚園児向け。

13 ::2008/08/03(日) 23:39:29
すみません。このスレは終了です。
どうもありがとうございました。

14 ::2008/08/03(日) 23:39:58
O(n)のソートアルゴリズムを発見した
http://pc11.2ch.net/test/read.cgi/tech/1212217022/

15 :デフォルトの名無しさん:2008/08/03(日) 23:40:17
〜再開〜

16 :デフォルトの名無しさん:2008/08/03(日) 23:41:49
ソートのような単純な処理は標準ライブラリに限る。

ぶっちゃけ仕事で使うプログラミングなんて
アルゴリズム知らなくてもいい。
それよりコミュニケーション能力のほうが大事

研究者は例外だからさっさと氏ね。

17 :デフォルトの名無しさん:2008/08/03(日) 23:43:55
GOOGLE検索の核となるアルゴリズムを教えてください。

18 :デフォルトの名無しさん:2008/08/03(日) 23:44:28
>>1しょぼいな
俺なんかジンバブエ問題を多項式時間で解くアルゴリズムを発見したぞ。

でもそれを記述するにはこの余白はあまりにも少なすぎ

19 :デフォルトの名無しさん:2008/08/03(日) 23:46:01
最も真の乱数に近くなるな種の求め方。

20 :デフォルトの名無しさん:2008/08/03(日) 23:58:07
言語を習得する順序の話題は異常に盛り上がるけど、正直、ぜんぜん実のないスレになりがち。
本当はアルゴリズムのほうが大事なのに・・・

21 :デフォルトの名無しさん:2008/08/04(月) 00:14:53
メニィコア上で高速なソートとか

22 :デフォルトの名無しさん:2008/08/04(月) 00:19:50
言語で苦戦しているやつはスタートラインにも立てていないわけで
アルゴリズムで苦戦して初めて入門者


23 :デフォルトの名無しさん:2008/08/04(月) 00:25:54
>>22
そんなのはどうでもいいんだ。
アルゴリズムの話をするんだ。いいな?

24 :デフォルトの名無しさん:2008/08/04(月) 02:45:58
>>16
マ板にいけよITドカタw

25 :デフォルトの名無しさん:2008/08/04(月) 05:01:11
悪いんだけど、まとめサイトを作る話は無期限延期にさせてくれ。
入った会社が求人票と全然違う会社でとてもとても。
年休65とかwww

26 :デフォルトの名無しさん:2008/08/04(月) 08:59:16
>>12
> 〜のアルゴリズム事典みたいな本は

Springerから出てるぞおい。Encyclopedia of Algorithms
お高いぜ……。

27 :デフォルトの名無しさん:2008/08/04(月) 15:45:04
共立のアルゴリズム辞典だってぜんぜん幼稚園児向けじゃないけどな

28 :デフォルトの名無しさん:2008/08/13(水) 13:08:48
幼稚園児の段階でそれぐらい理解する頭を持ってるやつ以外死ねって事ですね、わかります

29 :デフォルトの名無しさん:2008/09/08(月) 01:34:44
ドミノとか畳とか、1×2の格子で敷き詰められる格子を
任意の敷き詰め方で敷き詰めるアルゴリズムがわっからん
いいかげんにやらせると隅とかで詰んでしまう

30 :デフォルトの名無しさん:2008/09/08(月) 01:45:26
>>29
何となく言ってる事はわかるけど例題出してみてくれる?


31 :デフォルトの名無しさん:2008/09/08(月) 01:54:36
>>29
ソースとかじゃなくて悪いけど
効率を求めないのであれば、

X*Yの範囲におけない場所を任意に作る
おける場所の個数をNとして2の倍数でなければエラー
N/2個のブロックを用意、位置と縦か横かのパラメータを持つ
ブロックを左上から積めていき詰まったらブロックを戻して再検索

32 :デフォルトの名無しさん:2008/09/08(月) 02:16:40
>>31
トライアンドエラーでいけるのかな…
>>30
こんな感じ
┌┬┬┬┬┬┬┬┐ ┏┓
├┼┼┼┼┼┼┼┤ ┃┃
├┼┼┼┼┼┼┼┤ ┗┛
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┤
└┴┴┴┴┴┴┴┘

33 :デフォルトの名無しさん:2008/09/08(月) 03:13:01
>>32
はずしてたらすまんけどゲームとかでランダムに敷き詰めた
ものが欲しいのなら、こういう形で必ず敷き詰められるから
┌┬┬┬┬┬┬┬┐
│││││││││
├┼┼┼┼┼┼┼┤
│││││││││
├┼┼┼┼┼┼┼┤
│││││││││
├┴┼┴┼┴┼┴┤
└─┴─┴─┴─┘
これから
┌┬┐┌─┐
│││├─┤
└┴┘└─┘
をランダムに90度回転するというのはどうだろう。


34 :デフォルトの名無しさん:2008/09/08(月) 03:21:54
敷き詰められたという条件だけでなく
(特に乱数が擬似で無いならば)
乱数の機嫌がよければどの敷き詰め方も得られる可能性があるアルゴリズムが欲しい

35 :デフォルトの名無しさん:2008/09/08(月) 11:15:44
本題とは関係ないけど疑似乱数というものをわかってない気がする。
(理想的には)ブラックボックステストでは疑似かどうか判定できない
ものが疑似乱数列。

本題

あらゆる敷き詰め方を網羅できるアルゴリズムを考えてみる。
左上から順番に空きを探して、空きがあったらまず横向きに置いて、
その先を置いていく。その先のパターンを全て網羅したら、縦向きに
置く。つまったらバックトラック、というアルゴリズムで、あらゆる
敷き詰め方が網羅できる。

まず横向きに置く→次に縦向きに置く、この順序を乱数で決定
するようにすればランダムになる。

36 :デフォルトの名無しさん:2008/09/08(月) 12:24:54
敷き詰める空間が矩形と言う前提があるなら、バックトラックのいい練習台になりそうだ。
C++かなにかで再帰使って実装すれば一日もあればできそうだね。

>>29
勿論、隅で詰まったら手を戻して詰め直してみるだけ。

37 :デフォルトの名無しさん:2008/09/20(土) 03:26:23
ファイル管理ソフトでファイル内文字列まで見て該当ファイルを見つける
という検索がありますが、

あれは文字列の形式やフォーマットあるいはエンコードなどをすべての
ケースで調べているのでしょうか?

たとえばExcelやワードなどのファイルの場合は、それをテキスト形式
で取り込んで調べるのでしょうか?
よろしくお願いします。


38 :デフォルトの名無しさん:2008/09/20(土) 06:02:43
そりゃファイル管理ソフトによるだろ・・

39 :デフォルトの名無しさん:2008/09/20(土) 11:23:21
すまん、図形描画アプリみたいなものを作ってるんだが・・・
次のようなもので悩んでます。
1.複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか?
場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。
総当たり以外でエレガントな方法というとどんなんざんしょ?
2.同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。

教えてエロイ人・・・

40 :デフォルトの名無しさん:2008/09/20(土) 11:25:03
ごめんなさい。別スレの方が人いそうなのでそっちにかくです・・・
すれよごしすまんそ。

41 :デフォルトの名無しさん:2008/10/14(火) 22:58:25
全くの初心者が参考書を買うに当たってお勧めできるものなど教えていただけますでしょうか。
アルゴリズムは分かっても、それをうまくフローチャート化できなかったりします。
あとソートに関しても前述の理由でうまく説明が出来ない場合があります。

初歩以前の質問かもしれませんが、どなたかご教示願います。

42 :デフォルトの名無しさん:2008/10/15(水) 05:17:46
そういうのってなんとなくできるようになるもんだと思われてる感じで、
ちゃんと説明してくれるのは少ないよね。
英語で良ければHtDPがいいよ。

43 :デフォルトの名無しさん:2008/10/15(水) 20:42:21
>>42
ありがとうございます。
書籍だと1万円するようなのですが、とりあえずwebサイトも見つけたので書籍購入までで時間が取れる時はそちらを参照してみます。

どなたでも、日本語の書籍でも何か参考になるものがありましたら、お願い致します。

44 :デフォルトの名無しさん:2008/10/22(水) 00:40:29
可変長のバイナリデータをファイル名に変換する単射の写像を作らなくてはいけません。
ただしファイル名が長すぎて使えないことは考慮しないとします。

UnixならBase64、WindowsならBase32を使っておけばとりあえずOKですが。。。
UnixはスラッシュとNUL以外は何でも使えるようなので、Base64は非常にもったいない気がします。

なにかいいアイディアはありますか?

45 :デフォルトの名無しさん:2008/10/22(水) 06:44:17
>>44
> UnixはスラッシュとNUL以外は何でも使えるようなので、Base64は非常にもったいない気がします。

だからといってマルチバイト文字列でもなしに
printableでないバイトを使うのは非常に愚かだと思うがどうかね。

46 :デフォルトの名無しさん:2008/10/22(水) 11:18:13
使えない文字だけURLエンコードみたいに %xx にする

47 :デフォルトの名無しさん:2008/10/24(金) 21:57:47
二つの折れ線グラフが似ているものかどうかを確かめるアルゴリズムってありますか?
詳しい書籍、HPなどがあれば教えてくださると助かります。

48 :デフォルトの名無しさん:2008/10/24(金) 22:02:44
>>44
使っていい文字n個を全部使ってBase<n>エンコードすればいいやん。

49 :デフォルトの名無しさん:2008/11/18(火) 12:10:38
あっちむいてふたりで前ならえ
こっちむいてふたりで前ならえ
あっちむいてふたりで前ならえ
こっちむいてふたりで前ならえ
手を横に あら危ない
頭をさげればぶつかりません
手を横に あら危ない
頭をさげれば大丈夫

50 :デフォルトの名無しさん:2008/11/18(火) 12:48:41
>>29 アホだね「詰んだ」らそれを回避すればいいだけだろう

51 :デフォルトの名無しさん:2008/11/18(火) 12:51:14
とアホが申しております。

52 :デフォルトの名無しさん:2008/11/18(火) 14:08:12
今ちょっと有根系統樹という有向グラフについて調べてるんですが、
2つの同数の葉を持つ木構造のデータの類似性を比較するアルゴリズムってなにかないでしょうか?
データの文字列に対して編集距離を使って計算を行ったのですがそれではあまり差異が出ないので他の方法を探してます

53 :デフォルトの名無しさん:2008/11/22(土) 16:46:56
今日久しぶりにゲーセンでグラディウスUをやってきた。やっぱ改めてすごいね、当時
のコナミは。何がって、1面の竜!1本の竜に見えるけど、よーく見ると複数のパーツが
組み合わさってできている。多関節キャラの範疇に入るのかな?
他のギミックを見ると、どうやら回転機能は使ってないようだ。(カニの脚の上(膝より上って
意味ね)は一見すると回転機能を使っているように見えるが、よく見ると使ってない)
ということは、少しずつ回転させた絵をいっぱい用意してあるんだろうな。普通に蛇型?
竜型?のキャラを作ったらR-TYPEの蛇みたいに各パーツが別れて見える。それをきれ
いにつながっているようにデザインしているのがすごい!

54 :デフォルトの名無しさん:2008/12/10(水) 21:45:28
多角形を四角形に分割するアルゴリズムってありますか?
参考になる情報をお持ちでしたらご教授のほどよろしくお願いいたします。
凹凸組み合わせた図形を考えると難しそうです。

入力:多角形の頂点座標リスト
出力:四角形(rectangle)のリスト


55 :デフォルトの名無しさん:2008/12/10(水) 21:50:01
三角形でなく四角形なのはなぜ、とかふと疑問に思ったり。

56 :デフォルトの名無しさん:2008/12/10(水) 21:59:56
無責任思考垂れ流し

1.三角形に分割する

2.三角形をノード(節点・頂点)、辺をエッジ(枝・辺)とするグラフ理論に置き換える
2B.ただし辺を共有していても合体して三角形になる場合は
合体三角形でまた別のグラフを作る
(そもそも2Bの条件に引っかかる場合はそもそも合体三角形をなぜ分割したのだろう?
ということはこの処理は要らない?)

3.グラフを共通のエッジを持つ2つのノードの組に分解する
どうやるんだろう…市松模様のように塗れるのだろうか?

57 :デフォルトの名無しさん:2008/12/10(水) 22:26:00
斜めの辺が存在しないので、□の方が扱いやすいという特殊事情です。
(ディグダグ2みたいな感じ)
三角形の分割から入るということですか

58 :デフォルトの名無しさん:2008/12/10(水) 22:32:10
>>57
要は、水平線と垂直線だけ? 単に長方形に分割すればいいって話?
# だったら最初からそう書けよ。

59 :デフォルトの名無しさん:2008/12/10(水) 22:34:05

四角形じゃなくてrectangleか
道理で

60 :デフォルトの名無しさん:2008/12/10(水) 22:34:42
そうです。
言葉足らずですみません。

61 :デフォルトの名無しさん:2008/12/10(水) 22:44:41
そもそも元は癖のないポリゴンか、それとも最初から
水平垂直矩形の組み合わせ(ドット絵の影絵?)なのか
そこまで気になってきた

62 :デフォルトの名無しさん:2008/12/10(水) 22:48:50
ドット絵の過去ゲーを今時の3Dライブラリ(DirectXか?)で再現しようとしていると見た。

63 :デフォルトの名無しさん:2008/12/10(水) 22:54:47
必ず90度の角ができていて、立ち止まったり、引き返したりはないです


64 :デフォルトの名無しさん:2008/12/10(水) 23:13:58
そんなところです。

65 :デフォルトの名無しさん:2008/12/11(木) 07:28:49
映画トロンみたいな感じか

66 :デフォルトの名無しさん:2009/01/19(月) 03:39:52
計算アルゴリズムIIスレはこのスレに併合されました

67 :デフォルトの名無しさん:2009/01/19(月) 03:40:23
age

68 :デフォルトの名無しさん:2009/01/19(月) 09:17:06
ユビキタス情報環境って便利そうな言葉があるんだが
総務省のu-Japan政策が余りにも現実離れしてる件

69 :デフォルトの名無しさん:2009/01/20(火) 03:09:35
アルゴリズム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万計算できたとき、何年で計算が終わるかだれかちゃんと計算してくれ

70 :デフォルトの名無しさん:2009/01/20(火) 03:25:14
N=2, N=200, N=2^32とか具体的な数値が問題じゃないんでないの?

71 :デフォルトの名無しさん:2009/01/20(火) 03:26:31
計算量がO(2^n)だったとき、計算機の能力が10倍になってもnはたかだか3増やせる程度というのがわかってないんだろうな。
だから指数時間かかるアルゴリズムは実装がどうこうよりもアルゴリズムとしてO(1.7^n)とかO(1.4^n)に緩和することが大事だということがわからないんだろう。

72 :デフォルトの名無しさん:2009/01/20(火) 03:27:43
>>70
そうなんだが、アルゴ君はその具体的な数値を出してたから、アルゴ君なんだ。

73 :デフォルトの名無しさん:2009/01/20(火) 03:28:37
アルゴ君スレはここな
http://pc11.2ch.net/test/read.cgi/tech/1129376543/

74 :デフォルトの名無しさん:2009/01/20(火) 03:32:07
アルゴ君の名前の由来は、このあたりでまとめられてる。
http://pc11.2ch.net/test/read.cgi/tech/1220531647/240

75 :デフォルトの名無しさん:2009/01/20(火) 03:32:21
何だアルゴ君て?
美味い棒か?

76 :デフォルトの名無しさん:2009/01/20(火) 03:35:08
>>69
なーんにも経験したことないおまえの方が無能ってことだな。

77 :デフォルトの名無しさん:2009/01/20(火) 03:37:00
>>75
簡単に説明すると、次世代Javaスレでアルゴリズムをアルゴという人があらわれ、アルゴリズムIIスレでアルゴという言葉を使う人が現れたと思ったら次世代Javaスレのときと同じように逆切れしてたのが、アルゴ君なんだ

78 :デフォルトの名無しさん:2009/01/20(火) 03:45:41
みんな気付いてるかな?
このスレには既にアルゴ君が居る事に


79 :デフォルトの名無しさん:2009/01/20(火) 03:58:00
>>77
なんだかよく分からないが粘着してるのはおまえの方でないのか
キモイからそろそろ消えてくれないか?

80 :デフォルトの名無しさん:2009/01/20(火) 04:02:18
>>78
気づかないフリしてあげて!

81 :デフォルトの名無しさん:2009/01/20(火) 22:32:05
>>78
ワロタw

82 :デフォルトの名無しさん:2009/01/24(土) 22:18:12
平均情報量(エントロピー)って正の無限大に発散する?

83 :デフォルトの名無しさん:2009/01/24(土) 22:47:57
>>82
連続量のエントロピー

84 :デフォルトの名無しさん:2009/01/31(土) 15:44:27

高校の体育で
アルゴリズム体操やらされてる
私が通りますよ


85 :デフォルトの名無しさん:2009/02/18(水) 00:56:26
或るプログラムで今.NETのDictionaryクラスを使っているんですけど、
プログラム起動時にキーと値を読み込んだり終了時に書き出したりしないといけない上、
データが増えてきてメモリに収まらない程になってきたので、
ハードディスク上にデータを置いたままキーの検索などが行えるように改造しようとしています。

ググったらB+treeやB*treeや赤黒木なんかが見つかりましたが
お勧めのアルゴリズムとその理由を教えてください。

ちなみにキーは8バイトのハッシュ値で、値は16バイトの構造体です。


86 :デフォルトの名無しさん:2009/02/18(水) 01:24:55
1.データーベースソフトや同ライブラリを探してきて丸投げ

2.ハッシュ値の上位8ビット〜16ビットごと+キャッシュ、つまり257〜65万くらいに
データを分割する。十分な性能を持つハッシュならキーは十分平均的に分散するはず

なんて方法がさくっと浮かんだが、間違ってるかもしれない

87 :デフォルトの名無しさん:2009/02/18(水) 15:17:49
俺なら確実に1.

88 :デフォルトの名無しさん:2009/02/18(水) 22:01:59
ハッシュテーブルはどうだろう。
HDD上でのシーク回数が木構造よりも減るんじゃないかと。


89 :デフォルトの名無しさん:2009/02/19(木) 11:23:58
つうか、Dictionaryクラスを継承して、値をHDDに置くようにすればいいんじゃね?

90 :デフォルトの名無しさん:2009/02/19(木) 11:37:48
1以外にする強い理由が無いなら1だな。

91 :デフォルトの名無しさん:2009/02/20(金) 12:21:27
前から気になっていたのですが、逆行列を求めるアルゴリズム(消去法など)と行列式を
求めるアルゴリズム(数学どおりの余因子による方法)ではどちらが実用的なんでしょうか。
行列式の方法が効率的だと、逆行列は余因子展開で求められてしまうんですが・・・

92 :デフォルトの名無しさん:2009/02/20(金) 14:37:15
n次正則行列に対してガウスの消去法はO(n^3)、余因子展開はO(n^5)のような気がする

93 :デフォルトの名無しさん:2009/02/20(金) 15:16:53
n^2.8位の計算量のアルゴリズムなかったっけ

94 :デフォルトの名無しさん:2009/02/20(金) 22:13:12
>>91
余因子展開のときの行列式はどうやって計算するの?

>>93
逆行列の計算と行列積の計算は同じオーダーでできるので
現在最速の行列積がO(2^376)なので,これが現在最速.
ただし定数部分がでかすぎて実用的には使い物にならない.

95 :デフォルトの名無しさん:2009/02/20(金) 23:16:21
>>94
余因子を使ったdet値の導出は、公式自体は線型代数の教科書に普通に載ってるんですが。
たぶん、主要部分はいれご(再帰)になるだけでプログラムはかなり簡単になるんじゃないかな。
ピボットとかの職人技法的なことを考えることなく、機械的なプログラムのほうがいいかなっと思ってまして。

n^5は一見遅いけど頑張ってもn^3, n^2なので激遅いってことじゃないみたいですね。
それに通常の使い方では、逆行列は一度計算して変数に入れておくことが多く、det値を再計算しないで再利用して使いまわすので、
やはりプログラムが簡単なアルゴ(笑)のほうが言いかなって思うんですけど。

96 :デフォルトの名無しさん:2009/02/21(土) 01:54:53
64bit用のlock-free link-listで
一番良い実装ってどれですか?


97 :デフォルトの名無しさん:2009/02/21(土) 01:58:55
>>96
64bit が atomic にロード/ストア出来る CPU か否かによって変わってこないか?


98 :デフォルトの名無しさん:2009/02/21(土) 02:04:20
なので64ビットだからと言って特別なことは何もないと思う。

99 :デフォルトの名無しさん:2009/02/21(土) 11:49:30
>>95
何を聞かれているか理解できてないみたいね.

(1) 逆行列を余因子行列を用いて表す方法がある.これには O(n^2) の行列式の計算が必要.
(2) 行列式の計算に余因子展開を用いるものがある.これには O(n!) の四則演算が必要.
(3) 行列式の計算は巧くやれば O(n^3) 以下でできる.逆行列を余因子行列で計算する方法が O(n^5) というのはこれを用いた場合.

ちなみに O(n^5) は十分遅いレベルで,実用的には使い物にならない.
逆行列の使いまわしも,数値線型計算では逆行列の形では陽に持たないのが常識で,LU分解の形で持つ.

100 :デフォルトの名無しさん:2009/02/21(土) 13:54:37
話がそれて聞きたいこととずれてしまったのですが、行列式detの値を出すアルゴリズムはあるんでしょうか?が本題です。
もしあるなら、余因子展開で逆行列も高速に出ますよねってことです。

今やってるのは、行列式の値は逆行列(消去法などで)出すときに付随して出てきます。
detだけを出すのは、数学定義通り余因子による方法しか知らないので他にないんでしょうか。
といっても実際は線型打数のパッケージ使うので、アルゴリズムの練習程度なのでこだわってるわけじゃないんですが。

101 :デフォルトの名無しさん:2009/02/21(土) 14:08:52
奥村先生の辞典でやってるんですけど、行列式をピンポイントで出すアルゴ(笑)は載ってませんでした。
次は従来の算法など数値計算用(ソルバー)と、文字列・グラフ理論なども含む探索用(ファインダー)とかで2冊ぐらいに分けて出してくれませんか?
そろそろぼろぼろになってきたし、先生の本は解説は個人的な偏りがなくソースは素直で読みやすいから次も買うんで。

102 :デフォルトの名無しさん:2009/02/21(土) 15:28:27
っていうか、逆行列そのものってほとんど必要ないよね

103 :デフォルトの名無しさん:2009/02/21(土) 15:49:47
>>100
行列式を計算するアルゴリズムは存在する.
効率的なものと非効率的なものがあり,余因子展開によるものは非効率.
効率的なものでも,行列の積や逆行列よりも小さなオーダで行うことはできない.

逆行列と同じオーダでやるのは簡単で,行基本変形で上三角形にして(ガウス消去),
対角成分の積を取ればよい.これも行列式の定義の1つとしてよく知られている.

104 :デフォルトの名無しさん:2009/02/21(土) 16:00:07
>>102
アルゴリズムでは直接求めたりはしないけどね。

>>103
やっぱり消去法とか三角行列になるんですか。参考になりました。

105 :デフォルトの名無しさん:2009/02/21(土) 16:00:17
>>101
そこまで大規模な改訂は多分行われないので諦めよう.
現代的な項目を追加しようとか,ソースが汚いので直そうとか,
何度か意見は出てるけど,結構な大仕事で,人材不足だとさ.

106 :デフォルトの名無しさん:2009/02/21(土) 16:21:31
行列の積が遅いのは結局 for と内積 a*x + b*y で掛け算と足し算を一度にやってるからだと思います。
もし掛け算のパートと足し算のパートを並列化できれば別の手法が考えられるし、作業配列を当然に仮定するので演算は前後演算に影響はなく、並列化どころかストリーム処理でもできそうな感じですかね。
そうすると、FFT乗算やカラツバ法とかと同等になるんじゃないでしょうか。といっても、パッと浮かんだ程度で専門でもないんで・・・

107 :デフォルトの名無しさん:2009/02/21(土) 16:28:36
行列演算回路でググってみた。研究はいくつかされてるのね

108 :デフォルトの名無しさん:2009/02/21(土) 16:44:54
>>106
FFTとかと同等ってどういう意味か分からないけれど,所謂Strassen系のアルゴリズムは
先に「後に使いまわせる和の項を作っておく」方法なので,その着眼点は良いよ.

ちなみに,昔から行列乗算の最適計算量は Θ(n^2) だろうと信じられていたんだけど,
2005年くらいの結果で,組合せ論と群論における2つの未解決予想を認めると,
実際に O(n^2) が達成できることが示されている.

109 :デフォルトの名無しさん:2009/02/21(土) 17:24:56
着眼点というよりも、カラツバ法の発想そのものなんですが。
例えば多倍長で1−100桁目の加算と、これと同時に別スレッドで101−200桁目を計算できます。
したがって、掛け算パート用の配列、足し算パートの用の配列をいくつも用意して、スレッドで並列計算すればいいだけです。
配列やスレッド生成のコストとか、配列ではスレッドローカル変数、スレッドは予め行列演算用のスレッドをクラス定義しておけばいいので主要コストとは考えられません。
100x100以上だとしても、結局はやってること(演算)は画像のブレンドと同等になっていくので考え方次第ではストリーム処理が可能となり、よって「同等」です。100x100の行列は普通使わないんですけど。

シングルスレッドにこだわるなら、確かにO[n^5]は遅いんですが、実際使うのは10x10とかテイラー級数で15桁程度の多項式係数を求める程度(20x20程度)なんで、
マテマテカ使って式展開させて行列式と逆行列をハードコーディングでもいいかなって思います。

他にはO[n^5]でも10x10程度だと、今のPCリソースからすれば遅いって実感は全くないのでプログラミングが楽な再帰による方法(つまり余因子行列)でもたいして問題は生じないってところです。
プロジェクションなどの用途なら4x4程度だし、そもそもDirectXとかになるからソフトウェア上のアルゴリズムとは関係ありません。

ただ、逆行列と行列積は球根と数値計算の要なんで速いに越した事はないですけど。

110 :デフォルトの名無しさん:2009/02/21(土) 18:52:06
>>109
で,君は何を主張したいの?

間違いだけ指摘しておくと,余因子展開で行列式を計算すると O(n!) 掛かる.
これは既に >>99, >>103 でも指摘済み.

111 :デフォルトの名無しさん:2009/02/21(土) 18:53:14
相手とのレベル差が見えてないのは無残だな

112 :デフォルトの名無しさん:2009/02/22(日) 01:44:21
確かにO[n!]は分かるんですが、それは数学上定義を愚直に一般化したアルゴリズムのときでしょ。
10x10程度まで良く使うなら式展開すればよいって書いてあるので、例えば2x2で行列式を展開した方法 a d - b c もO[n!]なんですけど、これ以外に他に方法はあるんですか?

113 :デフォルトの名無しさん:2009/02/22(日) 06:18:05
>>112
どう式展開するつもりか知らないけど,行列 A の成分をすべて不定元だと思って
行列式を書き下したものをハードコーディングするつもりなら,止めたほうがいいよ.
項の数が O(n!) になるので,結局四則演算の回数は減ってないから.

114 :デフォルトの名無しさん:2009/02/22(日) 08:25:06
>>113
やめたほうがいいじゃないくて、他に方法はないのかと聞いてるようですが?
そのようなアルゴリズムは知りませんと答えるのが正しいんじゃないですかね。

いつまでも計算量にこだわってるようじゃあなたの人生、先に進みませんよ。

115 :デフォルトの名無しさん:2009/02/22(日) 10:18:09
何に牙剥いているのかわからないけど
> PCリソースからすれば遅いって実感は全くない
みたいな色々な主観を全部記述するほうがアホみたいだと思われ
そんでもって,そんなの書いて人に聞くより試しにやってみればいいんじゃないの?
俺にはサッパリわからんが

116 :デフォルトの名無しさん:2009/02/22(日) 10:21:54
>>114
君は >>103-104 の流れで別のアルゴリズムがあることを理解したんじゃなかったかい?

117 :デフォルトの名無しさん:2009/02/22(日) 10:25:54
実際に測ったことがないからないから
> いつまでも計算量にこだわってるようじゃあなたの人生、先に進みませんよ。
みたいなことが言えるんだろうな

118 :デフォルトの名無しさん:2009/02/22(日) 10:51:12
ハードコーディング(笑)しようが何しようがQR分解の方が速い件
せいぜいn=4か5までだろ、計算量的に考えて…

119 :デフォルトの名無しさん:2009/02/22(日) 11:28:44
>>118
普通は行列式の計算はQR分解じゃなくてLU分解を使うことが多い気がする.
実際,LUのほうが精度的に良いケースが多いはずで,LAPACKはこちらを推奨している.

120 :デフォルトの名無しさん:2009/02/22(日) 13:10:12
>>118
行列は結局n=4,5ぐらいが一番使うんだけど。
どうせ誰かが実装したアルゴリズムを使うだけで自分で実装なんかしないんだし、ハードコーディング(笑)でなにか問題でもあるのか?

121 :デフォルトの名無しさん:2009/02/22(日) 13:32:29
普通は大学や研究所に依頼してやってもらうことが多いから、アルゴリズムを日々研究してるのなんかほんの数人しかいないよな。
なんとか自慢のアルゴリズムで特許とったところで、組み込みとかでブラックボックスにされちゃ確認のし様がないし。

>>117
言いたいことは分かるが、10マイクロ秒単位を気にして生きてかなければならない人生なんて哀れだな。その研究は幾らになるんだ?

122 :デフォルトの名無しさん:2009/02/22(日) 13:39:16
>>121
( ゚д゚) ・・・ (つд⊂)ゴシゴシ (;゚д゚) ・・・ (つд⊂)ゴシゴシゴシ
  _, ._
(;゚ Д゚) …!?

123 :デフォルトの名無しさん:2009/02/22(日) 13:50:20
>>120
誰かが実装した"ライブラリ"のtypo?
あと、ハードコーディングの意味は分かってる?
QRでもLUでもべた書きしたらいいじゃない

>>121
行列演算で10マイクロ秒って驚異だろ
何回呼ばれると思ってんだ

124 :デフォルトの名無しさん:2009/02/22(日) 13:51:01
いや・・・ある意味・・・現実って厳しいかも・・・

125 :デフォルトの名無しさん:2009/02/22(日) 14:12:29
>>120
> 行列は結局n=4,5ぐらいが一番使うんだけど。
ご冗談をw

126 :デフォルトの名無しさん:2009/02/22(日) 14:14:35
>>121
オーダーの違いがマイクロ秒単位でしか現れないという認識が残念すぎる
オーダー1つ落としたおかげで実社会で使われるようになったアルゴリズムがどれだけあると思ってるんだ

127 :デフォルトの名無しさん:2009/02/22(日) 14:17:07
アルゴ君だから仕方ないよw

128 :デフォルトの名無しさん:2009/02/22(日) 14:19:38
>>123
行列の話などしてないし、誰かと勘違いしてないか?

ところで、最近 sin/cosを効率的に求める CORDIC というとんでもないアルゴリズムを知ったのですが、
いまではこれら超越関数は普通にテイラー展開することが多くてすでに見捨てられるようです。
http://en.wikipedia.org/wiki/CORDIC

このような有用なアルゴリズムがあっても結局見捨てられてしまうわけで、どうして計算量にこだわるんですか?
上にもありましたが並列化など全く別のアプローチを取れば、一気に計算量が減らせることもあるわけで、
計算量を評価の指標とする考え方は全くずれてるに思うんですが。


129 :デフォルトの名無しさん:2009/02/22(日) 14:26:40
例えば行列なら、Strassen法のように速度(計算量)を稼ぐために全く意味不明な実装になっているなら、
それは既にアルゴリズムというよりも粒度が大きいプログラム、というか逆行列を解くための専用のアプリケーションじゃないでしょうか。

つまりifなどの分岐だらけになるようなアルゴリズムは、既に汎用のアルゴリズムではなくてその問題に特化したただの「プログラム」じゃないでしょうか。
アルゴリズムの複雑な組み合わせとなっているような大きいアルゴリズム(プログラム)などに計算量による評価とか全く意味ないと思うのですが。
実装がしやすい理解がしやすいかどうかで評価するべきじゃないでしょうか。

130 :デフォルトの名無しさん:2009/02/22(日) 14:36:55
アルゴリズム至上主義の人は、10年以上前の計算機性能を考えてみてはいかがでしょう。
当時、スパコンと呼ばれていた計算機は、現在のパソコン並か、それ以下です。
無駄な計算量の向上に時間を費やすよりも、使いやすくて読みやすいプログラムを書くことに時間をつかうべきですよね。
優れたアルゴリズムを考えても、すぐに廃れてしまうのです。
優れたプログラムを書けば10年後も使えるんです。



131 :デフォルトの名無しさん:2009/02/22(日) 14:39:03
>>125
行列はn=2,3,4,5ぐらいが一番多いけど、他に何に使ってるの?
まさか測定点を全て通る多項式とか出してないよね。

132 :デフォルトの名無しさん:2009/02/22(日) 14:40:18
あまりにひどい.勉強不足にも程があり,ほぼ全ての行が突っ込みどころだよ.

>>128
> いまではこれら超越関数は普通にテイラー展開することが多くてすでに見捨てられるようです。
現在でもCORDICが使われている場面はある.あなたが知らないだけ.

> このような有用なアルゴリズムがあっても結局見捨てられてしまうわけで、どうして計算量にこだわるんですか?
本当に,テイラー展開など比べて有用なのか評価したのかい?
特に,計算量はどういう測り方をして,どちらがどうなるのか分かってる?

> 並列化など全く別のアプローチを取れば、一気に計算量が減らせることもあるわけで、
並列計算機上の計算量にはそれなりの測り方があり,台数効果は計算量減少にカウントしない.

>>129
> 例えば行列なら、Strassen法のように速度(計算量)を稼ぐために全く意味不明な実装になっているなら、
Strassen程度で意味不明というのは力不足.
既にメジャーな数値計算ライブラリにおいてStrassen法は実装されており,
それまで時間が掛かりすぎていた問題が,解けるようになったという報告がある.

> それは既にアルゴリズムというよりも粒度が大きいプログラム、というか逆行列を解くための専用のアプリケーションじゃないでしょうか。
あなたの「アルゴリズム」と「プログラム」と「アプリケーション」の定義は何?

> アルゴリズムの複雑な組み合わせとなっているような大きいアルゴリズム(プログラム)などに計算量による評価とか全く意味ないと思うのですが。
なぜそう思うの?

> 実装がしやすい理解がしやすいかどうかで評価するべきじゃないでしょうか。
そういう評価があってもよいと思うけれど,これは定量的に量れるもの?

133 :デフォルトの名無しさん:2009/02/22(日) 14:40:56
とりあえず、十分に並列化したLU分解かQR分解かそのへんの
計算時間(計算量ではなく)を見積もって
余因子並列をぶちのめせたら解決、のような気がしないでもない

と下書きしていたら>>130に噴いた、どういう宗教だろう
その考え方はアルゴリズムスレじゃなくてプログラムスレで論ずるべきだな

134 :デフォルトの名無しさん:2009/02/22(日) 14:41:08
で、君は優れたプログラムを書いているのかね?

135 :デフォルトの名無しさん:2009/02/22(日) 14:44:40
>>130
> 当時、スパコンと呼ばれていた計算機は、現在のパソコン並か、それ以下です。
> 無駄な計算量の向上に時間を費やすよりも、使いやすくて読みやすいプログラムを書くことに時間をつかうべきですよね。
例えば巡回セールスマン問題で,アルゴリズムを変えずに100倍のサイズの問題を
同じ時間で解こうと思ったら,計算機性能は何倍になればいいか知ってる?

136 :デフォルトの名無しさん:2009/02/22(日) 14:48:02
>>133
電波・お花畑板が相当だと思う

137 :デフォルトの名無しさん:2009/02/22(日) 14:50:55
何を言いたいのか不明だけど、PCで測るなら普通はミリ秒単位なわけで、ある特定の問題についての解法を自分で実装して、少しベンチとって終わりじゃないのか?
別にその報告や論文書くわけじゃないし。
おまえはそんなに凄い「世の中を変えちゃうような壮大な」研究でもしてるか?(脳内でw)

組み込みとか4ビット8ビットの貧弱CPU向けのアルゴリズム(というかすでに特化プルグラムだけど)の議論なら分かるけど、
PCやスパコンwとかだと、結局カッコいいこといってるけど実際は実装が面倒だからハードでごり押しじゃないの?
大金もらってるから面倒とか言うことは無いだろうけど、もしくは断念して誰かが作ったライブラリを使うとか。

つまり時代が流れて、ハードが進化したから、実社会で採用されたと考えられなくもない。
例えばインタプリタや中間コードは当時70年代は研究目的で全く見向きもされなかったけど、今は見直されたというよりもハードが進化したから普通に当たり前になってるとかのこと。


138 :デフォルトの名無しさん:2009/02/22(日) 14:52:51
んでだな、>>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

142 :デフォルトの名無しさん:2009/02/22(日) 15:07:41
>>132
なんか一気に吹き出したって感じだな。このオッサンはww

なぜ?どうして?定義は何?とかどこの哲学版だよ

お花畑版ってのが2chにあるから、君は早いところそっちに引っ越した方がいいよw

143 :デフォルトの名無しさん:2009/02/22(日) 15:11:58
>君は2chの分際で少々生意気だな。
>そのうちIP抜いて不幸の手紙でも送ってやろうか?w

受けるw
もっとやれ

144 :92他 ◆DRdCZDy4PY :2009/02/22(日) 15:14:51
>>141
うわあ、礼儀飛び越えて中傷脅迫してるなり…

>>142
定義が大事な話してるのに、それを蔑ろにしては何も語れないかと
というわけでお花畑はあなたが行くべきっぽいんだが

145 :デフォルトの名無しさん:2009/02/22(日) 15:21:21
Strassen程度とかも別に難しくはないけど、もっと理論的な裏づけ、例えばルンゲクッタ法みたいなのが欲しいよね。
奥村センセの本でも「複雑すぎるし、たいして性能向上ないから省略」とか書いてあるし。

>>132
君はアルゴリズムの深みにはまりすぎてんじゃないの?w

一番理解できないのは、

>それまで時間が掛かりすぎていた問題が,解けるようになったという報告がある.

それもO[n^3]やO[n^2]で影響が出るほどの行列(想定できないが10000x10000とか)のことでしょ。
実社会やビジネスではそんなの大きい行列は使いません。
ベンチャー企業や研究機関でもこの行列を必要とするところは考えにくく皆無なため、結局その報告は「これは実用的です」って言う宣伝(サクラ)じゃないの?

誰かが論文にあるサンプルコードどおりに実装してライブラリにすれば終わりだから別にStrassen法程度を否定するつもりはないけど、壮大な話を聞いて君は騙されちゃったんだねw

146 :デフォルトの名無しさん:2009/02/22(日) 15:37:49
>>135
というか、このスレは同じ人がレスしてるっていう前提を持ってる時点であなたの妄想じゃないの?

たとえば「計算機性能は何倍になればいいか知ってる?」について知ってる・知らないと答えたところで、議論についてあなたに何か変化があるんですか?それはあなたの傲慢から生じるあなたの偏見じゃないですか?
よく読んでみると、「ハードが進化すると当時遅いっていわれてたアルゴリズムも遅くないよね」って書いてあるようですけど。

行列で計算量云々についての議論をしたとしてもn=1000なら、
8バイト*1000^2で8メガぐらいあるんですが、いくらO[n log[n]]となったとしても常時8メガの演算(それもメモリ間コピー含む)が実用的だと思いますか?
結局現在でもn=100ぐらいが実用の限界でありアルゴリズムの制約条件じゃないですかね。
つまりアルゴリズムの計算量の議論は既にお花畑なんでしょう。もっと実社会に即した評価の目をもってみてはいかがですか。

147 :デフォルトの名無しさん:2009/02/22(日) 15:40:21
>>125
あのー
>>131に答えてもらえないんですか?
どうせ線型代数の教科書も読んだことないんでしょうけどw

148 :デフォルトの名無しさん:2009/02/22(日) 15:40:29
超文かくやつは吟味して短くおねがいします

149 :デフォルトの名無しさん:2009/02/22(日) 15:42:09
アルゴリズムなんて、クヌースが本を書き始めたときにはもう終わっていたんですよ。

150 :デフォルトの名無しさん:2009/02/22(日) 15:44:12
妄想ってのは肯定であれ否定であれ
まじめに相手にする人がいると激しくなっていくものだ
霊が見えるって人もこのたぐい

151 :デフォルトの名無しさん:2009/02/22(日) 15:44:45
謝れ! 数百次元の疎4階テンソルを扱ってる俺に謝れ!

152 :デフォルトの名無しさん:2009/02/22(日) 15:48:54
ごめんなさい。

153 :デフォルトの名無しさん:2009/02/22(日) 15:53:19
あの・・・どうでもいいんですが、計算量は定量的に見積もることが目的みたいですが、何を定量化してるんですか?
普通は速い・遅いは時間ですが、オーダは計算量で、式のステップ数というか計算回数とでもいいましょうかもしくはリストの個数とでもいましょうか
どちらにしても計算量というのは時間ではないようなので、全く速い遅いの指標になってないんじゃないでしょうか。

そうすると、計算量が多いアルゴリズムO(n^3)でもスレの流れにあるような議論のように、速いとか実用とかは実際はアルゴリズム自体ではなくてハードによるってことだけなんですけど・・・
それでも観念しないのはアルゴリズム職人としてのポリシーか何かあるんですか?アルゴリズム研究とは一種の宗教なんですか?

154 :92他 ◆DRdCZDy4PY :2009/02/22(日) 16:02:05
とりあえず2次〜6次くらいまでの正則行列について
並列的な余因子展開で逆行列を求める速度と
並列的なQR分解または並列的なLU分解で逆行列を求める速度を
それぞれ算出するんだ

一般的なCPUでの実測とベクトルプロセッサでの実測と四則演算等の段数両方考察するといいぞ

ちなみに俺に任せるとQR分解の勉強からはじめなければならないから
演算の段数数えるだけでたぶん一ヶ月はかかる、ひゃほーい

155 :デフォルトの名無しさん:2009/02/22(日) 16:02:15
アルゴ君絶好調だな

156 :デフォルトの名無しさん:2009/02/22(日) 16:24:21
>>145-147
構造計算や大規模偏微分方程式に使うFEMのソルバについて軽く調べてみるといいよ
nが数万とかの(疎)行列の固有値救解や連立方程式計算をすることになるから

んで、その為のスカイライン法とか、マルチフロンタル法とか、
効率のいいアルゴリズムを見つけた上で更に並列計算に持っていこうとするんだよ
やってることは結局のところ全てLU分解(正確にはコレスキー分解)なんだけどね

そういう行列計算の世界もあるんですが、知らなかっただけですよね

157 :デフォルトの名無しさん:2009/02/22(日) 16:37:53
追記すると、FEMじゃなくてBEMなら疎行列じゃなくて密行列になるので
お望み通り、「nが数万の行列」になるね
FEMやらBEMやらがビジネス(笑)で実用化されてないとはまさか言われないだろうしね

158 :デフォルトの名無しさん:2009/02/22(日) 16:39:16
ttp://yucl.net/man/19.html
まあまあおまえら、コレでも読んでマターリしようぜ

159 :デフォルトの名無しさん:2009/02/22(日) 16:46:14
アルゴには理解も実装も何もかも無理だって随分前に俺が指摘したじゃん…。

160 :デフォルトの名無しさん:2009/02/22(日) 17:21:13
>>145
Googleのページランクの計算は結局のところ行列の計算なんだけど,
どれくらいのサイズの行列を使ってるか知ってるかい?

数値計算の分野では 10000×10000なんて「十分小さい」行列だよ.

161 :デフォルトの名無しさん:2009/02/22(日) 17:22:25
で、実際問題余因子展開によるクラーメルの公式って並列化できるのか?
行列をプロセッサ数に効率よく分割できなくね?

162 :デフォルトの名無しさん:2009/02/22(日) 17:28:34
>>160
シッ!そういう言い方すると
>議論についてあなたに何か変化があるんですか?それはあなたの傲慢から生じるあなたの偏見じゃないですか?
とか言われちゃうよ。どうせ知らないのにね。

で、どんぐらいなの?

163 :デフォルトの名無しさん:2009/02/22(日) 18:00:24
>>162
凄い勢いでデータが増えているので今現在ではもっと増えてるかもしれないけど,
2008年の末で大体数百億くらい.ちなみに2002年くらいで数十億だった.
ただし,もちろん疎行列で,非ゼロ成分もこのオーダーくらいしか存在しない.

164 :デフォルトの名無しさん:2009/02/22(日) 19:05:11
>>146
> よく読んでみると、「ハードが進化すると当時遅いっていわれてたアルゴリズムも遅くないよね」って書いてあるようですけど。
逆だ逆w 具体的に何倍になるか答えてみろよw

165 :デフォルトの名無しさん:2009/02/23(月) 01:31:58
8ビット時代のメモリが4kBくらいでCPU駆動周波数が
2MHzの頃のアルゴリズムを後生大事にしてる愚か者っているよなw。

166 :92他 ◆DRdCZDy4PY :2009/02/23(月) 01:42:44
超大量にループぶん回す必要のある箇所は
今でも極限までアルゴリズムや実装をチューンナップするものだ
もっともプロセッサの配線やライブラリと化したものが多いだろうけど

167 :デフォルトの名無しさん:2009/02/23(月) 02:28:08
>>165
> 8ビット時代のメモリが4kBくらいでCPU駆動周波数が 
> 2MHzの頃のアルゴリズムを後生大事にしてる愚か者っているよなw。 
誤字?
×アルゴリズム
○プログラム

168 :デフォルトの名無しさん:2009/02/23(月) 02:29:15
>>165
おまえはアルゴリズムの評価に コンニチハ セカイ みたいな文字列の出力まで考慮するタイプの人間なのか

169 :92他 ◆DRdCZDy4PY :2009/02/23(月) 02:43:52
花壇の叩き台としてイージーに計算段数を考えてみた
#まじめに読まないこと推奨のような気がしてきた

(r s t)
(u v w) = A なる3次正則行列 A についてクラーメルの公式
(x y z)

(vz-wy xw-uz uy-vx)
(ty-sz rz-tx xs-ry)÷{r(vz-wy)-u(ty-sz)+x(sw-vt)}
(sw-vt tu-rw rv-su)

vzで1段、vz-wyで2段、r(vz-wy)で3段、
r(vz-wy)-u(ty-sz)+x(sw-vt)は3項だから一気に足せず5段
それと2段で計算終わってる(vz-wy)〜(rv-su)を掛けて6段

必要な計算の段数は6段

2次正方行列の固有値を求めるのに2段
3次正方行列の固有値を求めるのに+3段で5段
4次正方行列の固有値を求めるのに+3段で8段
5次正方行列の固有値を求めるのに+4段で12段
6次正方行列の固有値を求めるのに+4段で16段
n次正方行列の固有値を求めるのに+(1+天井[log(底2){n}])段で総計は…めんどくさい

行列式の算出が一番段数食うので
余因子を固有値で割る最後の1段があれば逆行列は求まる

とりあえずべらぼうに回路の面積食いそうな点とか
検証が怖いので考えない方向。

何で俺、こんな時間にこんなこと考えてるんだろ。
そして絶対どっか豪快に間違えてるぜ、眠いし。

170 :92他 ◆DRdCZDy4PY :2009/02/23(月) 03:40:14
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の右上隅が一番、そして派手に段数食いそう。

171 :デフォルトの名無しさん:2009/02/23(月) 05:22:34
>>160
それって、よくわからんけどグラフ理論にある隣接行列のことじゃないか?
要素が1か0とかほとんど固定パターンのやつ。それを愚直に演算してるとでも思ってんのかよ。
「行列サイズは数億になるんだ!」とか偉そうにするな。お前は一生知ったかのカス野郎のくせにww

172 :デフォルトの名無しさん:2009/02/23(月) 05:27:06
>>171
要素が0と1じゃ情報少なすぎだろjk
おまえの頭はどこまで真っ直ぐなんだよ・・・

173 :デフォルトの名無しさん:2009/02/23(月) 05:41:57
>>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
さすがに朝からしゃぶしゃぶはないわ

177 :デフォルトの名無しさん:2009/02/23(月) 07:17:16
>>173
とりあえず、君は名前を付けてみない?

178 :デフォルトの名無しさん:2009/02/23(月) 07:18:40
自分が使わないから他でも使われないという思い込みはアルゴ君の特徴
もう放っておけ

179 :デフォルトの名無しさん:2009/02/23(月) 07:20:00
>>172
誰が書いたか知らないけど、行列で言えばn=3万つまり、
30000^2 * 8バイトは6ギガで既に32ビットのメモリアクセスの限界を超えてるってことは分かってる?
>>160で戯言が書いてあったけど、「小さい行列」とか知ったかもそれぐらいにした方がいいよ。

アルゴリズムが200^3か200^2かなんて実質関係ないし。
2次関数のグラフで見てもその値は両者ともはるか上のほうでしょ。
結局そのアルゴwで解を得られるかどうかでしかないんじゃないのかな…
計算量を指標とすることで、学問・理論とは関係ないお花畑の議論に持ち込まれちゃって騙されちゃってるんだろうなwww考え直した方がいいよ

180 :デフォルトの名無しさん:2009/02/23(月) 07:21:07
じゃあお前はどんなに大きな配列でも
バブルソートでソートしとけや

181 :デフォルトの名無しさん:2009/02/23(月) 07:27:29
メモリに載んないから色々工夫が必要なんだよ。
その都度再計算したり、0でない要素だけ保存したり、ディスクに保存したり。

182 :デフォルトの名無しさん:2009/02/23(月) 07:30:19
というか6ギガのメモリを使う行列の演算について、アルゴリズムが早い遅いとか全く無意味な議論だよね。
そもそも、普通に買える計算機では1000x1000の行列なんかは普通はOSに叱られて作れないし、オーダーでそれぞれのアルゴリズムを比較するって言う思考自体が理想論なんだろう。

6ギガの配列は32ビット環境では確保できないし、「6ギガ^3 と 6ギガ^2 では計算効率が全然違うんです!」とか夢の話をされてもな・・・(笑)

183 :デフォルトの名無しさん:2009/02/23(月) 07:31:21
1000x1000の行列が作れなかったら
画面のキャプチャもできないよwwww

184 :デフォルトの名無しさん:2009/02/23(月) 07:33:04
バブルソートは遅いけど、遅いってことが問題になることは無い。もう一回アルゴリズムの目的とはなんであったかを勉強したほうがいいんじゃないかと思う。
速いか遅いかではないよ。

君だって、文字列検索とか結局は線型サーチ使うでしょ

185 :デフォルトの名無しさん:2009/02/23(月) 07:42:41
そりゃデータによってアルゴリズムは使い分けるさね。
文字列検索が遅いと感じる大きさのデータを扱う場合は
他のアルゴリズムを使う事を検討するさ。

186 :デフォルトの名無しさん:2009/02/23(月) 07:43:37
>>184
じゃあ Google も線形サーチを使えば満足するんだねw

187 :デフォルトの名無しさん:2009/02/23(月) 07:56:52
突っ込みどころしかなくて吹くわー。トヨタ他の車の強度シミュレーションが数百節点でできるかよ。て言うか、800万画素のフィルタリングなんてデジカメのASICレベルの話じゃん。

アルゴリズムの話で何で評価基準ガユーザビリティなんだw

188 :デフォルトの名無しさん:2009/02/23(月) 08:03:20
1000×1000が巨大とかwww
たった8メガwww

189 :デフォルトの名無しさん:2009/02/23(月) 08:06:26
>>169-170
仮定は「無限に大きな回路を用いる」ことかな?

行列式をハードコーディングした際の計算段数は大体
log(項の長さ) + log(項の数)で, n log n くらい.

LU分解(ガウス消去)による方法の計算段数は,
各行ごとの掃き出しが 3 段(並列的に b - (a/u) v を計算)なので 3n くらい.
b - (a/u) v で計算したものを次々と使いまわすことで,段数の爆発を抑止してる.

190 :デフォルトの名無しさん:2009/02/23(月) 08:11:32
>>182
> 1000x1000の行列なんかは普通はOSに叱られて作れないし
どんなOSw

191 :デフォルトの名無しさん:2009/02/23(月) 08:15:32
>>182
それ書いたの自分だけど、メモリマップドファイル知らないの?グーグル先生に聞いて。

で、ディスクからの読み出しは線形時間の処理で、行列の処理はO(n^3)だから、行列がでかいほどアルゴリズムの改善が優位になるんだけど。

むしろ、小サイズ行列ってどこに使われるか例が欲しい。同次変換以外には?

192 :デフォルトの名無しさん:2009/02/23(月) 08:31:17
HDDにデータおいて、固定長なら値取り出せるだろ


193 :191:2009/02/23(月) 08:43:35
ん、違うな。
「数千数万行の行列を使うのはそういう需要があるから」ってのが答えなのか。PCやスパコンの記憶容量の発達(と十分な処理速度)でそれが近年ようやく現実的になっただけで。

194 :92他 ◆DRdCZDy4PY :2009/02/23(月) 12:01:06
>>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分解のとき何の理解を間違えてるんだろう…

195 :92他 ◆DRdCZDy4PY :2009/02/23(月) 12:13:40
>>169>>194の計算段数を比較すると
クラメール(てかクラーメルじゃないやん)の公式が優位なのは
4次以下の行列に対してで、5次以上の行列に対しては
ガウスの消去法のほうが有利

ただもちろん加減乗除それぞれで速度違いそうなところとか
一番致命的と思われるのは、そんなだだっ広い贅沢な回路できるかーいなところ
とはいえガウスの消去法ならパイプライン方式諦めてレジスタ使うようにすれば
異なった段数で回路使いまわしできそうなんで…というかたぶんまんま
ベクタープロセッサが求められた理由の多くをこれが占めてるような

という夢をみたので、ここから壮絶な袋叩きが始まるか華麗にスルーされるのであった

196 :92他 ◆DRdCZDy4PY :2009/02/23(月) 12:48:26
いや俺は何を言っているんだ
クラメールの公式で行列式や余因子の値求めるときに
ガウスの消去法が効率的な場合はそっち使えばいいじゃないか

197 :92他 ◆DRdCZDy4PY :2009/02/23(月) 13:09:55
…ガウスの消去法で行列式の素を計算した時点で
逆行列まであとたった2段やん…

一方、行列式の素はn項あるんで、掛け合わせるだけでlog(2)nはかかるし
そして余因子に掛け合わせる1段も必要

余因子による行列式計算の段数が
nが1増えるごとにlog n のペースで増えてしまう余因子展開法と
nが1増えるごとに2のペースでしか増えない上に逆行列まであと2段まで迫る
ガウスの消去法、か。

198 :デフォルトの名無しさん:2009/02/23(月) 15:24:07
悪いけど10000の書き間違えなんだけど・・
1000x1000の行列の書き間違いのレベルだとやっとついてこれると思ったのか、反応するゴミが多いなっておもった・・・・
2chでそれもこんな糞スレでゴミのあいてしてもね・・・

199 :デフォルトの名無しさん:2009/02/23(月) 15:28:11
というか、書き忘れたけど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みたく勘違いしちゃうゴミが多いけど、「速くなった」「バブルソートは遅い」などの表現はアルゴリズム評価の参考にすらならない。
結局は実際に動かして体感で判断するんだろ。これが計算量のマジックだけど、何の指標なんだかちゃんと理解し解かないとな。


202 :デフォルトの名無しさん:2009/02/23(月) 15:50:39
>>201
> n=100の行列では(100^2)^3で
何で n^6 してるの?w

203 :デフォルトの名無しさん:2009/02/23(月) 15:52:27
>>201
> 関数の形(指数関数)
n^2 とか n^2.22 とか n^3.12 って指数関数なの?

204 :デフォルトの名無しさん:2009/02/23(月) 15:59:11
だからさ、計算量なんかどうでもいいけど、実装が簡単なもの、メンテナンスしやすいもの、図を書けば誰でも理解できるような「算法」にするべきじゃないか?
多少複雑なアルゴリズムなら、たいては他のアルゴリズムの組み合わせでしかないし、そうでないなら数学による証明などの理論的裏づけがないと全く理解できない。
アルゴリズムが速いかどうかなんかどうでもよくて、解が出ればいいよ。それよりも理論的な不備や実装によるバグ探しの方が数十倍恐ろしい。


205 :92他 ◆DRdCZDy4PY :2009/02/23(月) 16:04:33
>>204
最悪のアルゴリズムでもそこそこ速い小さな問題も数多く
そういう場面では多少遅くてもバグの少ない実装を心がけるべきという主張はわかる



全ての問題がそうとは限らない
巨大な行列の計算なんかはモロにそういうチューンアップが問題になるケースでしょ、と

206 :デフォルトの名無しさん:2009/02/23(月) 16:24:03
>>204
トレードオフってものがあるよね

207 :デフォルトの名無しさん:2009/02/23(月) 18:15:39
20兆年かかる計算を2秒にするアルゴリズムを捨てることはできない。

208 :デフォルトの名無しさん:2009/02/23(月) 18:44:42
>>201
> 950ミリ秒が95ビリ秒になればそれは速い

えー

209 :デフォルトの名無しさん:2009/02/23(月) 20:36:44
コムソートって本当に速いの?

210 :デフォルトの名無しさん:2009/02/23(月) 20:47:17
「速くは無い」という結論が出てるよ。

211 :デフォルトの名無しさん:2009/02/23(月) 20:48:06
ちょーはやいよ

212 :デフォルトの名無しさん:2009/02/23(月) 20:51:19
>>201
指数時間じゃなくて多項式時間な。根本から間違ってるぞ。
あと、形が問題になるのはnが大きいと言う仮定をおくから。お前はnが大きい方がいいのか小さい方がいいのかどっちなんだ。

>950ミリ秒が95ビリ秒になればそれは速いが、この「速度」による評価はアルゴリズムではなくて、ハードによるんじゃなかったか?
ハードを変えて実行速度を10倍にするのがどれだけ大変だと思ってんだ
問題の評価は同ハードでやるに決まってんだろアホ

213 :デフォルトの名無しさん:2009/02/23(月) 21:02:17
コムソートが終わる時間ってどうやって見積もればいい?

214 :デフォルトの名無しさん:2009/02/23(月) 21:04:34
>>210
どこどこ?

215 :デフォルトの名無しさん:2009/02/23(月) 21:06:36
リソースを全く消費しないという点で考慮に値するよ>コム(r

216 :デフォルトの名無しさん:2009/02/23(月) 21:27:58
安定じゃないと使いにくいよね

217 :デフォルトの名無しさん:2009/02/23(月) 22:37:01
アルゴ君、元気だな。

218 :デフォルトの名無しさん:2009/02/24(火) 03:13:15
>>205
そんないきり立って主張するのもいいが、バグのほうが怖いな。
ちゃんと動いてたのに2年後に動かなくてバグ探しとかどうする?
そのアルゴリズムの仕様や制約が原因で。

今あるハード以上のことを考えて、限界を突破しようと、人より先に行こうとしても苦難の道なだけじゃないか?
それで報酬はいくらもらえるんだろう。windows95の時代はメモリ16-32が標準だったけど、今じゃハードの進化は10倍どころじゃないよな…
所詮ソフトウェア上での実装でしかなく上にはハードによる制約があるから、そんなにこだわっちゃうとストールマンみたいな一種の宗教になっちゃうよ。
オレはFF10で「全てを超えしもの」をもらったけど、結構大変だったぞw

219 :デフォルトの名無しさん:2009/02/24(火) 03:14:57
こいつ高校生か中学生?

220 :デフォルトの名無しさん:2009/02/24(火) 03:29:10
>>212
なんかカッコつけて書いてるようですけど、多項式と関数の違いを区別できてますか?
「多項式の形が重要だ!」とは普通言いませんよね?
あなたは関数との違いを書きたいようですが、多項式というからには「+」による連結を想定してるんですか?
根本的に間違ってるのはあなたの脳味噌の方でしょう。あなたの脳味噌はとっても臭そうですけど。

221 :92他 ◆DRdCZDy4PY :2009/02/24(火) 03:29:53
>>218
ストールマン程度で宗教なら、アンドリュー・ワイルズとかペレルマンとかどう評価するんだろう…

222 :92他 ◆DRdCZDy4PY :2009/02/24(火) 03:31:39
>>221書き直し
ストールマンの行列の積の計算の省力方法程度で宗教なら
アンドリュー・ワイルズのフェルマー最終定理の証明とか
ペレルマンのポアンカレ問題解決とかどう評価するんだろう…

223 :デフォルトの名無しさん:2009/02/24(火) 03:36:17
名前: 92他 ◆DRdCZDy4PY [sage]

なんでこいつはこんな時間にこんな糞スレに張り付いてるんだ?
どうせニートだろうし。一回切腹してみた方がいいんじゃね?w


224 :デフォルトの名無しさん:2009/02/24(火) 03:39:13
>>222
評価?おまえには一生謎のままの方がよさそうだな。一生悩んで自分なりのアルゴを出してみたらどうよ?アルゴ君w

225 :92他 ◆DRdCZDy4PY :2009/02/24(火) 03:41:24
アルゴ君って俺のことだったのか!
丸っきり気付かんかったぞ

226 :デフォルトの名無しさん:2009/02/24(火) 03:51:49
>>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
釣りえさもつけずに釣りとな

229 :デフォルトの名無しさん:2009/02/24(火) 04:52:22
>>222
ブルーバックスを読みすぎると、あなたのように頭がおかしくなっちゃうんで今度から気をつけたほうがいいですよ。

230 :92他 ◆DRdCZDy4PY :2009/02/24(火) 04:55:24
俺はいいけど、ブルーバックスへの中傷じゃね?

231 :デフォルトの名無しさん:2009/02/24(火) 04:58:53
>>212
同ハードで評価するのは当然ですけど、その報告書や論文・ベンチマークで使ったハードが、スパコンとか店で普通に買えないようなハードだと全く意味ないってことじゃないの?
それに、ベンチのプログラムなんかいくらでもそのアルゴリズムが有利になるようなコードを書くことができるんだけど・・

ハードの進化も>>218にあるようにとんでもないし、今のゆとり世代にwindows3.1や95の時代でも「この性能は旧式のスパコンと同等だ!」とか宣伝されてたなんて信じられないだろう。
脳味噌ゆるゆるの奴はすぐ引っかかるみたいだけど、ま、騙されないようにしてよww

232 :デフォルトの名無しさん:2009/02/24(火) 05:05:07
>>231
なんで最初と最後に言ってる事がちがうの?バカなの?

233 :デフォルトの名無しさん:2009/02/24(火) 05:21:58
>>232
バカはおまえだろw
早く働いた方がいいと思うよ

234 :92他 ◆DRdCZDy4PY :2009/02/24(火) 05:23:41
>>233
まさかと思うけど、>>232は俺だと勘違いしてる?

235 :デフォルトの名無しさん:2009/02/24(火) 05:26:58
まずは>>212が妄想で言ってないというなら、「大きい」というのはどれぐらいからなのか、
実行速度を10倍にするのがどれほど大変なのか明らかにしてくれないか?

そうじゃないならおまえの妄想か、創価学会への勧誘にしか見えんよw
おまえが高校生で、ブルーバックス読みすぎて頭おかしくされちゃってるっていうなら見逃してやるけどww

236 :デフォルトの名無しさん:2009/02/24(火) 05:33:54
>>233
いいやおまえだ

237 :デフォルトの名無しさん:2009/02/24(火) 05:39:26
>>231
> それに、ベンチのプログラムなんかいくらでもそのアルゴリズムが有利になるようなコードを書くことができるんだけど・・
なんて言っちゃってる辺りは確かにバカに思うよ

238 :デフォルトの名無しさん:2009/02/24(火) 05:51:29
>>237
そんなこといってる余裕があるなら早いところハロワで職探せ。おまえのお母さんは泣いてるぞ。

239 :デフォルトの名無しさん:2009/02/24(火) 06:12:30
公務員のほとんどは基本年収500万で、住宅手当とかつけて700万以上なんだよね。
どっかの市長がブログで公務員給料を公開してた。

いくら難しい勉強しても、いくら資格をいっぱい取っても年収がこれにも満たない底辺(ITドカタ)は多いだろ。
民間よりも公僕のはずの公務員の方が給料多いってのはおかしな話だけどねぇ
こんな糞スレで傷の舐めあいなんかしてないで早く働いたほうがいいんじゃないの?ww

240 :デフォルトの名無しさん:2009/02/24(火) 06:20:58
とニートが申しております。

241 :デフォルトの名無しさん:2009/02/24(火) 06:29:52
公務員はこうやって高年収だから実際はニートとかIT派遣とかの生活なんてどうでもいいんだろうな。
政治家が悪いというよりも公務員のニート・派遣への偏見の方が問題は大きそうだ。
基本給は年収100万!のバイトとか年収300万の派遣ぐらいにして、後は成果主義なら公務員も世の中の厳しさを気がつくかもな。

>>222
おまえは年収100万の分際で、「フェルマーの定理バンザイ!」とか哀れな奴だ・・・

242 :デフォルトの名無しさん:2009/02/24(火) 06:50:41
>>240
ニートの君には実感沸かないだろうけど、早いところ仕事探して世の中に出ればこれに実感が湧くようになるんじゃないか?かなり大問題だよ。

243 :デフォルトの名無しさん:2009/02/24(火) 06:58:47
>とニートが申しております。

こんな単発レスしか出来ないゴミに何言っても無理。
一生2chと一緒に生きていくって宣言してるようなもんだろw
確かにこういうのは自民党が言ってたけど自業自得だよな・・・自己責任だったか?w

244 :デフォルトの名無しさん:2009/02/24(火) 07:20:52
巣に帰れクズども
http://pc11.2ch.net/test/read.cgi/tech/1233622578/

245 :デフォルトの名無しさん:2009/02/24(火) 07:51:54
アルゴ君大活躍だなあ。なんか詳しそうな人が数人居るのに勿体無い。

246 :デフォルトの名無しさん:2009/02/24(火) 08:00:29
↑やーい無職無職wおれと同じだw

247 :212:2009/02/24(火) 08:01:31
色々アンカついてて面倒だな。
多項式時間、指数時間、ランダウの記号の意味ぐらい調べてきてからもう一度釣りに来てくれ。
この流れでnなんて問題の大きさ以外に何があるよ…。

248 :デフォルトの名無しさん:2009/02/24(火) 08:10:38
アルゴ君ってのは誰だか知らんけど。
このスレの奴らは、各種アルゴリズムに詳しいだけで自分でアルゴリズムを発案するようなタイプではないな。
いつまでも計算量による評価を過信してばかりで、ただの安月給のオッサン(それもアルゴリズムは趣味なんです!とか)でしかないんじゃないかな。
その詳しそうな人という奴らの書き込みをよく見ると、ググればすぐ出てくるようなことを少し難しく偉そうに言ってるだけってことに気がつく。
各種アルゴリズムを知っていても、ここのオッサンも所詮はハードでごり押ししかできなだろうしなぁ・・・

「行列式のハードコーディングはO[n!]だから絶対ダメ!」とか
「O[n^5]のアルゴリズムは遅くて使い物にならないから使ってはだめだ!」とかアホだろ。
もしちゃんと勉強してる奴とか専門家ならこういう表現は使わない。
信用すのは勝手だけど、n=無限大みたいな何の具体例もないお花畑の説明は、上のレスには層化がどうとかあるけど宗教の勧誘と同じ

249 :92他 ◆DRdCZDy4PY :2009/02/24(火) 08:13:03
>>248
計算量評価でなく、段数評価やってみたんだけど…

250 :デフォルトの名無しさん:2009/02/24(火) 08:17:30
>>248
アルゴリズム専門の准教授ですが何か

251 :デフォルトの名無しさん:2009/02/24(火) 08:28:28
クラメールの公式のハードコードなんてわかりやすさもメンテ性も0だと思いますが
如何お考えでしょうか

252 :デフォルトの名無しさん:2009/02/24(火) 08:35:20
>>245
おまえさ、アルゴ君ってだれよ?ウザイよ。

グラフ理論とかNP困難とかに関心持ってるんだろうけど、おまえの脳味噌じゃ時間の無駄だから止めとけ。
そもそも関数とか多項式の違いとか分かってないんだろ。
そのていどの奴がアルゴリズムに関心持っちゃうのはブルーバックス(もしくはウィキ)の読みすぎ。はよ働けw

253 :デフォルトの名無しさん:2009/02/24(火) 09:03:03
>>252
アルゴ君今日も元気だね

254 :デフォルトの名無しさん:2009/02/24(火) 09:24:01
>>250
おまえがこのスレで偉そうにしてる奴か。2chごときでいきがる。
2chばっかりみてると研究所のPCにウイルスが入しちゃうかもな。
研究所のPCから2chへのアクセスには最新の注意をしておいた方がいいぞ

255 :デフォルトの名無しさん:2009/02/24(火) 09:25:38
>>253
おまえがアルゴ君か。2chのやりすぎで頭おかしくなっちゃってんだろ。

256 :デフォルトの名無しさん:2009/02/24(火) 09:29:37
アルゴ君探検隊の大冒険

257 :デフォルトの名無しさん:2009/02/24(火) 09:58:05
>>250
専門家ということですけど、アルゴリズムの分類が仕事でしょ。
分類以外に他に仕事あるんですか?

「例えば行列式は数学的定義どおりにコーディングしたらダメ」って言うのは、いいすぎですよ。
あなたがだれか知りませんが、計算量と実測速度の違いぐらい分かってますか?
それで、本当に専門家を名乗るつもりなんですかね…

258 :デフォルトの名無しさん:2009/02/24(火) 10:02:50
>>257
他のスレでフルボッコされてこのスレを住処にしてんだから悪口言っちゃダメ
このスレが一番の楽しみなんだしとっても可哀想な人なんだから、お山の大将が気に食わなくても黙っててあげて

259 :デフォルトの名無しさん:2009/02/24(火) 10:04:09
自演乙w

260 :デフォルトの名無しさん:2009/02/24(火) 10:40:39
>>257
ニートのようですが、何かお仕事はお持ちなのでしょうか?
(ry

261 :デフォルトの名無しさん:2009/02/24(火) 12:01:10
>>245
何がもったいないの?

262 :デフォルトの名無しさん:2009/02/25(水) 02:05:10
>>250
あれ?レスないね。
「準教授」とか言ってみたけど名前負けだよねw

263 :デフォルトの名無しさん:2009/02/25(水) 03:28:24
>>226
「それもこの指数は普通は正数限定で、多項式ではn^3.11などありえない。」wwww
アルゴ君ってここまでバカだったのか

264 :デフォルトの名無しさん:2009/02/25(水) 03:41:30
はぁ?

265 :デフォルトの名無しさん:2009/02/25(水) 04:33:00
アルゴ君、つっこまれても意味がわかてないから、はぁ?としか返せないのか

266 :92他 ◆DRdCZDy4PY :2009/02/25(水) 05:23:34
ストールマンを別人と勘違いしてた…

267 :デフォルトの名無しさん:2009/02/25(水) 07:50:25
あんまり他所で暴れてやるなよ

268 :デフォルトの名無しさん:2009/03/01(日) 01:31:23
マリオRPGにあるマジカルスイッチのようなパズルを解くアルゴリズムを考えているのですが、誰か教えてください。

269 :デフォルトの名無しさん:2009/03/01(日) 01:35:19
考えているんですか。
では考えてください。

270 :デフォルトの名無しさん:2009/03/01(日) 01:51:14
>>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での場合を考えているが、任意の個数でも可能なアルゴリズムを考えたい。よろしくお願いします。

272 :92他 ◆DRdCZDy4PY :2009/03/01(日) 02:50:20
>>271
オレ流解法のヒント:
最上段の押すパターンAを仮定 → N段目を■■■…■にするようN+1段目で調整
→ 最下段にパターンBがあらわれる
ので、AとBの組み合わせを幾つか調べておく

273 :デフォルトの名無しさん:2009/03/01(日) 08:33:46
ちょうど昨日スーパーマリオRPG(VC)をやってて、それをやったよ

ちなみに
・プレイヤーが押すことが出来るのは、押されてないスイッチだけ
・スイッチを押すと、上下左右の4つのスイッチの状態が反転する
・全部押した状態にしたら勝ち               ~~~~~



274 :デフォルトの名無しさん:2009/03/01(日) 08:52:47
>>273
反転するのか。てっきり押したものはひっくり返らないのかと思って、
それならほぼ自明な解があるかなと思ってた。

275 :デフォルトの名無しさん:2009/03/01(日) 09:15:05
>>271
>>273 のルールなら,多項式時間で解けるね.方針は次の (1), (2) による.

(1)「押されているスイッチも押せる」というように問題を緩和して解く.
これを解くと,最終的に押すべきスイッチの一覧が得られる.

(2) 押すべきスイッチ一覧を適当な順番で押していく.


(1) はライツアウトの変種なので,連立方程式を立てて解けばいい.
詳しくは「ライツアウト 連立方程式」あたりで検索すれば分かる.

(2) は,押し方によっては手詰まりになるのが怖いのだけれど、
実はどんな順番で押していっても,手詰まりにならないことが証明できる.
よって (1) で作った一覧から押せるものを見つけて押す,を繰り返せばよい.

276 :デフォルトの名無しさん:2009/03/01(日) 09:21:42
解を知っているなら簡単なんだけどな
解を知っていなければn×nの一時方程式(ただし変数は全部bool型)になるかな?


踏まれた状態:
1 0 0
0 0 1
0 0 0
を考えると,床の状態は
1 1 1
1 1 1
0 0 1
ってなるから…わからん

アルゴ君たのんだ

277 :デフォルトの名無しさん:2009/03/01(日) 10:03:26
>>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 個の条件式を適当な方法で解けばよい.

278 :デフォルトの名無しさん:2009/03/01(日) 10:26:03
うひー
私をもっと踏みつけて〜

279 :268:2009/03/01(日) 11:24:23
>>272-277
ありがとう。とりあえず、やってみる

280 :デフォルトの名無しさん:2009/03/01(日) 22:50:24
25x25正方行列の対角化問題に帰着するのか
アルゴ君のコメントが欲しいな

281 :デフォルトの名無しさん:2009/03/01(日) 23:00:16
アルゴ君じゃないけど、mod 2でしかないから行列(というか実数量)でやるほどでもない。
そのアルゴのルールだとグラフ理論が一番効果あるんじゃないか?

282 :268:2009/03/01(日) 23:20:37
ライツアウトで解けた。
順番は関係ないらしい。

後は連立方程式を解くアルゴリズムを実装するだけ
みんなサンクス

283 :デフォルトの名無しさん:2009/03/02(月) 05:40:32
>>280
対角化ではなく,連立一次方程式だよ.
mod 2の計算だと対角化問題は解けない.

>>281
mod 2の計算をわざわざ実数ではやらないよ.
グラフ理論って,具体的には何?

284 :92他 ◆DRdCZDy4PY :2009/03/02(月) 05:47:14
驚異のライツアウト解法ロジックいまごろ知った
そういうことか

285 :デフォルトの名無しさん:2009/03/02(月) 07:06:24
>>281 はアルゴ君にしか見えない

286 :デフォルトの名無しさん:2009/03/02(月) 22:57:43
>>284
7年前の記事ww
俺小学生www

287 :デフォルトの名無しさん:2009/03/03(火) 17:32:53
>>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 上での連立方程式だから単純だがな、
こういう場合に実数を持ち出さなくて済むということは知っておくといいぞ

288 :デフォルトの名無しさん:2009/03/09(月) 20:24:16
データ構造・アルゴリズムに関する問題なのですが。どなたかお手伝いお願いします
スレチなら申し訳ないですが誘導お願いします。長すぎるみたいなので分割投下させていただきます

----------------------------------------------------------------------------------
以下の事柄に注意し各問題に答えなさい
・与えられた文字列等のデータについては問題の指示に合うように事前処理が必要な場合がある。
・木等を表記する際に、 ダミー接点であるheadとz(外部接点)は表記する必要はない。
・同一キーについては後から挿入される方を大きいものとして扱う。

1.文字列「ASORTINGBYPOLYPHASEMERGINGEXAMPLE」に対し、3ウェイ併合を用いたポリフェーズ法による外部整列を行うこととする。
 このとき、整列が始まる直前のランが配置されたテープの姿を現しなさい

条件)・主記憶の容量は文字3文字分とする。
   ・使用できる磁気テープは4本。

2.文字列「BINARYSEARCHQUESTION」について
 1)「H」を2分探索で行うとキーの比較は何回必要か。
 2)内装探索を行った場合はどうか。

 ただし、比較対象文字が確定しない(文字を示すポインタアドレスが整数でない)場合は
 ポインタアドレスを切り上げ後方の文字を比較対照とせよ。

ソートしたもの「AABCEEHIINNOPQRSSTUY」

3.文字列「BINARYTREESEARCH」について赤黒木を作成せよ。なお、黒リンクは1本線、赤リンクは2重線で表記せよ。


289 :デフォルトの名無しさん:2009/03/09(月) 20:27:15
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つずつ 格納できるものとする
----------------------------------------------------------------------------------
連投・長文お目汚し本当に失礼しました

290 :デフォルトの名無しさん:2009/03/11(水) 05:49:36
ワロタ
少しは自分で考えろ



291 :デフォルトの名無しさん:2009/03/18(水) 01:54:58
>>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通りの解がある。

292 :デフォルトの名無しさん:2009/03/18(水) 03:08:41
ORじゃなくてXORだった

293 :デフォルトの名無しさん:2009/03/19(木) 20:46:38
http://tvde.web.infoseek.co.jp/cgi-bin/jlab-dat/s/387477.jpg

294 :デフォルトの名無しさん:2009/03/20(金) 08:39:04
アッカーマン関数というネタか?

92 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)