計算アルゴリズム【Ⅱ】

[表示 : 全て最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 2chのread.cgiへ]
Update time : 01/02 08:46 / Filesize : 251 KB / Number-of Response : 871
[このスレッドの書き込みを削除する]
[＋板最近立ったスレ＆熱いスレ一覧 : ＋板最近立ったスレ／記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

計算アルゴリズム【Ⅱ】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ]: 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉

>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。

前スレ↓
pc8.2ch.net/test/read.cgi/tech/1090227743/
178 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 19:46:30 ]: 最小二乗フィッティングだね．
理論的には，s_1, ..., s_n をパラメータとする関数 f(x; s_1, ..., s_n) を
データ列 (x_1, y_1), ..., (x_N, y_N) にフィッティングするときは誤差の二乗和
φ(s_1, ..., s_n) = Σ(f(x_i; s_1, ..., s_n) - y_i)^2
を最小化する s_1, ..., s_n を求めてやればいい．

で，それは結構難しくて，凸関数とか条件付かないと最良解が出る保証は無い．
ある程度の解でいいなら，「勾配法 + アニーリング」くらいで，それなりに求まってくれるはず．
179 名前：デフォルトの名無しさん [2005/12/05(月) 19:50:09 ]: 画像調整のガンマをスクロールバーで実装したいのですが、
イマイチ正確な定義が分かりません。

それか、組み込めるライブラリどこかに落ちてないでしょうか？
180 名前：174 mailto:age [2005/12/05(月) 20:15:07 ]: >>178
詳しいレスありがとうございます。
今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が
最小になる(p, q)の組を解としています。

勾配法、アニーリングを調べてみて、検討してみます。
181 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 20:17:32 ]: >>179
質問の意味がわからないけど多分スレ違い。

・言語と開発ツールは何を使ってるのか
・具体的にやりたいことは何か
・今自分は何がわからないのか

この三点をはっきりさせて、適切なスレに行って聞いてください。
182 名前：デフォルトの名無しさん [2005/12/05(月) 21:10:48 ]: あるデータ列に
Y = (A(X^3)+B(X^2))/(CX+D)
の最小自乗法を適応するばあい、
残差の２乗和 S に対して
A, B, C, Dそれぞれで偏微分したもの = 0
の連立方程式を解いて、
A = Σを含む式
B = ...
C = ...
D = ...
とすれば良いのでしょうか？

簡単な式の最小自乗法しか使っていなかったので、
そのまま適応して良いものかどうかが分かりません。
お願いします。
183 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 21:18:39 ]: >>182
OK．

ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし，解けたとしても解は一般に複数存在するので
出した解が本当に良いフィッティングになってるかは十分議論する必要がある．
184 名前：182 [2005/12/05(月) 21:30:11 ]: >>183
ありがとうございます。勉強になります。
185 名前：アルゴリズム mailto:fh [2005/12/06(火) 10:20:52 ]: N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい

年齢が３０歳以下の人の、体重と身長の平均値を計算し表示する
186 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 10:59:37 ]: select average(weight), average(height) from DATA where (age <= 30);
187 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 12:50:40 ]: >185
スレタイくらい嫁。
くだ質スレか宿題スレ池や。
188 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 20:36:58 ]: >177
エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。

ところでexp（）の形になると判ってるなら、logを取ったらどうなる？
189 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 21:51:46 ]: プチ統計学講座だなｗ
190 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:09:54 ]: >>188
ヒント：Windowsとは限らない
191 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:28:03 ]: ひんと：Excel以外にも統計処理できるソフトはあるし、そもそもMacでもExcelは動く。
192 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:34:45 ]: >>190-191
ヒント：そもそも汎用機とも限らない　例：宇宙計算用スパコン

だからこそのアルゴリズムスレだろ？
193 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 23:14:51 ]: だからlogとったらどうなるかと聞いてみたんだけど
194 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 23:30:44 ]: だから前半にだけ突っこんだんだけど
195 名前：デフォルトの名無しさん mailto:sage [2005/12/07(水) 19:22:24 ]: まぁまぁ、次のネタを待ちましょう
196 名前：デフォルトの名無しさん [2005/12/07(水) 19:55:37 ]: 上にも最小自乗法の話題が出ていますが･･･

y=(A(x^3)+B(x))/(C(x^2)+D)
の関数に最小自乗法を適応することは出来ますか？
残差の２乗和が最小になる(A,B,C,D)を見つけるわけですが、
例えばCで偏微分して=0となるCは、単なる極地のCであり、
それが極小かつ最小となるわけではありませんよね？
197 名前：196 [2005/12/07(水) 19:57:51 ]: あれ！？
よく見たら>>182とまったく同じ式でした･･･。
当方、学生ではないので課題とかでもないのですが。
同じ書物を読んでいるのかしら。

>>183を参考にします。
無視してください。
198 名前：デフォルトの名無しさん mailto:sage [2005/12/07(水) 20:29:05 ]: フローチャートしか知らない
199 名前：デフォルトの名無しさん [2005/12/08(木) 10:14:07 ]: 二次元配列と、
その中の３つの点で定義される三角形があって、
ある点がその中か外か判定するアルゴリズム教えて下さい。
200 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 11:58:18 ]: >>199
(0,0), (0,2), (2,0) という要素数3個の2次元配列が与えられた場合、
(1,1) という点がその三角形の中にあるかどうかということだよな？

1)与えられた3点が三角形を構成するかどうかを吟味。
2)その3点から各々2点を取り出し(3通り)、2点を通る直線の式を求める。
3)その3本について、直線で座標平面を分割した場合、残りの頂点を含む領域を不等式(3通り)であらわす。
4)中か外かを判定したい点について、その3つの不等式を同時に満たせば中、そうでなければ外。
201 名前：デフォルトの名無しさん [2005/12/08(木) 12:26:41 ]: そのまんまじゃん
202 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 13:04:30 ]: ナップザックを背負ったバックパッカー*がいるとする。ナップザックの中は、
できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、
どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが
最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ
*リュックサックに全ての荷物を入れて旅行する人のこと。
問1
0/1 ナップザック問題とは何か？
問2
全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん
な問題となるのだろうか？
問3
アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの
か？
問4
ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか？参考
書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか
記述せよ．
203 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 15:35:02 ]: >>202
ここは君が来るべきスレでは無いよ。
204 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 15:59:27 ]: >>203
いいじゃんべつに。
お前の個人的な感情は出さなくてもいいよ。
そんなもの読んでいる人間には全く価値がないから。
文句があるならどのスレにいけ、ぐらいは言えよ。
あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。
205 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 18:15:33 ]: >>204
つまんないﾈﾀ書くのも自由だし
それを批判するのも自由。
206 名前：デフォルトの名無しさん [2005/12/08(木) 18:37:18 ]: 座標３つ（どれがどの位置か不明）から、３角形の面積を計算する方法はありますか？
207 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 18:40:49 ]: >>205
自重しろよ。
自由ではないんだよ？あまりひどいとアク禁だ。
208 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 19:52:21 ]: >>206
3点から辺の長さ求めてHeronの公式、とか。
209 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:01:43 ]: 三点のベクトルが v1, v2, v3 のとき
[v1-v2, v3-v2]/2 の絶対値が面積になるね。

[x,y] は x と y の外積ね。
210 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:02:07 ]: >>206
ある点を原点に移動させるように全体を並行移動させて、
(0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを
使った方が簡単かも。

３点が三角形が作られない位置に無いことを確かめてからね。
211 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:03:50 ]: 実は
（>>182の式）≠（>>196の式）
である件について
212 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:55:54 ]: >>206
www.tensyo.com/urame/prog/linealgo.htm
の多角形の面積でやれば？
213 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 23:07:36 ]: >>199
>>99,>>107-108

>>204
>>187

てか、質問する前にスレ内くらいは読もうぜ？
214 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 18:24:45 ]: >>206
でも、3点とも座標がわかってて位置不明ってどゆこと？
215 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 19:24:25 ]: >214
「固定座標じゃない」って意味だろ。
確かに意味は解らないが、気持ちは伝わってきた。
216 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:30:04 ]: ヘロンの公式のことをたずねているの？
217 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:39:02 ]: 辺の長さが与えられてるわけじゃなく、頂点座標だから
ヘロンの公式をわざわざ使うより
素直に台形公式による閉曲線積分
218 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:56:04 ]: >>217
頂点座標？閉曲線積分？言葉はちゃんと使おうぜ
219 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 01:18:24 ]: >>214
任意の三点ってことだろ。
220 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 11:53:04 ]: 三角形なんだから、3点を P, Q, R として、
2つのベクトル a ＝ PQ、b ＝ PR を定義。
(1/2) |a × b|
ただし、×は3次元ベクトルの外積、|| はベクトルの絶対値。

っつーか、ぐぐれ。
homepage2.nifty.com/PAF00305/math/triangle/node3.html
221 名前：BASIC mailto:fh [2005/12/14(水) 15:57:56 ]: 次のプログラムをＢＡＳＩＣで作成しなさい

データを１件ずつ、ユーザ定義関数を利用して
「公共料金」を計算させることにします
＜水道料金の計算＞
基本料金：1250円定量制料金単価は
・使用量が10立方米以下であれば80円／立方米
・〃 10立方米超20立方米以下であれば185円／立方米
・〃 20立方米超50立方米以下であれば205円／立方米
・〃 50立方米超100立方米以下であれば240円／立方米
・〃 100立方米超200立方米以下であれば275円／立方米
・〃 200立方米超であれば310円／立方米
（計算例）
使用量が8立方米であれば、1250＋8×80
使用量が15立方米であれば、1250＋10×80＋(15－10)×185
＝2050＋(15－10)×185
使用量が40立方米であれば、1250＋10×80＋10×185＋(40－20)×205
＝3900＋(40－20)×205
使用量が75立方米であれば、1250＋10×80＋10×185＋30×205＋
(75－50)×240＝10050＋(75－50)×240
使用量が120立方米であれば、1250＋10×80＋10×185＋30×205
＋50×240＋(120－100)×275＝22050＋(120－100)×275
使用量が230立方米であれば、1250＋10×80＋10×185＋30×205
＋50×240 ＋100×275＋(230－200)×310 ＝49550＋(230－200)×310
222 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 15:58:42 ]: 作成しなさい、だってさ↓
223 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 16:01:00 ]: 　　　　　　　　　　　｜　　　　　∧＿∧
　　　　　　　　　　　｜.　　　　(･ω･` )ｽﾙｰ
　　　　　　　　　　　｜ｽｽ…　/J　　 J
　　　　　　　　　　　↓　　　,,, し―-J
224 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 16:51:10 ]: アルゴリズムじゃねえな
225 名前：デフォルトの名無しさん mailto:sage [2005/12/14(水) 19:15:46 ]: アゴリズムだな
226 名前：デフォルトの名無しさん mailto:sage [2005/12/15(木) 00:36:36 ]: アルゴリズムじゃねえって！
227 名前：デフォルトの名無しさん mailto:sage [2005/12/15(木) 04:40:03 ]: アルゴリズム体操！アルゴリズム体操！
228 名前：デフォルトの名無しさん mailto:sage [2005/12/16(金) 15:42:28 ]: 立方米って一般的なのか。
m^3と書かないの。
229 名前：デフォルトの名無しさん mailto:sage [2005/12/16(金) 15:51:32 ]: >>228
メートル=米、だからね。
他にも糎とか粍とか。
でも、普通は立方米と書かずに立米(りゅうべい)と書く希ガス。
#平米は割と一般的でしょ。
230 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 12:32:02 ]: 口頭ではよく「へーべー」と言うな。
俺の父親が。
231 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 12:34:10 ]: なんでメートルが米なの？？その由来は？
232 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 12:58:32 ]: 亜米利加　と同じじゃないの？　メの元の漢字だと思ってたけど
ttp://www.fudemojiya.com/syo/katakana.htm
によると　女　らしい
233 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 13:05:23 ]: 明治時代か江戸末期に「メートル(或いはメーター)」という音に似ているから当てたんじゃないの?
他にもグラムやインチなどにも当てられた漢字があることだし。
234 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 19:27:50 ]: ttp://freett.com/ToshiN/kanji/kanji02.html
発案した人も途中からヤケクソになっていったのだと推測
235 名前：デフォルトの名無しさん mailto:sage [2005/12/17(土) 22:42:29 ]: >>234
そこまでして漢字にせんでもええやん…とおもた。
236 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 03:23:45 ]: 当時ハ送リ仮名ガ片仮名デアッタタメ
外来語ヲ片仮名ニ割リ当テルトイウ
発想ハ無カッタンダロウナ
237 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:08:19 ]: 質問なのですが、例えば、
1、２、３、４、５、４０、５０、６０、７０　といった代表値である数字があるとします。

で、例えばXがその代表値のどれに一番近いかを求めるとき
すべてを探索すれば答えはわかると思いますが、できるだけ高速に
求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、

例えばXが6だとするとまず、5が一番近いことがわかります
これをどうやって木にしたらいいのかがわかりません。
また１，２、３・・・・といっていましたが
（X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう？
一致するのを探すのではなく一番近いものを探すので苦労しています。
近さの判定としてはユークリッド距離を用います。
どうぞよろしくお願いいたします
238 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:13:08 ]: 代表値の数列が整列されている前提ならバイナリサーチでいいのでは？
239 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:32:56 ]: >>238
ありがとうございます。
バイナリサーチですと完全に一致する場合は問題ありませんが
完全に一致せず一番近いものを選択するときに問題がおきます

237の例で6に一番近いものをバイナリサーチで探そうとすると
40になると思われます
240 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:46:58 ]: バイナリサーチで最終的に 40 がヒットするわけだけど、
この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。
あとはどちらに近いかを計算するだけじゃないのかな。
241 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:54:28 ]: >239
最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。
n次の場合は、a=f(X,Y,...)で、aの値でソート。
242 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 05:01:13 ]: >>240
>>241
ありがとうございます。
ｎ次の場合はうまくいかないように感じるのですが
できれば具体例を出していただけないでしょうか？
241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか
しらべて次はY、Z・・・というふうなことだと感じているのですが
例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで
Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので
あまりうまくいかなようなきがします。
間違っていたらすみません
243 名前：241 mailto:sage [2005/12/18(日) 05:37:33 ]: >242
スマソ、完全に寝ぼけてた。
1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね？
244 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 05:40:16 ]: >>243
ありがとうございます。

総当りですか・・・それですと時間がかかるので
何かいい方法がないかなと思いまして
245 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 07:16:28 ]: >>241
２次元（平面）ならボロノイ図・近傍で似たような問題がある
３次元以上だとできるかどうか知らない

総当りにしたら
246 名前：245 mailto:sage [2005/12/18(日) 07:17:31 ]: >>245 の >>241 は >>237 の間違いですｽﾏｿ
247 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 07:55:24 ]: >>245
ありがとうございます。
ボロノイ図については知っていまして、三次元でも可能のようです。
ですが、これをどう木にすればいいのかよくわからなかったもので
何かいい方法があればと思って相談してみました、。
248 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 09:03:12 ]: >>237
空間データベースって分野のお話だね．

望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな．
空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に
点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで，
その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)．

ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく：
www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html
vision.unige.ch/~moennen/publi/moennen_tech0505.pdf
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley
249 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:00:28 ]: >>248
ありがとうございます
望んだ形でデータを持っていても大丈夫です。
K－ｄ　tree　についてなのですが、これでは一番近い代表値に近似することはできないと
考えられます。
例えば
www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html
のｋ－ｄ　ｔｒｅｅ　のところの図で説明しますと
代表地がＰと考えると、Ｐ４とＰ５の線の中に点があるのですがＰ９に
一番近い点（一番近い代表地に近似したい点）があったとすると
これはＰ４かＰ５に近似されることになります。
実際はＰ９に一番近いのにこれには近似されないとおいうことです
木を作る際にＰ７からでなくＰ６からはじめたとしても同様の問題はおきると考えられます
しかしＲ－ｔｒｅｅというのは使えそうな気がします
ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが
なんとかがんばってみます
ありがとうございました
250 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:04:36 ]: www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html
のＲ－ｔｒｅｅを読んでみましたがこれでも正確に一番近い代表地に
近似されないように感じます。
うーんどうしよう
251 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:05:18 ]: 一番近い点は一回では求まらないだろう。
　求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。

　たとえば2次元なら　x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで
　　矩形で絞り込めばいいでしょ
252 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:07:59 ]: あと、この問題は、最悪の場合は、全数検索が必要になる。

たとえば円周上に点が並んでいて、中心に近似しようとした場合など
253 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:17:52 ]: >>251
>>252
ありがとうございます。
自分の中で何か新しいアイデアが浮かんできそうな気がします
が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです
どうかおねがいします
254 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:25:28 ]: データ構造として、各母点に、母点を中心に、一番遠いボロノイ点までの距離半径の円内にある
母点までのリンクを距離順に並べて持たせておいて
最初に検索した母点までの距離内にあるリンクだけ全検索する
検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする
255 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:35:34 ]: >>254
ありがとうございます
私の理解力不足のためわからなかったです　すいませんが
もう少し簡単な説明をしていただけないでしょうか　どうかお願いします
256 名前：248 mailto:sage [2005/12/18(日) 10:53:05 ]: >>249
二つ目に挙げたテクニカルレポートも読んでね．ちゃんとそっちに作った木から kNN を絞り込む方法について
コメントが入ってるから．参考文献にもそれっぽいのが沢山あるので子引き，孫引きしましょう．
257 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 09:08:38 ]: 長いですが、NP完全について質問です。
アルゴリズムの本に
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか？
"=Which of the diagrams do not contradict the current state of our knowledge
about the complexity classes P, NP, and NPC (NP-complete problems)"」
という質問があってヒントに
「これらのうちの二つのみが現在の私たちの知識と矛盾している
"=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。
「私たちの知識」とはその本に載っている
「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ
"=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」
っぽいです。

図は五つあって、そのうち
aはP=NP=NPCで、bはNPCがP=NPの部分集合になっており、dはPとNPCが重なった形でNPの部分集合になっており、
これらは明らかに矛盾しているので除外です。
eは↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。

ttp://www.jyi.org/volumes/volume10/issue2/articles/widjaja.html

で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが
NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか？)
これも矛盾してますよね？PでもNP完全でもないNP問題がないといけないんですから。
そうだとしたらこの本の間違いなんですが…。
ここの賢い人、どうか答えてください。せめてヒントだけでも…。
258 名前：257 mailto:ageで [2005/12/19(月) 09:19:37 ]: あまりの必死さに図を描いてしまいます。m(__)m

c.　　　　　　　　ＮＰ
┌─────┬─────┐
│　　　　　　　│　　　　　　　　│
│　　　Ｐ　　　│　　ＮＰＣ　　　│
│　　　　　　　│　　　　　　　　│
└─────┴─────┘

てな感じです。
259 名前：257 mailto:sage [2005/12/19(月) 09:23:48 ]: 度々すみません。訳し間違えました。正しくは
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か？」
と
「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」
です。もう後で逝ってくるつもりです。m(__)m
260 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 10:19:49 ]: >>188
すみません
261 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 13:34:18 ]: >>257
「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」
であって、「P≠NP」とは限らない。
262 名前：257 [2005/12/20(火) 12:17:51 ]: >>261
ありがとうございます。
なるほど、「P≠NP」とは限りませんよね。
もしそうだとすれば選択肢は「P＝NP」しかない訳で
その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」
と解釈してよいのでしょうか？

友達の一人は「『P＝NP』は『現在の私たちの知識』に矛盾していないか？
図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。
cがP=NPとするなら矛盾していると判断するべきだろう？」と問いかけてきました。うーむ。

すみません、自分、人より脳が少し足りないようです。
また説明お願いします。m(__)m
263 名前：デフォルトの名無しさん mailto:sage [2005/12/20(火) 14:31:12 ]: >>262
現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。
P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で
とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、
多項式時間で解くことの出来ない問題があることを証明できていない現在、
P=NPは矛盾しているとはいえない。
264 名前：257 mailto:sage [2005/12/21(水) 12:01:14 ]: >>263
なるほど、ようやく分かりました。
すべてのNP問題が(近似解とかではなく)
多項式時間で解けるようになったら面白いでしょうね。
天寿を全うするまでに見たいものです。
ありがとうございました！
265 名前：デフォルトの名無しさん mailto:age [2006/01/09(月) 00:12:14 ]: age
266 名前：BASIC mailto:fh [2006/01/09(月) 16:12:52 ]: N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい
体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する
267 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:34:00 ]: 宿題は自分でやれ
268 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:54:08 ]: BASICなんて記憶の彼方だな
269 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 18:15:01 ]: 何ベーシックかは指定していないな。
VBとかでもいいとすれば随分アレだ
270 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 19:08:23 ]: >>266
www.sagami.ne.jp/tadaka/99Basic/
271 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 03:29:11 ]: ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？
(n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです

もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！
272 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 06:49:10 ]: Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない．
定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし．

O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？
273 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 10:57:45 ]: >271
LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、
次回以降は演算を省くってのはどうだろう？
辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。
274 名前：271 mailto:sage [2006/01/12(木) 12:31:26 ]: >>272-273
早いレスどうもです！

>>272
やはりO(nm)回は「本質的に」避けられないわけですよねー・・・
微分の差分近似をループでnm回やるつまらない実装なんで、
工夫できないかなと思った次第だったのですが。
ちなみに問題は非線形関数の最小値探査みたいな感じです

>>273
んー、いいアイディアなんですが今回は
適用できないような気がします、ゴメンナサイ
ただ、そのうち他の問題で使えそうな気がするんで、
そのネタはもらって覚えておきます！　ありがとう！
275 名前：デフォルトの名無しさん mailto:sage [2006/01/14(土) 00:48:34 ]: >>274
最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような
276 名前：デフォルトの名無しさん [2006/01/31(火) 17:55:55 ]: 最小二乗法のライブラリきぼんゅ。
277 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 03:14:47 ]: >>276
ライブラリも何も、大した計算じゃないじゃん。
278 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 12:32:21 ]: >>277
世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある？
279 名前：276 [2006/02/01(水) 12:44:24 ]: 最小二乗法おしえて欲しいぉ。
280 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 13:38:16 ]: 残差平方和が最小になるようにパラメータを決定するのです
このスレでも簡単な例がいくつか
>>178
>>182
>>196

非線形になってくるとちょっとめんどい
en.wikipedia.org/wiki/Gauss-Newton_algorithm
en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
ここら辺を参考に
281 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 02:20:31 ]: >>278
FFTになると、ライブラリが欲しい程度には複雑だと思う。
282 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 08:51:05 ]: >>281
どれだけある？という問いにＦＦＴ１個かよ。
283 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 09:25:21 ]: >>282
世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。
284 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 13:43:21 ]: 行列計算もだいたい書く気がしないな．条件数が悪い場合とか考え出すと相当面倒くさい．
285 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 14:58:57 ]: あとは圧縮＆展開と多倍長演算あたりかね？　汎用的なのは。
各分野毎にはいろいろとあるだろうけど。
画像エフェクト、サウンドエフェクト、3D系演算とか。
286 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 15:52:22 ]: >>281
難しくはないが複雑ではあるよな。
287 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 22:26:58 ]: 各種関数なんかは、大概簡単なことをやっていても、実装は面倒だなぁ。
288 名前：デフォルトの名無しさん mailto:sage [2006/02/05(日) 09:27:32 ]: 最小二乗法は
円に適用するだけでも、厄介だし、
直線に適用しようとしたって、実はけっこう難しいよ。
たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。

　残差って何って所から取り掛からないとね。

そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。
数値解で求める事になるだろうな
289 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 07:09:38 ]: >>288
ただの偏微分でしか説明しないのって，相当ひどい学校だと思う
290 名前：276 [2006/02/06(月) 10:04:37 ]: >>288
じゃ、何を使うのさ？？？？？

>>289
詳しく！！！！！
291 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 14:14:46 ]: >>288
最小二乗法はロバストでないのでそのあたりは考慮しないと。
例えば、y=x上に完全に点が並んでいる状態で、
たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。
292 名前：276 [2006/02/06(月) 14:22:51 ]: 今回の開発では点の数に関しては、決めウチできます。
293 名前：288 mailto:sage [2006/02/07(火) 06:30:36 ]: >>290
だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ
直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う
数表上なら結果の誤差を最小にしたいし
2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある
294 名前：デフォルトの名無しさん [2006/02/09(木) 11:57:07 ]: 最小2乗法ｱｹﾞ
295 名前：sage mailto:sage [2006/02/09(木) 21:45:42 ]: sage
296 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 17:31:27 ]: n個の要素の2番目に小さい要素は最悪n+logn－2回の比較で求められることを証明しなさい。

順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。
どなかか説明してもらえないでしょうか？よろしくお願いします。
高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。
297 名前：デフォルトの名無しさん [2006/02/11(土) 18:07:41 ]: 　／￣￣￣￣＼
／　　　　 ●　　 ●　
|Y　　Y　　　　　　　　＼
| |　　 | 　　　　　　　 ▼　| ﾊﾟｸｯ
| ＼／　　　＿＿＿＿人__|
|　　　　　　|∨∨∨∨∨　←296
＼　　　　　＼∧∧　　　）
　｜｜　|＼　￣￣＼＼＼
　｜｜　|　　￣￣￣しし/
　（_＿）＿）
298 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:33:39 ]: 最悪 n - 1じゃないか? 何番目でも最悪 n - 1回でいけそうだ。
今適当に考えただけだから間違ってるかもしれないけど。
299 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:40:59 ]: 違った、最悪 n回か。
300 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:45:05 ]: >>298
いや、漏れが覚えている限りでは違うと思われ。
MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず
院試にでてたかも。
301 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:57:23 ]: >>300
やっぱり違ってた。考え直したら、
nが偶数なら (3/2)*n - 2,
奇数なら (3/2)*n - 3/2 回だった。
302 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 20:58:20 ]: >>296
ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。
あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。
303 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 00:24:16 ]: 証明になってないｗ
304 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 03:01:20 ]: >>296
完全二分木でトーナメントを考えよう。
一番小さい要素を見つけるのにn-1回の比較が必要。
二番目に小さい要素は一番小さい要素の対戦相手のどれか。
木の高さはceil(log n)で木の一番上には対戦相手はいないから、
二番目に小さい要素の候補たりえるものはceil(log n)-1個
この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。
したがって比較回数は、
(n-1)+ceil(log n)-2<n+logn-2
ただし、ceil(x)はxの小数点以下切り上げの関数
305 名前：デフォルトの名無しさん mailto:sage [2006/02/13(月) 00:39:26 ]: >>304
なるほど。
それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど
どうなんだろう。
306 名前：デフォルトの名無しさん mailto:sage [2006/02/13(月) 06:11:40 ]: ２分木にする必要性が感じられないってかなってないｗ
307 名前：デフォルトの名無しさん mailto:sage [2006/02/14(火) 10:30:15 ]: >>305
実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは
結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。
308 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 09:33:06 ]: ３２ビットの符号無整数型で３２個のビットのうち
N個をランダムに選んで１にするアルゴリズム。
（残りの３２－N個は０）
賢い人教えて。
309 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 11:33:45 ]: >>308
そのサイズの乱数を一個生成するだけじゃいかんの？ C なら rand() とかで。

それとも乱数生成のアルゴリズム自体を聞いてるの？
310 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:12:40 ]: たぶん
１）組み合わせの数の計算方法が判らない
２）乱数と、その全部の組み合わせを対応させる方法が判らない

のだろうと思うんだけどね
311 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:28:33 ]: 1U << (rand() & 31)
とか、そういうことではないの？
312 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:35:07 ]: >>311
rand って完全にランダムじゃなくて、
下位ビットほど短い周期性持ってるから、
rand() & 31 はあんまりよくない。
(rand() >> 16) & 31 とか、何ビットかシフトするの推奨。
313 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:38:20 ]: 分かってて書いてたつもりだけど…アルゴリズムの質問だし。
random()でもMTでも好きなの使えばいいんじゃない？
314 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:41:56 ]: >>313
まあそうだけどね。

>>308 がそんな判断できると思えなかったんで、一応補足のつもり。
315 名前：308 mailto:sage [2006/02/27(月) 13:09:41 ]: MTとかで生成された乱数の立っているビットの数は
１６本を中心にした正規分布になってると思うんだけど、
必ずN本になるようにしたい。
３本とか３０本とかってのはたまにしか発生しないし。
N回ループで一度使った数は記憶させとくとかっていう
愚直なのは思いついたんだけど遅そうなので聞いてみた。
316 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 15:31:21 ]: 32個の数字から N個取り出して順不同というのと　問題は同じでしょ
317 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 20:50:08 ]: >>316
ですね。
1～32の間で離散一様乱数発生させたものをa_0、
1～31の間の乱数をa_1、1～30の間をa_2として、
初期値は0で左からa_0番目のビットを1にする。
以降左からa_k番目の0のビットを1にする。
　　　　　　　　　　　　　~~
318 名前：308 mailto:sage [2006/02/28(火) 09:54:13 ]: >>317
今はそれでやってます。
みなさん聞いてくれてありがとう。
319 名前：308 mailto:sage [2006/02/28(火) 09:58:33 ]: あ、ついでに言っとくとNが17以上の場合は32-N個のビットを立てて反転してる。
連投ごめん。
320 名前：308 mailto:sage [2006/03/01(水) 16:40:57 ]: やっぱりもっと速いのないかな。
321 名前：デフォルトの名無しさん mailto:sage [2006/03/01(水) 17:19:36 ]: >>320
これ以上議論するなら，「速い」をきっちり定義してもらわないと．

特に乱数生成のコスト，各ビットを参照するコストなどが無いと，
どっちが速いかなんて比較できんよ．
322 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 11:59:32 ]: もっと早い方法は、全部の組み合わせのテーブルを作っておいて
それの配列番号を乱数で選ぶ事だね
323 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 12:53:16 ]: >>322
2^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB
何を使って動かすつもり？
324 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 16:39:38 ]: >>317
それは、順番を考慮した場合のアルゴリズムだから違うようだけど
結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか

>>323
Nを固定すれば　最大の組合せ数は N=16の時でその1/4程度の容量だから最近のPCなら入るんじゃないの？

組み合わせの数ってどの程度だろ？
32!/N!/2^N では大きすぎるな
325 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 16:43:14 ]: たとえば32個中3個が１の組み合わせを F(32,3) のように書くと

先頭ビットが0 なら残りは F(31,3)
先頭ビットが1 なら残りは F(31,2)

という事で
F(N,M)=F(N-1,M)+F(N-1,M-1)
326 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 17:23:15 ]: >>324,325 高校数学の教科書読み直したら？
ttp://ja.wikibooks.org/wiki/%E9%AB%98%E7%AD%89%E5%AD%A6%E6%A0%A1%E6%95%B0%E5%AD%A6A_%E5%A0%B4%E5%90%88%E3%81%AE%E6%95%B0%E3%81%A8%E7%A2%BA%E7%8E%87#.E7.B5.84.E3.81.BF.E5.90.88.E3.82.8F.E3.81.9B
327 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 18:34:31 ]: という事は 32 C 16
www.google.co.jp/search?q=32!/(16!*16!)
601 080 390
って事か

Σ M C n =2^M って事になるんだな
328 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 18:39:51 ]: で 32個中16個の組み合わせ　は　32!/(16!*16!)
なのに >>317の方法は　順列　で　32!/16!　という事で、16! の重複があるから、なんか重そうに見えるという事？
329 名前：デフォルトの名無しさん [2006/03/03(金) 07:29:43 ]: 配列のソートではなく、上位2者と下位2者を高速にシークするアルゴリズムを教えて＞＜
330 名前：デフォルトの名無しさん mailto:sage [2006/03/03(金) 07:50:10 ]: var max1,max2 min1,min2;

max1:=data[0];
max2:=data[1];

if max2> max1 then swap(max1,max2);
min2:=max1;
min1:=max2;

for i:=low(data)+2 to High(data) do begin
　 if data[i] > max2 then begin
　　if data[i] > max1 then max1:=data[i] else max2:=data[i];
　 end;

　 if data[i] < min2 then begin
　　if data[i] < min1 then min1:=data[i] else min2:=data[i];
　 end;
end;

こんな感じでは？
331 名前：デフォルトの名無しさん mailto:sage [2006/04/18(火) 07:42:35 ]: いわゆる○×。ただし、ちょっと特殊。
ban(0) ban(1) ban(2)
ban(3) ban(4) ban(5)
ban(6) ban(7) ban(8) //盤面　位置関係はこんな感じ
turn //ターン数　最初は1

プレイヤーＡのターン開始
↓
Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号
（Ａは１、Ｂは２とする。）を代入。
↓
turn>6ならば、次のことを行う。
　banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入
↓
banに縦横斜めに自分の番号が並んでいるならば勝利
↓
turnに１を足し、Ａのターンを終了、Ｂのターンになる。

で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。
お願いします。
332 名前：デフォルトの名無しさん mailto:age [2006/04/18(火) 13:54:18 ]: あぶらあげ
333 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 16:23:12 ]: >>331
ゲーム木使って実際に解いてみたら。
EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。
終盤6個そろってからの場合の数は
9*8*7*6*5*4 = 60480
回転と対称で重なるものを除くと
60480/8 = 7560
リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。
自分の手番でダブルリーチをかけられる状態であれば勝ち。
双方最善を尽くしたとき、ループに陥れば引き分け。
334 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 17:08:22 ]: 消してから勝利判定だとダブルリーチにならないんじゃない？
335 名前：デフォルトの名無しさん [2006/05/22(月) 17:26:54 ]: 楕円近似ライブラリなんてありまつか？
336 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 17:37:12 ]: 楕円近似というのは　

１、点列を楕円の一部として近似する事

２、楕円の周長を近似計算する事

どっち？１はとても難しい　円ならまだ方法があるが
337 名前：デフォルトの名無しさん [2006/05/22(月) 17:56:27 ]: ＞１、点列を楕円の一部として近似する事

これをやりたいです。
338 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 18:20:03 ]: 円なら　
ttp://www.tensyo.com/urame/prog/linealgo.htm
ここの円弧推定が良い方法だと思える。

普通は、円との誤差を　ｓ＝√｛（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2｝－ｒ　と置くが
これだと非線形で解かなければならない。

（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2－r^2 とすれば数値解が簡単に求まるというものだ。

楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ
339 名前：AVL木 [2006/05/22(月) 20:52:10 ]: 18,7,35,13,16,10,40,21,22,50,46,3,5　　を
からっぽのAVL木に入れていくとどうなりますか？誰か教えてください。
340 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 21:41:44 ]: 教科書読め
341 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 18:54:44 ]: 繰り返し二乗法のプログラムをご教授お願い出来ますでしょうか？
342 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 20:20:09 ]: デジタル回路の閾値関数を考えたのですが、既知ですか？
f:=x->cos(PI/2*x)^2
f(f(f(x))), x=-0.5..1.5
343 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 01:36:13 ]: >>335
Direct least-squares fitting of ellipses
Andrew W. Fitzgibbon, Maurizio Pilu, and Robert B. Fisher
IEEE Transactions on Pattern Analysis and Machine Intelligence,
21(5), 476--480, May 1999

research.microsoft.com/~awf/ellipse/
research.microsoft.com/~awf/ellipse/ellipse-pami.pdf

一応 Java 実装もあるけどコードがちょっと汚いかも。
344 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:01:36 ]: fla板から来ました以下の解答お願いします。

プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか？
(x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが
具体的にどういった計算をすればいいかご教授願います

ちなみに最小二乗法だと、

＼
／
＼
／

このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・
345 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:26:48 ]: >>344
軌跡が直線に近いってのは、どういうこと?
346 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:37:46 ]: >>344
最小二乗法で相関係数みりゃいいだろ。
347 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 00:13:17 ]: >344
数値を求めたいんだろう？
最後の行が意味不明だぞ
348 名前：344 mailto:sage [2006/07/29(土) 00:16:20 ]: >>345
www.uploda.org/uporg461782.gif
この画像のように、どれだけ直線に近い動きをしたか、ということを
直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。

>>346
相関係数ですか、調べてみます
ありがとうございます
349 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 15:15:39 ]: もしかして、344は「軌跡から最小自乗法で直線を求めて、与えられている直線と比較する」とか考えているのだろうか。

「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの？
350 名前：デフォルトの名無しさん mailto:sage [2006/08/10(木) 08:08:24 ]: あらかじめ引いてある直線が X 軸に合うように回転させて
Σ(Yi^2)/N とか
軌跡の2次モーメントとか
351 名前：デフォルトの名無しさん mailto:sage [2006/09/15(金) 13:37:19 ]: 軌跡に沿って所与の直線との距離を積分すればいいじゃないの。
352 名前：デフォルトの名無しさん mailto:sage [2006/09/16(土) 00:36:41 ]: 随分とまた遅い進行だな
353 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 22:34:05 ]: ベクトルを正規化する式は
float x, y, z;//元のベクトル
float vx, vy, vz;//正規化したベクトル
float s;
s=sqrt(x*x+y*y+z*z);
vx=x/s;
vy=y/s;
vz=z/s;

で求まると思いますが、sqrtを使わずに正規化するにはどうすればいいのでしょうか？
どうしても速度が気になります。
自分でも考えてみましたが分かりませんでした。よろしく御願いします。
354 名前：age mailto:age [2006/10/18(水) 22:38:49 ]: age
355 名前：デフォルトの名無しさん [2006/10/18(水) 23:04:16 ]: f(u0,v0)=
ΣΣf(uk,vl)C(uk-u0)C(vl-v0)
k l

ここで
C(x)= 1-2|x|^2+|x|^3 (0<|x|<1)
4-8|x|+5|x|^2-|x|^3 (1<|x|<2)
0 (2<|x|)

3次補間法の計算式なのですが，どのようにプログラムで書いたら良いのでしょうか?
356 名前：デフォルトの名無しさん [2006/10/19(木) 00:02:01 ]: >>353
>どうしても速度が気になります。
本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。

sqrtを使わなければできないと思いますけど。
本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。
ただし、精度を犠牲にしてのことですけど。

Newton法でのsqrtの近似の場合、ループは高々20回くらいです。（誤差1.0e-15で）

まずは実測です。
357 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 00:08:31 ]: 脳味噌ぶら～んにでも行って速そうなの探してこいよ。
358 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 01:37:21 ]: >353
まず環境晒そうや。
CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。
359 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:20:45 ]: >>356
精度にもよるけどせいぜい３－５回ぐらいじゃなかったか？
20回もまわすか。
360 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:52:10 ]: double sqrt(double x) {
double a = 1.0;
double eps = 1.0E-10; /* 精度 */
while (abs(a * a - x) > 1.0E-10) {
a = 0.5 * (a + x / a);
}
return a;
}
361 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:56:57 ]: >>353
www.google.co.jp/search?q=fast%20sqrt
362 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 12:32:48 ]: >>360
そのコードで３－５回
1.0E-15で9回ってところ
確かに20回もありえるけど、極端な言いぐさは信用されないな。
363 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 13:16:19 ]: >>360
Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。
SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。
364 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 13:44:45 ]: >>355
その計算式のままだと思うけど…
アルゴリズムの入力と出力は理解できてる?
(入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値)
365 名前：デフォルトの名無しさん [2006/10/19(木) 16:36:19 ]: 式は分かってるんですがプログラムにできないんです・・・
366 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 17:01:18 ]: >>365
具体的なコードが欲しいなら
具体的な入力形式を指定した方がいいと思うよ。
(これは大学の宿題か何かですか?)
367 名前：デフォルトの名無しさん [2006/10/19(木) 17:19:03 ]: 初心者なもですいません．大学のC言語の画像処理の宿題です．

#include <stdio.h>
#include <rasterfile.h>
#include <math.h>
#include "bitshift.h"

void Disp_Ras(struct rasterfile ras);
void cercle(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void tri(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void sq(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void satr(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);

int height;
int width;

int main(int argc,char *argv[]){

/*変数宣言*/
int i=0;
int j=0;
int point[2];
struct rasterfile ras;
unsigned char **R,**G,**B;
unsigned char **r,**g,**b;
FILE *fp1,*fp2;

int nt,nn;
double p,q;
double bai;
int tmp_nt,tump_nn;
368 名前：デフォルトの名無しさん [2006/10/19(木) 17:22:41 ]: 続き
printf("倍率を入力");
scanf("%lf",&bai);

/* 入力画像 */
if((fp1 = fopen("hane256.ras","rb")) == NULL){
fprintf(stderr,"can't open file!!\none more check it!!\n");
exit(1);}

/* ヘッダ読み込み */
ras.ras_magic = readtoInt(fp1);
ras.ras_width = readtoInt(fp1);
ras.ras_height = readtoInt(fp1);
ras.ras_depth = readtoInt(fp1);
ras.ras_length = readtoInt(fp1);
ras.ras_type = readtoInt(fp1);
ras.ras_maptype = readtoInt(fp1);
ras.ras_maplength = readtoInt(fp1);
369 名前：デフォルトの名無しさん [2006/10/19(木) 17:23:35 ]: 続き
height =bai*ras.ras_height;
width = bai*ras.ras_width;
height = height - height%4;
width = width - width%4;
/* 出力画像 */
fp2 = fopen("out.ras","wb");

/* ヘッダ書き込み */
writetoInt(fp2,ras.ras_magic);
writetoInt(fp2,width);
writetoInt(fp2,height);
writetoInt(fp2,ras.ras_depth);
writetoInt(fp2,ras.ras_length);
writetoInt(fp2,ras.ras_type);
writetoInt(fp2,ras.ras_maptype);
writetoInt(fp2,ras.ras_maplength);
370 名前：デフォルトの名無しさん [2006/10/19(木) 17:24:06 ]: 続き
/* メモリ確保 */
R = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
G = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
B = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
r = (unsigned char**)calloc(height,sizeof(unsigned char *));
g = (unsigned char**)calloc(height,sizeof(unsigned char *));
b = (unsigned char**)calloc(height,sizeof(unsigned char *));
for(i=0;i<ras.ras_height;i++){
R[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
G[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
B[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
}
for(i=0;i<height;i++){
r[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
g[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
b[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
}
371 名前：デフォルトの名無しさん [2006/10/19(木) 17:24:59 ]: /* 画素データ取り込み */
for(i=0;i<ras.ras_height;i++){
for(j=0;j<ras.ras_width;j++){
/* B → G → R(24bit) */
fread(&B[i][j],sizeof(unsigned char),1,fp1);
fread(&G[i][j],sizeof(unsigned char),1,fp1);
fread(&R[i][j],sizeof(unsigned char),1,fp1);
}
}

/*線形補間法*/
for(i=0;i<height;i++){
for(j=0;j<width;j++){

nt = floor(i/bai);
nn = floor(j/bai);
p = i/bai - nt;
q = j/bai - nn;

r[i][j] = R[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+R[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+R[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+R[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
g[i][j] = G[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+G[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+G[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+G[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
b[i][j] = B[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+B[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+B[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+B[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;

}
}
372 名前：デフォルトの名無しさん [2006/10/19(木) 17:27:39 ]: この線形ほかんの部分を3次補間にしないといけないのですが・・・
373 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 17:50:33 ]: 宿題スレ池
374 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 21:39:46 ]: >367-371
・宿題の趣旨を理解していないバカ
・「初心者」と書けばなにをしても許されると思ってるバカ
・構造化出来ないバカ
・ざっと見ただけでもコンパイルが通らないのが解るコードを晒すバカ

久々に悪寒が走るほど汚ぇコード見たわ。
375 名前：デフォルトの名無しさん [2006/10/19(木) 22:12:12 ]: 初心者をバカにするやつに上級者はいない(^.^)
376 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 23:37:57 ]: >>374
これ、たぶん宿題出した先生が書いたコードだと思うんだけど、
大学の先生 (特に年配の人) って結構こういうコード書くのよ。
漏れが習った人も FORTRAN が最初だったらしくてこんな感じだった。
理論とかに関してはすごく頭切れるんだけどね…。
377 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 01:36:50 ]: ・糞レスでageるやつは2ch初心者
・携帯のノリで顔文字使ってるやつは2ch初心者
378 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 10:59:23 ]: >>371
＞nt = floor(i/bai);
キャストしる。

＞R[(unsigned char)nt][(unsigned char)nn]
このキャストは意味あるの？
元画像が縦横どちらか256pixel超えると破綻すると思うけど。
それとも、charが16bitか32bitの処理系？

マジで講師の書いたコードだとしたらヤバイな。
こんなの習った奴が卒業して、新人として入社してくるんか・・・orz
379 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 13:02:51 ]: >>376
結構いるよね
原理が分かるんだからいいじゃん，
コード読みやすくするのは各自勝手にやってくれとか思ってそう
380 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 14:37:21 ]: まあ、歳食うと新しいこと覚えられないからねぇ。
FORTRAN のパラダイムのままで C とか Java 書くのなんて当たり前。
381 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 15:04:24 ]: つまり、年寄りってゴミっていうこと？
382 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 15:28:34 ]: そこまでは言わんが･･･
383 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 15:58:18 ]: でも実際この業界では、年寄りは廃棄処分にされるんだよね？
384 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 16:11:20 ]: >>383
その当時、専門でなかった人材を無理矢理ソフトウェア開発に回した、という背景があるからじゃない？
そういう年寄り連中は基礎的な事を学ばずに、現場たたき上げで今までやってきたけど、そのツケが今に回ってきてる。
385 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 16:31:02 ]: んじゃ、年寄りが新しいことを覚えられないというのは、基礎的なことを知らないから、新しいことに対処する能力が低いということ？
386 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 17:07:54 ]: 歳食うと新しいこと覚えられないってのは、人間なら誰でも。
普通は、新しいこと出来ないってのを今までの経験からくる勘とかで補うんだけど、
>>384 みたいな背景があるんじゃ、この業界じゃほんとにゴミになりかねんな、年寄り。
387 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 19:36:38 ]: どの業界でも年取れば、現場から一歩引いて管理職になるが普通じゃないのか？
ただし、ITドカタじゃそれが特別速く押し寄せるってこと。
388 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 20:05:52 ]: >>387
アメリカでは職種は変わらない。
389 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 20:48:27 ]: お前はどこで仕事してる？
390 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 00:03:00 ]: >>387
まあ、だってさ、管理職って多人数は必要ないわけじゃん。
全員が管理職にはなれないだろ。

って、話題がなんかマ板臭いな。
391 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 00:13:51 ]: 【】この業界では何故、年寄りは廃棄されるのか？【】
392 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 13:56:19 ]: >>390
その話の最後は、「国が必要もない公共工事をいつまでも続けるのはなぜなのか」に落ち着くぞ。
393 名前：デフォルトの名無しさん [2006/10/22(日) 22:12:32 ]: ｵﾏｲﾗ赤黒木ってしってる？
394 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 22:13:44 ]: 常識では
395 名前：デフォルトの名無しさん [2006/10/22(日) 23:30:04 ]: 実装を知ってるのと聴いたことあるのとではまったく違う
396 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 23:53:11 ]: どのくらい効率いいの？＞red-black tree

小規模のDBなら偏っても問題無いし、大規模DBならいまどきツリー使ってないだろうし。
ターゲットはどこらなん？
397 名前：デフォルトの名無しさん [2006/10/23(月) 00:33:08 ]: FEMプログラムで使われてるのは見たことある。
398 名前：デフォルトの名無しさん [2006/10/23(月) 00:43:13 ]: >>国が必要も無い公共工事を続ける理由

三下土方に職を与える為
に落ち着くぞ
399 名前：デフォルトの名無しさん [2006/10/23(月) 00:45:39 ]: >>人口減ってるから、住宅作らなくてもいいんだよ。
どうせ大半は地震でぶっ壊れるし。

いやいやゼネコンの小遣い稼ぎでしょう。
400 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 02:05:37 ]: >>393
日本語だと、2色木って言われることの方が多いような、red-black tree。

>>396
要素の挿入・削除時にちょっと処理が増えるけど、
要素の探索時にはペナルティなしで、
木の高さが必ず log n オーダーに抑えられる。

数百～数万程度のデータ扱うときにはすごい効率いいと思うよ。
C++ の map とか C# の SortedDictionary は2色木使ってる。
Java の Hashtable も、名前に反して実装は2色木じゃなかったっけ？
401 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 16:39:56 ]: 2色木は初めて聞いた。俺は赤黒木派。
402 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 18:36:23 ]: 実測結果キボンヌ
403 名前：デフォルトの名無しさん [2006/11/17(金) 17:26:34 ]: 平面上の凸とは限らないポリゴンを三角形分割したいのですが、どういったアルゴリズムがあるでしょうか？
また、そのポリゴンに穴が開いている場合も対処できるアルゴリズムはありますか？
1週間ほど調べているのですが埒があかなくて。。。
404 名前：デフォルトの名無しさん [2006/11/17(金) 18:51:11 ]: 穴空きなら、外側とつなぐ。切れ込みを入れる感じで。
凹なら凹部と別の頂点で分割して凸にする。
405 名前：デフォルトの名無しさん mailto:sage [2006/11/18(土) 03:15:54 ]: どんな多角形だろうと、単調多角形への分割をした後に
単調多角形の三角形分割をして O(n) で解けることが知られている。

まともな計算幾何の本ならだいたい書いてあるとおもうが。
406 名前：デフォルトの名無しさん mailto:sage [2006/11/18(土) 03:21:41 ]: その単調って凸と同じ意味？
407 名前：デフォルトの名無しさん mailto:sage [2006/11/18(土) 12:45:18 ]: 違う。端点のリストを一番下にある点から巡回したとき
y_1 < y_2 < ... < y_k, y_k > y_{k+1} > y_{k+2} ... > y_n となること。
つーか本嫁。
408 名前：デフォルトの名無しさん [2006/11/18(土) 21:06:08 ]: ここにでてくるShare Sortってなに？
ぐぐっても日本語の解説が見つからなかったよ。
とりあえず並列処理用のアルゴリズムらしいのは
わかったけど。

www.cs.rit.edu/~atk/Java/Sorting/sorting.html
409 名前：403 mailto:sage [2006/11/19(日) 15:10:28 ]: >>404-407
ありがとうございます。
なんとなくわかりました。
ただ、本屋に行ってみて計算幾何の本をいくつか見てみたのですが、どの本がよいかよくわからなくて...
もしお勧めがあれば教えていただけないでしょうか。すみません。
410 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 15:57:59 ]: >>408
www.cs.mu.oz.au/498/notes/node35.html
これじゃだめ？
・row columnにわける(row数,column数はプロセッサ数の定数倍に近いほうがよいだろう)
・奇数rowで昇順ソート偶数rowで降順ソートをする
・columnで昇順ソートをする
何回かやってるとできるはずなのでできたら取り出す
なんでrowのソートで逆にする必要があるのかな...
411 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 19:39:16 ]: >>409
www.amazon.co.jp/gp/product/476490277X/
www.amazon.co.jp/gp/product/4795263213/
412 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 20:20:48 ]: >>411
ありがとうございます！
早速買ってこようとおもいます。本当にありがとうございました。
413 名前：デフォルトの名無しさん [2006/11/19(日) 20:44:17 ]: shear sort実装してテストしてみたんだが、std::sortに比べて遅い・・・
int型で要素数2^16程度だと何回か繰り返してみたが25倍程度遅く、
2^32程度だと１回のテストで1000倍程度遅かった。
coreが1個だとオーダも悪いね。n個もcoreがあるなら、
quick sortでも順次分けていけるようなきがするし、
メモリを飛び飛びにアクセスして書き換えるから並列処理にも合ってない気がする。
414 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 21:06:23 ]: O(n log n) を切れるソートって、かなり特殊な前提がないと使えないんじゃないの？
データの数と同じだけプロセッサがあるなら、
バブルソートでも O(n) でしょ、確か。
その Shear ソートも、そういう前提の下で O(√n) とかではないの？
415 名前：デフォルトの名無しさん [2006/12/13(水) 12:06:49 ]: 「ｍ個の数字集合からｎ(0～ｍ)個の組み合わせを比較し、指定値Ｘ以上かつ最小の組み合わせを求める。」

こういうプログラムを作りたいのですが、どうアルゴリズムを組めばいいのかわかりません。
どなたかお願いします。

例
インプット
　数字集合：5,7,10,12,15
　指定値：18

　↓数字集合の組み合わせで、『指定値』以上かつ最小の組み合わせを求める。

アウトプット
　最小合計値の組み合わせ：7+12=19
416 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 12:34:57 ]: >>415
アルゴリズムを説明すれば自分でプログラム書けるの？
プログラム書いてほしいとか言うのは宿題スレいってくれ
417 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 12:50:26 ]: ナップサック問題のバリエーション？
418 名前：415 mailto:sage [2006/12/13(水) 12:50:50 ]: >>416
アルゴリズムによってはプログラムで書けるか分からないので、宿題スレに行きます。
419 名前：429 mailto:sage [2006/12/13(水) 13:26:11 ]: 415ではないが移動先はっとく
pc8.2ch.net/test/read.cgi/tech/1165943509/22/
420 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 14:16:15 ]: >>417
Subset Sum Problem という有名 NP （の、最適化問題版）。
まあバリエーションといえばそうなんだけど、知ってて損はない名前よ。
421 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 14:37:22 ]: 問題から推測すると集合の最大値は指定値をより小さいのかな
422 名前：415 mailto:sage [2006/12/13(水) 15:15:11 ]: >>419
お手数おかけしました。

>>417 >>420
有名な問題なのですね。
名前自体しらなかったです。

>>421
集合の全合計値より、指定値が小さいという意味ならそうです。
423 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 17:46:53 ]: sqrt(O(N^2)の処理)の計算量が知りたいのですが
sqrtの計算量わかる人いますか
424 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 19:59:02 ]: >>423
sqrt( O(N^2) の処理 ) という記号の意味がわからん。処理の平方根って何。
具体的にどんなことをしているかを書いたほうが正しい解が得られると思われる。
425 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 00:00:12 ]: ひょっとして多倍長計算？
ニュートン法なら一回の反復で桁数２倍
426 名前：426 mailto:sage [2007/01/24(水) 15:42:39 ]: ttp://www.apple.com/jp/downloads/dashboard/developer/colourmod.html
このようなカラーピッカーを作りたいのだけれど、
中心からの位置によってどのようなRGBに変換されるかの式がわかりません。
どうやって計算しているのでしょう？
427 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 15:46:57 ]: >>426
ttp://image-d.isp.jp/commentary/color_cformula/HSV.html
Hが円角度 Sが円半径 Vが隣の垂直ﾊﾞｰ　じゃねーかな？
428 名前：426 mailto:sage [2007/01/24(水) 15:54:15 ]: >>427
ありがとう、作ってみます
429 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 16:01:43 ]: >>428
変な色マップになったら　同サイトの HLS変換も試してみてね
430 名前：426 mailto:sage [2007/01/24(水) 16:58:12 ]: >>429
おかげさまで出来ました。atanの戻り値[-pi/2,pi/2]を[0,360]に変換するのにミスったのと
427さんに紹介してもらったページのFの式が間違っていた（正しくはF = H/60 - I）ので
ちょっとだけ手間取りましたが、無事きれいなカラーサークルになりました。
ありがとうございました。
431 名前：デフォルトの名無しさん [2007/01/24(水) 17:14:29 ]: 強欲アルゴリズムについて分かる人はいますか？
432 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 17:32:15 ]: 貪欲とかgreedyとかで検索したらどうだろう。
433 名前：デフォルトの名無しさん [2007/01/24(水) 17:36:37 ]: それがなくて…
434 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 19:08:19 ]: 俺はだいたいのところは分かっていると思うぜ
435 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 19:27:16 ]: >>430 atan2使えばいいんじゃね？
436 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 06:11:36 ]: 長さが同じint配列が2個ある。
一つの配列内で重複する数は無い。
同じ数がそれぞれの配列で同じ位置にあるとは限らない。
で、一方の配列内に入ってる数が全て他方の配列にも入っているかを確認したい。
こういう場合で配列をそれぞれソートして
先頭から最後まで一致するかを調べる以外に何かいい方法ある？
437 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 07:12:23 ]: それは set equality problem という問題で，
O(n log n) が計算量下界であることが知られている．
よって，計算量的には 436 のソート比較は最適．

ハッシュとか確率的アルゴリズムとかで実用的な速度は
上がるかもしれんが，ソート比較が簡素で良いと思うよ．
438 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 09:06:29 ]: >>437
なるほど。
ありがとう。
439 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 09:26:09 ]: >438
データの範囲が狭ければ有無の配列(データが添字)を使ってO(n)で可能
データに対して有効なハッシュ関数があれば広くても同上
440 名前：デフォルトの名無しさん mailto:sage [2007/01/27(土) 00:38:31 ]: データの個数があんまり多くないからソート比較でも十分速くできた。
>>439
>>437でハッシュと聞いてピンと来た。
機会があれば今度その方法も試してみるよ。
ありがとう。
441 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 14:13:28 ]: 有無なら配列じゃなくてビットマップにしろや
442 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 11:48:52 ]: >441
もしかして：ビットの［配列］
443 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 14:05:22 ]: >>441
アルゴリズムと実装は区別しような
分からなかったらスレッド名も見てくれ
444 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 23:26:47 ]: >>443
言葉遊びがしたいのか？
アルゴリズムと実装でいうならどう実装をしようが配列は配列
最適化の話がしたいならアセンブラスレでも逝け
445 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 00:44:54 ]: >>444
444=441 ?

とりあえず君の配列の定義が知りたい。

アルゴリズム論の文脈では、実装における配列と理論における
配列はまったく対応しない可能性があるけど、それは大丈夫？
446 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 10:54:45 ]: え～い面倒くせえ
ビットマップ＝ビットの配列
でFAだろ
447 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 12:10:45 ]: まぁ、普通そんなこと言わんがな。
448 名前：デフォルトの名無しさん mailto:sage [2007/02/08(木) 15:47:29 ]: ある会計（０円～９９９円）を行う際に
一回の硬貨のやり取り（渡す枚数+受け取る枚数）を最小にするアルゴリズム

考えているんだけど思いつかない・・・助けてくれ
449 名前：デフォルトの名無しさん mailto:sage [2007/02/08(木) 16:32:47 ]: void minimumExchange(int account) {
　　int pay = account;
　　int min = getCount(account);
　　for (int i = account + 1; i < 1000; i++) {
　　　　int c = getCount(i) + getCount(i - account);
　　　　if (c < min) {
　　　　　　pay = i;
　　　　　　min = c;
　　　　}
　　}

　　System.out.println("account=" + account + " pay=" + pay + " min=" + min);
}

int getCount(int n) {
　　int c = n/500;
　　n %= 500;
　　c += n/100;
　　n %= 100;
　　c += n/50;
　　n %= 50;
　　c += n/10;
　　n %= 10;
　　c += n/5;
　　n %= 5;
　　return c + n;
}
450 名前：デフォルトの名無しさん mailto:sage [2007/02/08(木) 17:16:55 ]: ちょっと修正

＞　　for (int i = account + 1; i < 1000; i++) {
を
　　for (int i = account + 1; i <= 10000; i++) {

＞int getCount(int n) {
を
int getCount(int n) {
　　n %= 1000;

アルゴリズムを考える時はまず、最も分かりやすい方法（しらみつぶしとか）を考えるといいと思います。
それでダメならそれから工夫する事を考えればいいのですが、大抵はそのままでも大丈夫です。

＃「硬貨のやり取りが最小」とは別に紙幣を払ってもいいのですね。
451 名前：デフォルトの名無しさん mailto:sage [2007/02/09(金) 22:24:47 ]: 1円札から999円札まで1円単位の紙幣を使ってもいいんですよね
特に条件が指定されてないので
452 名前：デフォルトの名無しさん mailto:sage [2007/02/09(金) 22:28:43 ]: 999円札なんて無いだろ
常識で考えれ
1円札を999枚使うんだ
453 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 08:59:48 ]: >>452
>1円札を999枚使うんだ

現在有効なお金
ttp://www.boj.or.jp/type/list/yuko/okane.htm

一円券は今でも有効だから使用は違法ではないし
常識で考えて不可能というわけではないな。
つまり「現在発行されている」という条件がない限り、
硬貨のやり取りは常に0が最小というわけだ。

一本取られたな。
454 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 14:08:01 ]: でも一円札とかって１円より価値あるよな
455 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 14:24:42 ]: 貨幣として使う分には１円だ。
456 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 14:26:34 ]: そこでコイン商やオクだな
457 名前：デフォルトの名無しさん mailto:sage [2007/02/10(土) 15:35:02 ]: 買いたい人が*いれば*ね。
はっきり言わせてもらうと、一円札程度なら、札束で無いと誰も買わないよ。
458 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 20:53:26 ]: 金融恐慌時の裏面がすってないお札なんかは高かったりするのだろうか
459 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 22:02:58 ]: 刷られた数
使用された期間
現存数
等は少なければ少ないほど良い

どんなにいらなそうな物でもコレクターにとっては価値がある
460 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 03:28:54 ]: そういえばうちの親父が記念硬貨とか集めてたな。
天皇陛下御在位６０年1万円硬貨とか。
461 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 10:21:21 ]: 売りたい人は山のようにいるから。
462 名前：デフォルトの名無しさん [2007/03/03(土) 14:04:36 ]: 質問よろしいですか。

２次元空間上に重複して平面が沢山（簡単のため長方形で）ありました。
ある点を選んだとき、その位置を含む平面の集合が欲しいのですが、
どんなアルゴリズムがいいでしょう？

よくある問題っぽいですね、もし問題に名前がついてたら、それだけでも
教えていただけると助かります。
463 名前：デフォルトの名無しさん mailto:sage [2007/03/03(土) 15:16:32 ]: ん？

たとえばＡ４用紙の束かなんかを床に撒き散らしてから、ピンを一本床に突き刺す。
ピンが刺さっている紙を全部調べよう

って問題？
464 名前：デフォルトの名無しさん mailto:sage [2007/03/03(土) 17:58:17 ]: >>463
ピンを横に置くんじゃないの？
465 名前：デフォルトの名無しさん [2007/03/04(日) 09:59:17 ]: 長方形と点のコリジョンだね。元データをグリッドに分割しておくのが
普通かな？２次元だと正方形や可変サイズのグリッドとか
ツリー状（検索を対数的なオーダーに減らす）にしておくとかいろいろ種類はあるよ。
466 名前：デフォルトの名無しさん mailto:sage [2007/03/04(日) 10:41:11 ]: 重複していない空間の分割なら、もっと簡単なのだから
平面を全部領域別けして、その領域にリンクリストで平面を割り付けるのが簡単じゃないのかな
467 名前：デフォルトの名無しさん [2007/03/04(日) 11:15:36 ]: 六十周年金貨はあったけど
五十周年金貨ってなかったよね？
468 名前：462 [2007/03/04(日) 18:16:51 ]: そうです、紙をピン止めみたいな奴です。

3次元に拡張するために、かなりの広さで使うため、グリッドにするのは無理なもので、木にできると嬉しいです。

実装は難しくてもかまいません。
469 名前：デフォルトの名無しさん mailto:sage [2007/03/04(日) 19:08:06 ]: 長方形は固定で点がいろいろ与えられるって考えていいのかな
今適当に考えただけだけど
最初に排他的な長方形の集合を探してR1とする
(多い方がいいけど最大独立点集合問題はNP困難なので適当でいい）
R1に含まれてない長方形の中から排他的な集合を探してR2とする。
これを再帰的に繰り返す。
点が与えられたらR1から順番にどの長方形に入ってるか調べればいい。

全部の長方形が重なってたらそれぞれ1つの要素からなる集合になるから
結局全部チェックしなきゃいけなくなってしまうのでダメ。
もっといい方法があるのかもしれん。
470 名前：デフォルトの名無しさん mailto:sage [2007/03/04(日) 19:10:09 ]: 空間を超平面で切って平面集合を2つに分ける。
両方に属する平面があってもよいが、できるだけ2分するような超平面を選ぶ。
探索は点がどちらの超空間に属するかを調べて属するほうの平面集合を総当りで調べる。
これで全部の平面を総当りよりおよそ1/2の計算量になる。
あとはこれを再帰で最終的に完全二分木に近い形で分割できればOK。
471 名前：462 [2007/03/05(月) 01:18:32 ]: 空間を超平面で切るってのは、いわゆるBSP木みたいなもんですよね。

その場合平面が両方の空間に属すると、両方の枝に平面を登録することになるわけで。
例えば一番最後に全部を覆う大きさの平面が入ってきたら、その平面を分割しまくら
なくちゃいけなかったり、データ量が問題になるかな、というのが現在の悩みです。
472 名前：デフォルトの名無しさん mailto:sage [2007/03/05(月) 03:30:57 ]: 閾値より大きな領域は、別段そのツリー内に入れなければいいのでは？
単一の構造にする必要性も無いし、BSPは静的なものだけにすればいいし。
473 名前：デフォルトの名無しさん mailto:sage [2007/03/05(月) 20:42:16 ]: 空間を平面で切るときに
・一方の空間に完全に属する領域の集合（２つ）
・断面と交わる領域の集合
の３つに分けてみるのはどうか．こうすれば各領域は必ず一箇所に属する．

探索するときは，断面上の領域と点の落ちる空間内の領域の２つを調べる．

断面と交わる領域の格納は
数が少ないとき（多分，n < (log(n))^d'（d'は断面の次元）のとき）は単純なリスト
数が多いときは１つ次元を落とした同様の構造にする

よくわからないけど最終的には
(log(n))^d （dは次元）←適当
あたりになりそうな気がする．
474 名前：デフォルトの名無しさん mailto:sage [2007/03/05(月) 21:19:27 ]: >470-471 >473
なぜ一般次元に拡張を…
応用が利くのは良いっちゃあ良いんだけど微妙
475 名前：462 [2007/03/06(火) 01:07:58 ]: >>472
大きいというか、重複が多い場合に結構問題になるんです。
今回は空間全ての領域で少なくとも３枚は被さっているのを想定してるんで、
必要な記憶領域がかなり大きくなってしまうという。

>>473
あ、そうか、２つとも探索すればいいんですね。
１次元で紙に書いてみたら、いけそうな感じです。
記憶領域はO(n)ですね、計算量もちょい大き目のlog(n)っぽい。
よーし、明日の夜にでも組んでみます。
476 名前：デフォルトの名無しさん mailto:sage [2007/03/06(火) 20:33:21 ]: こーいうのって全くの別人が同時期に同じ解法を求める事ってないよな。

特定(ry
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 ]: ２４シーズンⅤで解析に、独自のアルゴリズムを使って出す、とか言ってた。
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 ]: 値近くてハッシュが衝突するって、どんなアルゴリズムだよ
578 名前：デフォルトの名無しさん mailto:sage [2007/10/31(水) 02:27:51 ]: 8byteの16進データを
完全ハッシュ化するソースコード置いてある
とこないですか？
579 名前：デフォルトの名無しさん mailto:sage [2007/10/31(水) 21:09:37 ]: 区分サンプリング法やラテン超方格法のアルゴリズムを教えてください。
580 名前：デフォルトの名無しさん mailto:sage [2007/11/28(水) 05:05:51 ]: 二点で定義されてる直線上に、ある点があるかどうかを判定するにはどうすればいいですか、教えてください。
581 名前：デフォルトの名無しさん mailto:sage [2007/11/28(水) 06:17:51 ]: 要は３点が一直線に並んでいるかを知りたい、と解釈し直してみた。
１点を基準に他２点へ直線を引くときの傾きが一緒だったらOK。
x軸と垂直だった場合なんかも考慮すると、
(x1-x0)*(y2-y0)==(x2-x0)*(y1-y0)
582 名前：デフォルトの名無しさん mailto:sage [2007/11/28(水) 13:05:52 ]: あ、なるほど、ありがとうございます
583 名前：デフォルトの名無しさん mailto:sage [2007/12/07(金) 21:54:02 ]: [N][N]の2次元配列を３つ

[N]の配列を2つ使ってる場合の使用領域のオーダーってＯ(n^2)におさまります？
584 名前：デフォルトの名無しさん mailto:sage [2007/12/07(金) 22:02:42 ]: うん
585 名前：デフォルトの名無しさん mailto:sage [2007/12/09(日) 21:31:14 ]: 3N^2+2N = O(N^2) が分かってないのか？
586 名前：デフォルトの名無しさん [2007/12/14(金) 13:42:55 ]: グレブナ基底を求めるプログラム、誰か持っていませんか？
C言語でおねがいしたいです。
587 名前：デフォルトの名無しさん mailto:sage [2007/12/15(土) 02:12:22 ]: >>586
23457円になります。
588 名前：デフォルトの名無しさん [2007/12/29(土) 03:46:49 ]: 均一なセル上に分割した空間で、円（または球）を配置して、円と交差する
セルを全て見つけたいのですが、どうしたら効率よく求まるでしょう？
589 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 06:33:27 ]: セルってのはよくわからないのだが、格子なの？
格子が座標と平行になるように回転変換して　格子間隔が1になるように伸縮して
円の中心座標の小数点以下座標を見ればいいだけでは？
590 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 07:51:56 ]: あ、格子です。あ、最初から座標軸並行を仮定してます。
さらに辺の長さを1で仮定してしまいましょか。
えーと意味がいまいちつかめないんですが、

＞格子が座標と平行になるように回転変換、格子間隔が1になるように伸縮
これは元々が単位格子であるなら何もしないでOK?

＞円の中心座標の小数点以下座標
これで、なぜ全ての格子が求まるかがわかりません。
整数部をみれば、中心を含む格子は求まると思いますが。
591 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 13:33:11 ]: 欲しいのは「円周」と交わるセルだろ？
そこがちゃんと書いてないから勘違いされたと思われ
592 名前：デフォルトの名無しさん mailto:sage [2007/12/29(土) 17:06:31 ]: あ、そうです。申し訳ない。
593 名前：デフォルトの名無しさん mailto:sage [2007/12/30(日) 12:13:13 ]: DDA(digital diffrential analyzer)というのがあるが使えないかな？
３次元は分からんが
594 名前：デフォルトの名無しさん mailto:sage [2007/12/30(日) 12:39:28 ]: 3次元も、半径が違う円で切り出したものと考えればイケルんじゃないの？
595 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 01:56:42 ]: ある年月日が与えられ、そのn日後の日付を求めたいのですが、
1,fairfieldの公式で西暦1年1月0日からの経過日数daysを求める
2,days+nを西暦年月日に変換する
という方法を考えました。
2は1の式を変形して解けるだろうと見当を付けていましたが、
小数点以下を切り捨てたりしているためうまく式を求められません。
素直に最初の日付にnを足し、年・月に順次繰り上げていくほうが賢明でしょうか？
日付は最近のものに限定して考えています。
ユリウス暦とグレゴリオ暦の判断が面倒になるので…
596 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 08:25:44 ]: >>595
日付を1日進めるプログラムは書けるかい？

おｋ。ならば、1日進める部分をn回実行するんだ。
597 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 08:49:10 ]: つーか、なんで既存ライブラリを使わないのだろう。
大抵の言語に日付け処理系の関数があると言うのに。
598 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 11:47:35 ]: >>595
ttp://ufcpp.net/study/algorithm/o_days.html
599 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 12:25:41 ]: >>595
ちょっと検索してみたらこんなのがあった
delphiだけど、ｃ言語に変換するのはこどもあそびにひとしい

ttp://kwikwi.cocolog-nifty.com/blog/2005/12/delphi_266f.html

ところで前々から思ってたんだけど、fairfieldの公式って誰が考案したの？
日本のサイトしか引っかからないんだよね
600 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 12:29:16 ]: >>596
なるほど。
ただ、(情報が小出しになってすみません)n日前の日付も求められるようにしたいので
上に書いたような方法だとdays+nを-に変えるだけで実現できるかなーと･･･
>>597
Cなのでそういった関数はもちろんあるのですが、若干不便なので
勉強も兼ねて自前で実装してみようというわけです。
601 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 12:51:11 ]: >>598
おおお÷4を右シフト演算できるのは考えが及んでませんでした
>>599
(mjd - 15078.2) / 365.25　　…?　もはや何がなんだか。

ttp://cl.is.kyushu-u.ac.jp/Literacy/PP/H14/adp/program/date.html
こんなの見つけたので読んできます。
602 名前：デフォルトの名無しさん mailto:sage [2007/12/31(月) 13:18:34 ]: >>600
ttp://www.tensyo.com/urame/date/day_c.shm
ここの
int YMD_AddD(int *Y,char *M,char *D,long d）　って関数を見ると
負数を渡した場合は　400年循環を使って正に直せばいいみたい。
603 名前：デフォルトの名無しさん mailto:sage [2008/01/01(火) 10:28:35 ]: つまり、-3日なら 400年前から(146097-3)日後と計算するわけか
604 名前：デフォルトの名無しさん [2008/01/02(水) 02:09:27 ]: 除算のシフト演算化はコンパイラの最適化段階で
自動でやってくれるものだと思ってたんだが、そうでもない？
605 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 08:29:27 ]: コンパイラの性能がソレなりならって事でしょう。
固定値の除算ならさらに、掛け算で代用してくれるのも多いね。
606 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 10:22:11 ]: >>604
2のべきの定数ならね。
607 名前：デフォルトの名無しさん mailto:sage [2008/01/02(水) 12:18:44 ]: という事で
１、カレンダを1日進める関数関数を作る
２、+N日は１の関数をN回呼ぶ
３、-N日は、年数を400日戻してから、146097-N回１の関数を呼ぶ
608 名前：595 mailto:sage [2008/01/02(水) 20:05:17 ]: これでいいのかな？
struct Date{
　int year,month,day;
};
/* 1日進める */
void tomorrow(Date& x)
{
　int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
　if((x.year%4==0 && x.year%100!=0) || x.year%400==0){
　　days[2]++;
　}
　x.day++;
　if(x.day>days[x.month]){
　　x.day=1;
　　x.month++;
　}
　if(x.month>12){
　　x.month=1;
　　x.year++;
　}
}
609 名前：595 mailto:sage [2008/01/02(水) 20:06:50 ]: /* n日後の日付 */
Date after(Date x,int n)
{
　for(int i=0;i<n;i++){
　　tomorrow(x);
　}
　return x;
}
/* n日前の日付 */
Date before(Date x,int n)
{
　n=146097-n;
　for(int i=0;i<n;i++){
　　tomorrow(x);
　}
　x.year-=400;
　return x;
}
610 名前：595 mailto:sage [2008/01/02(水) 20:39:23 ]: 「1にちずつ遡りながら日付を表示」とかやるとbefore()の処理量が馬鹿にならないので、
>>601に載ってるのを参考に書き換えてみました
/* 西暦1年1月0日からの経過日数から、日付を求める */
Date make_date(int n)
{
　int y=(n+305)/146097*400
　　　　+(n+305)%146097/36524*100
　　　　+(n+305)%146097%36524/1461*4
　　　　+(n+305)%146097%36524%1461/365;
　int diff=n-(365*(y-1)+y/4-y/100+y/400+31+28);　// 3月0日からの経過日数
　if(diff==0){　　　　//2月29日
　　diff=366;
　　y--;
　}
　int m;
　for(m=3;;m++){
　　//3月0日からm月0日までの経過日数, 30*(m-3)+3*(m+1)/5-2 の変形
　　if(153*(m+1)/5-122<diff && diff<=153*(m+2)/5-122){　
　　　break;
　　}
　}
　int d=diff-(153*(m+1)/5-122);
　if(m>12){
　　m-=12;
　　y++;
　}
　Date x={y,m,d};
　return x;
}
611 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 03:16:56 ]: 漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ
612 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 03:17:24 ]: 誤爆です。
ごめんなさい
613 名前：デフォルトの名無しさん mailto:sage [2008/01/08(火) 13:01:23 ]: >>611
そのまんまの意味じゃなーの。
f(x)=sin xで1,-1は明らかに漸近的ではないが
g(x)=1/x(x≥0)で0は漸近的。
614 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:18:07 ]: 質問させてください。

「ハッカーのたのしみ」p137 で多倍長のかけ算のサンプルがあったのですが、
わからない部分があります。

void mulmns( unsigned short w[], unsigned short u[], unsigned short v[], int m, int n ) {
unsigned int k, t, b;
int i, j;
for( i = 0; i < m; i++ ) {
w[ i ] = 0;
}
for( j = 0; j < n; j++ ) {
k = 0;
for( i = 0; i < m; i++ ) {
t = u[i] * v[j] + w[ i + j ] + k;
w[ i + j ] = t;
k = t >> 16;
}
w[ j + m ] = k;
}
}

u と v がかける数、かけられる数、w に結果が入ることはわかるのですが、k は何に使われているんでしょうか？
615 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:31:46 ]: 繰り上がり
616 名前：614 mailto:sage [2008/02/09(土) 20:41:09 ]: >>615 すばやい回答ありがとうございます。
くりあがりですね。

このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、
この理解で合っていますか？10 進数で表示したいときには変換するルーチンも別に必要でしょうか？
617 名前：デフォルトの名無しさん mailto:sage [2008/02/09(土) 20:44:43 ]: >>616
そのとおり。

10進数で画面に表示する回数が、普通の計算を行う回数よりも
圧倒的に少ないと考えると、そういう数の表現になる。
618 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 16:13:21 ]: w[ i + j ] = t;
k = t >> 16;
この部分を
　k = t/10;
　t -=k*10;
w[ i + j ] = t;
とすれば、１０進法になるんじゃない？
8bitなら１００進数
16bitなら10000進数なんてのがオススメだよ
619 名前：デフォルトの名無しさん mailto:sage [2008/02/11(月) 23:37:33 ]: HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた
620 名前：デフォルトの名無しさん [2008/02/18(月) 17:15:48 ]: 行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、
調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。
なぜ誤差が大きくなるのでしょうか？
621 名前：デフォルトの名無しさん mailto:sage [2008/02/18(月) 23:15:28 ]: 誤差についてはほとんど知識がないので調べてみました。
たまたま今やっていることに関係あるので。

さて、分かったことは小数演算は必ず誤差を含むと言ってもいいこと。
なので、10^n倍で整数に変換したり、ライブラリを使ったり対策を
しなければいけないこと。まぁ大体こんな感じです。

ではなぜ掃き出し法が誤差が大きいかというと、予測ですが
単純に計算量が他に比べて多いからではないでしょうか。
誤差を含む演算はやればやるほど誤差が大きくなるというわけです。

ちゃんとした理由ではないかもしれませんが、それよりも
どうすれば誤差を小さくできるか考えた法がいいと思います。
まぁ原因が分からなくては始まりませんが。
622 名前：デフォルトの名無しさん mailto:sage [2008/02/18(月) 23:42:00 ]: >>621
そんなに詳しくないから適当に書くけど、
基本的にはその通り。
収束性が悪いほど誤差は積もりやすい。

あと、除算があると誤差大きくなる。
なので、掃き出し法みたいな手計算的手法のものよりも、
ガウスザイデル法みたいな反復計算の方が誤差少ない。
623 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 02:13:06 ]: >>620
一概にそうとは言えない。というか、単純に比べることは不適当。

そもそも掃き出しは（解けるならば）必ず A x = b を解くが、
ガウスザイデル、SOR は特殊な A に対してしか一次方程式を解かない。
したがって、無条件で比較することはできない。

次に、生じる誤差が違う。掃き出し法は直接解法なので、考える誤差は丸め誤差のみ。
一方のガウスザイデル、SORは反復解法なので考える誤差は丸め誤差と打切り誤差。
反復法の打切り誤差をどの程度に設定するかということを述べないと、比較はできない。
624 名前：デフォルトの名無しさん [2008/02/19(火) 13:21:15 ]: >>623
掃き出しで解けるものでもガウスザイデル、SORで解けないものもあるということでしょうか？
新たな課題ですね(￣□￣;)!!
実は、エクセルマクロで書いた掃き出し法で計算した回帰分析と、
エクセルの分析ツールの回帰分析した結果、
後者の方が精度がよかったので分析ツールの回帰分析は別のアルゴリズムなのかなと考え調べていました。
後者はガウスザイデルなのかもしれません。
625 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 16:20:26 ]: >>624
マクロでやってるなら、ピボットの選択してる？
626 名前：デフォルトの名無しさん mailto:sage [2008/02/19(火) 18:31:45 ]: >>624
掃き出しで解けてガウスザイデルで解けない問題なんて
いくらでもあるよ．たとえば
　x + 2 y = 1
　2 x + y = 1
をこの順番で連立方程式と考え，ガウスザイデルを
初期値 x = 0, y = 0 で適用すると，発散する．
ガウスザイデルが収束する必要十分条件は，未解決のはず．
627 名前：デフォルトの名無しさん [2008/02/21(木) 22:41:32 ]: >>625
＞マクロでやってるなら、ピボットの選択してる？
いえ、まず中心をすべて1にしてから掃き出しています。
これではダメでしょうか？
628 名前：デフォルトの名無しさん mailto:sage [2008/02/22(金) 19:59:46 ]: >>627
ダメ
629 名前：デフォルトの名無しさん [2008/04/03(木) 03:18:18 ]: あげ
630 名前：デフォルトの名無しさん [2008/04/17(木) 12:46:54 ]: ユークリッドのアルゴリズム(テキストp.10参照．java版はHP参照)を用いて
1,000,000,000,000,000,000(10の18乗)と25の最大公約数を求めるとしたとき、
引き算は何回行われるか答えよ。また、1秒間に10億回の計算を行えるCPU(クロック
1GHzに相当）を用いてこの計算を行ったとき、計算にはどのくらいの時間がかかるか。
「X年Xヶ月」など実感が分かる単位に直して答えよ。

この解き方がわかる人がいましたら是非教えて下さい。
解けなくて困っています。
631 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 13:30:05 ]: >>630
宿題は自分で解決しようと努力しないと意味がないぞ
どこまでは理解できていて、どこが分からないんだ？
632 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 14:05:58 ]: というか、奇妙な問題だな
10^N は N>=2 なら25で割り切れる。
つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう

もしかして 64bit整数演算が出来ない32bitCPUで除算も筆算法でコードを書いたら
って場合か？　それでも実感がわかる単位にはならないわな
633 名前：デフォルトの名無しさん mailto:sage [2008/04/17(木) 14:46:19 ]: ・>>630が問題を間違えている
・出題者のちょっとした遊び心
どっちかじゃね？

難しそうに見えて実は簡単な問題を出して
最初から課題をやる気がない奴を調べるためだったりしてｗ
634 名前：デフォルトの名無しさん [2008/04/21(月) 13:16:15 ]: int型のデータをN個格納できる配列aを考える．つまり，配列要素は a[0],
a[1], ..., a[N-1] でアクセスする．a[0]～a[k]まではデータが既に格
納されており，a[k+1]～a[N-1]までは「空き」の状態であるとする(0 <= k < N)．
このとき，次に挙げる各操作に必要な手間(時間)を，「最も手間のかから
ない場合」と「最も手間のかかる場合」のそれぞれの場合について答えよ．
理由も書くこと．(例を参考にせよ)

例：指定された位置にデータを挿入する操作

答:最も手間のかからない場合：定数時間
最も手間のかかる場合：kに比例する時間
理由：指定された位置が末尾の場合には，データをずらす必要がな
いため定数時間で可能．指定された位置が先頭の場合には，既に格
納されているk+1個のデータを順にずらす必要があるため，kに比例
した時間が必要．

1-1 指定した位置のデータを削除する操作
1-2 指定したデータが格納されているか探索する操作
1-3 格納されているデータの中で最小の値を探索する操作

これを現在解こうと思っていますが、よく分かりません。
分かる人は是非教えて下さい、お願いします。
635 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 13:32:09 ]: 1-1
最良：定数
最悪：k比例
1-2
最良：定数
最悪：k比例
1-3
最良：k比例
最悪：k比例
636 名前：デフォルトの名無しさん [2008/04/21(月) 15:08:07 ]: 配列を用いてリストを実現することを考える．今，配列には以下のように
データが格納されているとする．(配列keyと配列nextはint型のデータを格
納するとする)

key[0] = 0 ,next[0] = 3
key[1] = 0 ,next[1] = 1
key[2] = 'S' ,next[2] = 6
key[3] = 'L' ,next[3] = 4
key[4] = 'A' ,next[4] = 5
key[5] = 'I' ,next[5] = 2
key[6] = 'T' ,next[6] = 1

位置0はhead, 位置1はzを表す．
このとき，次の問に答えよ．

(1)リストに格納されている文字を，リストの先頭から順に書け．
(2) もしも next[0] の値が4だった場合，リストに格納されている文字を
リストの先頭から順に書くとどうなるか述べよ．
(3) リストから'A'を格納している節点(key[4]とnext[4]に対応)を削除し
た場合，配列keyと配列nextの中身はどのように変化するか述べよ
(key[4]とnext[4]の値はそれぞれ0に設定せよ)
637 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 16:28:55 ]: ここは宿題すれじゃねーんだよ・・・
638 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 17:03:43 ]: 行列計算のガウスザイデル法が収束しないことがあるので気になっていたけど
検索するとGMRes(一般化残差最少法、GMRes法 )というのがあるらしい。
(残差を最小にするから、たとえ解が無くても最適な値が求まる？収束に向かうのは確実？)

ただ、ガウスザイデル法は数行のプログラムなのに対して
見つけたプログラムがかなりでかいサイズになっているのがまた気になる。

ガウスザイデル法で残差を小さくするような改良って無いのかな？誰か知ってる？
639 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 17:40:08 ]: これが、SOR法である。
ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。
www.akita-nct.ac.jp/yamamoto/lecture/2004/5E/linear_equations/relaxation/html/node6.html
640 名前：デフォルトの名無しさん mailto:sage [2008/04/21(月) 18:02:14 ]: ω=1.9から始めて発散なら値を引き下げていけばいいって事だな
ω=1がもともとのやつ　
641 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 00:29:31 ]: ガウスザイデル法には，原理的に収束しないインスタンスが存在するので
収束しないことが気になるような場合には，そもそも使ったらダメ．
これはSORでも状況は変わらない．

GMResやらBiCGやらIDRやら反復解法は色々あるんだから
解きたい問題にあわせて適切に解法を選ばないとダメよ．
642 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 00:57:39 ]: 原理的に収束しないとは? 解が存在する行列でもできないってこと?
643 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 05:48:37 ]: >>641
なるほど、どうもです。
プログラマ的な発想で少し工夫すればいけるんじゃない？と思ってましたが
やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても
その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。
644 名前：デフォルトの名無しさん mailto:sage [2008/04/22(火) 09:27:07 ]: >>642
そのとおり．
ガウスザイデル法は，対角優位とか半正定とかを満たしている場合を除いて
解が存在しても，収束するとは限らない．

いつ収束するかの厳密なところ（必要十分条件）は，現在でも未解決問題．
645 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 16:48:12 ]: >>644
639のこれは?

。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
646 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 17:10:06 ]: >>644
SOR法の0 < ω < 2である係数を2以上にすると必ず収束しない事がわかっている
ωの値によって収束が左右される　0に近づければガウスザイデル法で無理な場合も収束するのでは?
647 名前：デフォルトの名無しさん mailto:sage [2008/04/23(水) 20:15:14 ]: ω=1はガウスザイデル法である
648 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:51:21 ]: グレースケール変換。こいつより高速アルゴキボンヌ。
条件：徐々にグレースケール変換できればvolumeの持たせ方は自由

// 【メソッド名】convGrayScale
// 【引数説明】
// srcRGB：変換元画像(0xRRGGBBのピクセル配列)
// pixel_num：ピクセル数
// volume 0(無変換)～255(完全変換)の範囲でグレースケールに変換
// dstRGB：変換先(0xRRGGBBのピクセル配列)
649 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:52:02 ]: public void convGrayScale(int[] srcRGB, int pixel_num, int volume, int[] dstRGB){
　　int red, green, blue, Y;
　　for(int i=0; i<pixel_num; i++){
　　　　red = srcRGB[i] >> 16;
　　　　green = (srcRGB[i] & 0xFF00) >> 8;
　　　　blue = srcRGB[i] & 0xFF;
　　　　Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算
　　　　if(Y > red){　// R成分の調整
　　　　　　red += volume;
　　　　　　if(Y < red) red = Y;
　　　　}else if(Y < red){
　　　　　　red -= volume;
　　　　　　if(Y > red) red = Y;
　　　　}
　　　　if(Y > green){　// G成分の調整
　　　　　　green += volume;
　　　　　　if(Y < green) green = Y;
　　　　}else if(Y < green){
　　　　　　green -= volume;
　　　　　　if(Y > green) green = Y;
　　　　}
　　　　if(Y > blue){　// B成分の調整
　　　　　　blue += volume;
　　　　　　if(Y < blue) blue = Y;
　　　　}else if(Y < blue){
　　　　　　blue -= volume;
　　　　　　if(Y > blue) blue = Y;
　　　　}
　　　　dstRGB[i] = (red << 16) + (green << 8) + blue;　// 変換結果
　　}
}
650 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 01:54:17 ]: あ、一応JavaだけどCとかでもおｋ
651 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 02:10:24 ]: volumeって要は、グレイ化度合いみたいなものなのね。
処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
652 名前：648 mailto:sage [2008/04/25(金) 03:08:47 ]: volumeって要は、グレイ化度合い⇒そのとおり！
volumeを255まで振る前にグレイになってしまう
⇒それは思ったけど、取り得る範囲がわからんかった。。。
　r=0,g=0,b=255、r=255,g=255,b=0の場合で29.191890～225.808365の範囲で196.616475がMAXかなぁ
振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
⇒ちょっとわからんkwsk
　ちなみに自分の使い方としては元画像srcRGBはずっと変えずにvolumeを増やす感じ
　だから一度変換したdstRGBをsrcRGBに使うことはない
653 名前：648 mailto:sage [2008/04/25(金) 03:15:22 ]: ちなみに、volumeを0～100%として

dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
　　　　　　(((Y * volume + green * (100 - volume)) / 100)<<8) +
　　　　　　((Y * volume + blue * (100 - volume)) / 100);

としたてみたけど、遅くなったorz
654 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 06:45:23 ]: Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000;　// グレースケールの計算
これの意味を教えて
655 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 06:54:50 ]: >>654
YUV とか色空間あたりでググって見たら、、、
wikipedia の「色空間」だとか
ofo.jp/osakana/cgtips/grayscale.phtml の 2.NTSC ～
にある式を小数点の無い形にしたと考えたらいいんじゃない?
656 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 07:26:42 ]: こういう時は
Y = (red * 19589+ green * 38444+ blue * 7503) / 0x10000;
か、
Y = (red * 77 + green * 150+ blue * 29)/ 256 ;

と２のベキにしたらどうかな　/256 は >>8 に出来る
8bitにすれば rgbも8bitだから 16bitの入れ物で計算出来る

dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
　　　　　　(((Y * volume + green * (100 - volume)) / 100)<<8) +
　　　　　　((Y * volume + blue * (100 - volume)) / 100);
もvolumeを２のベキにして
Y*k + X*(1-k) = X+(Y-X)*k なので

dstRGB[i] = ((( red + (( (Y - red )*volume)>>8) )<<16) +
　　　　　　　　((( green+ (( (Y - green)*volume)>>8) )<<8) +
　　　　　　　　 (( blue + (( (Y - blue )*volume)>>8) );
としたら掛け算は減らせるよ
657 名前：648 mailto:sage [2008/04/25(金) 07:54:03 ]: >>656
なるほど！！さんくす
　Y = (red * 77 + green * 150 + blue * 29) >> 8;
　dstRGB[i] = (((red + (((Y - red) * volume) >> 8)) << 16) +
　　　　　　　((green + (((Y - green) * volume) >> 8)) << 8) +
　　　　　　　(blue + (((Y - blue) * volume) >> 8)));
今、これで自分の環境で試したら1000ms切った！(前は1100msくらい)
でも500くらいは欲しいorz
658 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 08:51:23 ]: >>657
distRGB の方は、
(red + (～)>>8)<<16 を red<<16 + (～)<<8 などど展開して
red<<16+green<<8+blue とまとめて、
*volume) << の部分を出して因数分解できれば良さげだよね。
>>8 の方もレジスタの H を取るような方法で早くなるかな。
だだ、新しいCPUだとシフト演算もテーブル化してあって
シフト回数がステート数に影響しないからなぁ。
あっ。もうすぐ9時なのでここまででカキコ。
659 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 10:12:30 ]: java　だから　割り算をシフトにするとかの最適化があんまり効かないのかもな

どの行が一番時間かかってるか　コメントアウトしては時間計って
一番時間かかってる行から順に工夫してゆくしかないと思うけど
cかDelphiでDLL作った方が早いんじゃないの？
660 名前：デフォルトの名無しさん mailto:sage [2008/04/25(金) 10:20:09 ]: あとは
Y8 = Y<<8
v = 256-volume;

dstRGB[i] =(((( ( Y8 - ( (Y - red )*v) ) & 0xFF00 )<<8 +
　　　　　　((( ( Y8 - ( (Y - green)*v) ) & 0xFF00 ) +
　　　　　　 (( ( Y8 - ( (Y - blue )*v) )>>8 ;

くらいかなv = 256-volume は最初からそう使えば問題ない
でも半分は無理だろな
661 名前：デフォルトの名無しさん mailto:sage [2008/04/26(土) 10:06:56 ]: >>645
任意のパラメタωに対して、真の解に収束しない例が作れる．
662 名前：648 mailto:sage [2008/04/26(土) 13:27:23 ]: >>658-660
いろいろありがと。
今んとこ、volume調整計算を事前にしておくことで800ms切ることができた
volumeは10段階くらいあればよくて、グレースケールの精度もそこまで求めてない
この条件でまだいげねがな？

char[][][] g_gray_tbl = new char[256][256][10]; // グレースケール変換計算テーブル

// 事前計算処理
// src：変換前値 dst：変換後値 vol：度合い(0～9の10段階)
for(int src=0; src<256; src++){
　　for(int dst=0; dst<256; dst++){
　　　　for(int vol=0; vol<10; vol++){
　　　　　　g_gray_tbl[src][dst][vol] = (char)(src + (((dst - src) * vol) / 9));
　　　　}
　　}
}

dstRGB[i] = ((g_gray_tbl[red][Y][volume] << 16) +
　　　　　　(g_gray_tbl[green][Y][volume] << 8) +
　　　　　　g_gray_tbl[blue][Y][volume]);
663 名前：デフォルトの名無しさん [2008/06/12(木) 13:23:40 ]: 誰かクイックソートが挿入法よりなぜ早いのか教えてくれ

クイックソートのほうがめんどくさそうなのに最速とか理解できん・・・
664 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 14:07:54 ]: >>663
クイックソートがソートの中で最速ってわけではないが……
同じデータ数なら、挿入法よりもクイックソートの方が
ソートが完了するまでの比較回数やデータ位置の入れ替えの回数が
平均的に少ないアルゴリズムになっているから。
ソートは基本的にループや再帰呼び出しによる操作だけれど、
ループに入る前や出た後の準備や後始末、
それにループ内での操作が少しくらい複雑になっても、
ループや再帰の回数がそれを補って余るだけ減少する方法なら全体として速くなる。
665 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 15:26:15 ]: >>663
大まかな話、例えば10,000個のデータをソートする場合、データの比較や交換を行う平均的な操作回数は、
挿入法なら1回当たり2～10,000個のデータの操作を行うループを10,000回行うから50,000,000回程度の操作が必要。
クイックソートは10,000個のデータをピボットに対する大小で2グループに分けるということを行うのに10,000回の操作が必要。
さらに2つに分けたグループごとに同じことを行うので両方のグループ合わせてやはり10,000回の操作が必要。
この分割をどんどん進めて最終的にグループ内のデータ数が1個になるまで行うと分割回数はlog10,000/log2=13回程度。
つまり全部で約130,000回の操作が必要になる。
50,000,000回と130,000回の操作では比べるべくもないということ。
しかもクイックソートは挿入法に比べて全体的に複雑なことをやっているように見えても、
データの比較や移動という基本的な操作にかかる時間が変わるわけではないから、
操作回数の極端な減少はソート時間の減少に繋がるということになる。
666 名前：デフォルトの名無しさん mailto:sage [2008/07/04(金) 23:20:30 ]: エクスポゼのような敷き詰めとGraphVizのようなほかの四角とかとぶつからないように関係する四角を近くにレイアウトしてさらに関係線を四角にかぶらないように線を引くアルゴリズムがわかりません(´・ω・｀)
667 名前：デフォルトの名無しさん mailto:sage [2008/07/27(日) 08:46:19 ]: >>666
おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ？
668 名前：デフォルトの名無しさん [2008/08/30(土) 18:14:43 ]: あげ
669 名前：デフォルトの名無しさん [2008/10/11(土) 22:27:10 ]: www.forest.impress.co.jp/article/2007/04/24/dfsupt.html
↑テキスト比較ツール「DF」のように２つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
（C#を予定）

この手のプログラムを組むにはどのようなアルゴリズムを調べれば実現できる
ようになるでしょうか？
670 名前：669 mailto:sage [2008/10/11(土) 22:29:00 ]: 失礼。↓こちらのスレで質問した方が適切でしたね。よく調べずに質問してすいません(´･ω･｀)

プログラミングの為の数学と算数 vol.3
pc11.2ch.net/test/read.cgi/tech/1197063023/
671 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 23:04:05 ]: >>670
こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの？
672 名前：669 mailto:sage [2008/10/11(土) 23:11:15 ]: >>671
両者の「aaa」と「ccc」がそれぞれ一致したと見なされ、前者の「bbb」が不一致と表示されます。
673 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 23:16:47 ]: >>669
手始めに ONP とか LCS とかでググレばいいんじゃね。

ONP とかだけだと、関係ないものがいっぱいヒットするから
「ONP アルゴリズム」とかでググルが吉。
674 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 01:23:58 ]: どうでもよさげだがDFの説明だとしたら>>672はちょっと言い方が適当過ぎないか？
diffっぽく聞こえる。　いや、やりたいことはdiffなんだろうけど。
675 名前：669 mailto:sage [2008/10/12(日) 01:54:11 ]: >>674
オリジナルの文のうち、消えた部分を特定できれば十分です。

aaa　aaa
bbb　ccc
ccc　ddd

左がオリジナル、右が比較用としますとオリジナルから消えた部分として
bbbを特定できれば満足です。
676 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 02:27:20 ]: >>675
あくまでアルゴリズムが知りたいなら>>673のとおりに。

外部ソフトの起動初心者じゃなくて、手軽にやりたくて、
２ファイル間の比較でいいならDOSにFCというコマンドがあるからC#からそれを呼んでその結果を解析すればおｋ
677 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 07:27:56 ]: > 手軽にやりたくて、

今時 FC はないだろ。

って言うか、それなら DF 呼び出すようにするだろうし。

単に楽したいだけなら、C# で LCS の実装例とかも見つけられるでしょ。

参考 URL: d.hatena.ne.jp/siokoshou/20070308
678 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 12:10:51 ]: >>677
DFってそういう出力する方法あるのか？

わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

あとFCなら配布時に別途導入してもらう必要が無いし。

あと>>673のキーワードで見つけられない人が実装例みて実装できるのかちょっと疑問。
679 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 13:30:35 ]: > わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

FC 勧める理由がわからん。

比較するテキストファイルの書式が決まってるならまだしも任意のテキストファイルを
想定すると、FC の出力の解析は結構大変だよ。
680 名前：669 mailto:sage [2008/10/12(日) 14:19:04 ]: 動的計画法と配列アラインメント
ttp://www.ibm.com/developerworks/jp/java/library/j-seqalign/index.html

↑LCSのプログラムに関して概念を説明しているサイトがありました。
これにそってLCSテーブルを作り、LCSを見つけてみようと思います。
681 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 15:09:12 ]: >>679
勧めた理由はその次の行に書いたが？

ぶっちゃけそれ以上の理由は無い。

解析が大変だと思うのは同意。

>>680
>>677のソースをコピペでいいのに。
682 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 15:26:58 ]: >>681
> 勧めた理由はその次の行に書いたが？

配布の容易さと解析の容易さの比較は状況次第だから議論は避けるよ。

> >>677のソースをコピペでいいのに。

>>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
ペでは得られないものがあると思うよ。

頑張れ > >>669
683 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 16:11:41 ]: 確かにプログラム書くことが目的なのかアルゴリズム知ることが目的なのかもはっきりしてなかったね。

とはいえスレとしては後者として考えるべきだった。　ｽﾏﾝｶｯﾀ
684 名前：669 mailto:sage [2008/10/12(日) 16:18:39 ]: みなさん暖かい支援どうもですm(_ _)m

> >>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
> ペでは得られないものがあると思うよ。

はい、>>680のサイトでO(NM)の単純なアルゴリズムに関してはおおよそ把握することができました。

可能ならば
hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
で紹介されていますO(ND)アルゴリズムや、さらに進化したO(NP)アルゴリズムも
理解したいと思っています。

さっそくO(ND)とO(NP)を解説した原著論文をDLしてきたのですがなかなか全体像を
把握するのが難しいです(´･ω･｀)
もう少し優しくかみ砕いて説明してくれているサイト、できましたら日本語で、があれば
嬉しいのですがそういうサイトは無いでしょうか？
685 名前：669 mailto:sage [2008/10/12(日) 16:19:20 ]: >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
d.hatena.ne.jp/siokoshou/20070315

aaa　aaa
bbb　bbb
　　　 ccc
（左がオリジナル、右が比較対象）

早速この二つを比較してみたところ。
オリジナルの"aaa"はCommon（共通）と判断されたものの、オリジナルの"bbb"はModified（変更）
と判断されました。ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。
686 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 16:22:21 ]: >>685
もっとPCの全般的な基礎知識を得た方がいいような希ガス。
おそらく、左のbbbには行末に改行文字がないのではないか?
687 名前：669 mailto:sage [2008/10/12(日) 16:35:39 ]: >>686
左のbbbには\nを付けましたが、やはりModifiedが返されるようです。

あと
aaa　aaa
bbb　ccc
　　　 bbb
だと

Common
Modified
Common

と返されるようです。
オリジナルが2行なのに返される行が3行だと後々の処理がちょっとややこしくなるかもしれません・・・
688 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 17:10:18 ]: > ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

C# のソースがあるんだから、ステップ実行しながら見てみればいいと思うんだが。

あと、それはそれとしてバイナリエディタを１つ使えるようになっておいた方がいいと思う。
テキストエディタ上では同じ改行に見えても片方は 0x0d のみで、もう一方は 0x0d 0x0a
なんてこともあるから。
689 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 17:48:14 ]: >>687
鈍らな比較ツールだと、「挿入された」ことを理解できないから>687のようなことになる。
逆に言えば、「挿入された」ことを考慮しないアルゴリズムでは、目的に合っていないと言うことだけ。
それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。
690 名前：669 mailto:sage [2008/10/12(日) 17:56:39 ]: >>689
> それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
> 意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。

釣りとかでは無いです（；´∀｀）・・・

>>685も>>687もどちらもオリジナルが2行なのに対して
比較対象の文字列（どちらも3行）をいじるだけで出力が
2行になったり3行になったりと変わってしまうと後々の
処理がややこしくなるかなと思った次第です
691 名前：だから、無駄なことはやめておけと mailto:sage [2008/10/12(日) 18:14:36 ]: >>690
読解力のない間抜けだということはよく判りました。
692 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 18:47:39 ]: 何で>>690みたいなゴミみたいな奴がアルゴとかやってんの？
693 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 19:52:19 ]: >>685
> >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
> d.hatena.ne.jp/siokoshou/20070315

そこのコードは最長共通部分とか返してくれない。
「とにかくO(NP)の最速で動くdiffコードを作ってみました」
ということを実証するためのコードだからあまり実用的じゃないぞ。
あるいはコードに手を入れてちょっとした改造を施すか汁。
694 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 20:58:19 ]: >>689
>それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
なんか勘違いしてね？
その二つの例が別の話題だということは>>687が「あと」と言っていることから分かる
自分の読解力を過信して、ろくに理解せずに他人にいちゃもんを付けるのは格好悪いよ
695 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 21:04:24 ]: >>691
> 読解力のない間抜けだということはよく判りました。

読解力の無いマヌケはお前の方だったようだなｗ
696 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 21:07:15 ]: 面白そうだから黙ってたのに。
697 名前：デフォルトの名無しさん [2008/10/12(日) 21:07:29 ]: 頭おかしくなっちゃうと屁が出るんだよねｗ
698 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 21:17:48 ]: >>689
(ﾉ∀`)ｱﾁｬｰ
699 名前：デフォルトの名無しさん mailto:sage [2008/10/12(日) 22:11:35 ]: basicのほうが早くね
700 名前：　 [2008/10/14(火) 00:07:37 ]: 文字列照合アルゴリズムでSIGMAてのがあるらしんですけど
詳しいアルゴリズムを解説したページありませんか？
なんか宣伝のようなページしか見つかりません。
701 名前：デフォルトの名無しさん mailto:sage [2008/10/14(火) 18:55:04 ]: ttp://hdl.handle.net/2324/3109
ここにたどり着いた
あってるかは知らん
702 名前：デフォルトの名無しさん mailto:sage [2008/10/14(火) 19:06:55 ]: management system だから違うんじゃなかろうか
>>700 はどこでSIGMAという名前を知ったの？
703 名前： mailto:sage [2008/10/15(水) 18:43:09 ]: >>701
エラーがでます。

>>702
シュンサクとかいうデーターベースで使われてると読んだのです。
704 名前：アラフＯＯ.ｏ（笑） [2008/10/15(水) 23:21:58 ]: >>703
オモローな記事があるぞ。兄弟。

いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
ttp://www.atmarkit.co.jp/fcoding/articles/algorithm/01/algorithm01a.html
705 名前：デフォルトの名無しさん mailto:sage [2008/10/16(木) 20:09:11 ]: >>703
pr.fujitsu.com/jp/news/2006/12/15.html
> 九州大学の有川節夫氏（現在、理事・副学長）と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA（シグマ）を基に開発・実装されている。

アルゴリズムじゃなくてシステムじゃないか。
人物から見ても >>701 であってるんだな。

あと、エラーが出るならどんなエラーが出るかくらい書こうよ。
少なくとも俺の環境では問題なく見られるけど。
706 名前： mailto:sage [2008/10/17(金) 03:43:42 ]: >>701 >>705
失礼しました。前見たときはWebのエラーがでて見れませんでしたが今見れました。
大変ありがとうございました。
707 名前：デフォルトの名無しさん [2008/10/18(土) 18:41:25 ]: 範囲のリストに新しい１つの範囲を追加するアルゴリズムをお願いします。
例えば、[1,2][5,7][8,15]という範囲のリストがあります。
上記のリストに[3,5]という範囲を追加すると
[1,2][3,5][5,7][8,15]に。

上記のリストに[1,6]という範囲を追加すると
新しく追加する範囲が常に優先されて、
[1,6][6,7][8,15]に。

上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
[1,2][5,7][8,10][10,13][13,15]。

リストは常にソートされているものとして、各範囲は重なって
はいけません。上記で範囲[Start,End]でEndは含まれません。

範囲のリストに1万件とか２万件を高速に連続追加できれば幸いです。

よろしくお願いします。定石のアルゴリズムがありそうですが、私の実力ではわかりません。
708 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 18:46:16 ]: あ、後、範囲のリストのデータ構造は配列・リストでお願いします。後でインデックスによる
アクセスをしたいので。
709 名前：デフォルトの名無しさん [2008/10/18(土) 18:53:28 ]: 多めに確保して置いて、存在するところのビットを立てておけ。
710 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:14:08 ]: データ構造はリストでお願いします。聞きたいのはアルゴリズムです。
実際は、各範囲にオブジェクトが関連付けられていますというより、
あるクラスに開始範囲を表すStartIndex,EndIndexフィールドがあります。
考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ
サーチして追加位置決定？
んー。
711 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:14:40 ]: ふと思いついたもの。

範囲を示すインデックスにどの範囲に属するかという情報を持たせる。

上の例で実際にやってみる。
[1,2][5,7][8,15]に[3,5]を追加する。
範囲を示すインデックスがどの範囲に属するかという変数 = ID (0,1,0,0,0,2,2,0,3,3,3,3,3,3,3)
[3,5]を追加。(0,1,0,4,4,2,2,0,3,3,3,3,3,3,3)

[1,6]を追加。(0,4,4,4,4,4,2,0,3,3,3,3,3,3,3)

[10,13]を追加。(0,1,0,0,0,2,2,0,3,3,4,4,4,3,3)

以上。追加は高速だと思う。
範囲のリストへのアクセスはIDからリストを作るので、そこは作る処理の時間だけ遅くなる。
712 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:19:05 ]: そして、追加位置からリストを後方に向かって１つずつ追加範囲と比較？
追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整？
完全に含まれていれば、削除？
713 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:24:57 ]: あー。すみません。データ構造とアルゴリズムは関係があるので、データ構造はリスト
でお願いしますといいましたが、撤回します。すみません。
ある程度高速であればいいです、自分が考えたコードが醜く読みずらくなっていくので
何かいいシンプルなアルゴリズムないのかなと思った次第です。
>>711
ありがとうございます。ちょっと考えてみます。
714 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 19:39:07 ]: >>711
なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。
715 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 21:13:16 ]: 範囲の列を、pより小さい部分とp以上の部分に分ける操作を考えて「値pによる分割」と呼ぶことにする
例えば[1,2][5,7][8,15]を3で分割すると[1,2]と[5,7][8,15]に、
10で分割すると[1,2][5,7][8,10]と[10,15]になる(このように列の分割が範囲そのものの分割を伴うことがある)

範囲の列Sに[start, end]を挿入するには、Sをstartで分割してS1とS2を得、S2をendで分割してS3とS4を得、
S1とS4の間に[start, end]を挟んだものを結果とすればいい

Sをpで分割するには、まずS中の範囲でendがpを越えるもののうち一番左にあるものを探す
そういうものがなければ、SはSと空列に分割される
あれば、それのbeginをpと比較して、それを分割するか全部右側に入れるか決める

多分この手順でいけるけど、これが高速に実行できるようなデータ構造は何があるだろう
2-3 Finger Treesとかならindexとappendとsplitが全部O(log n)だから、O((log n)^2)で挿入できるかな
716 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 21:47:34 ]: >>702 >>713
データ構造を弄ってよいなら，
できるべき操作をちゃんと指定してほしい．
たとえば

(1) 範囲の追加
(2) 範囲 [x,y] に含まれる全ての範囲を小さい順に出力
(3) 小さいほうから数えて k 番目の範囲の出力
(4) ある点を含む区間の有無の判定
(5) ...

みたいな感じで列挙してください．

あと，>>710 に関して質問なのだけど，
いまある区間が分割された場合（>>707 の [10,13] の例），
オブジェクトとしてはどうなっているの？

(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
(b) [8,10] と [13,15] は同じオブジェクトに対応する

どっち？
717 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 23:22:08 ]: >>707
範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
２万件とか言ってるなら、
struct {
　unsigned int StartIndex;
　unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。
718 名前：デフォルトの名無しさん mailto:sage [2008/10/18(土) 23:25:14 ]: >挿入とか削除は自前で好きなように
まさにその部分を質問してるんじゃね？
719 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:17:17 ]: >>713,714
反応してくれてどうもです。

最近はあまりやらないんですけど、前はパズルを解くプログラムを作ったりしていました。
ポイントは簡単な問題を数多くこなす事だと思っています。
すると、どういう処理が効率がいいのか分かってきます。

こういう場合の為におすすめです。あまり無いと思いますが。。。
720 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:52:35 ]: ＞上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
＞[1,2][5,7][8,10][10,13][13,15]。
これだけどさ、なんで
[1,2][5,7][8,15]
じゃないの？　そういうルールだからと言われたらそれまでだけど
こういう処理が必要な実例が思いつかない。
721 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 00:59:37 ]: >>720
想像力不足
722 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:38:10 ]: 俺は動画のフレーム編集を想像しながらスレを見てた
723 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 01:42:24 ]: だとしたら>>716のa,bはa？

あと>>721はどんなもの想像してたんかな？
724 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 10:05:09 ]: >>707です。
>>716
>(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
オブジェクトを複製して別物で管理します(範囲以外のプロパティをコピーして)
>できるべき操作をちゃんと指定してほしい．
外部に公開する機能は
・範囲の追加(1個ずつ)
・リストの先頭から末尾への連続アクセス
・リストの全削除
以上です。
>>717
なるほど、上で書いた外部に公開する機能みてもB-Treeでいいのかもしれませんね。
ちょっと実装してみます。
>>715
わ。ありがとうございます。すごいわかりやすいです。

もうちょっと色々もだえてみます。
725 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 10:12:56 ]: ・リストの先頭から末尾への連続アクセス
だとリストでデータ構造固定しちゃうような意味にとられるかもしれないので
正確には、
範囲の列に昇順に連続アクセス
かな。途中からアクセスすることはありません。
726 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 12:23:29 ]: >720
ttp://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。
727 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:08:31 ]: 8≦Nを満たす正の整数Nを3と5の和の組み合わせで表すにはどうすればいい？
3が何個、5が何個って分かればいいんだけど
あと表せない数はあるんだろうか

最初の5つはこんな感じ
8=5+3
9=3+3+3
10=5+5
11=5+3+3
12=3+3+3+3
13=5+5+3
728 名前：デフォルトの名無しさん [2008/10/22(水) 23:37:07 ]: N = 3m+5nでしょ。　互いに素ならいけるんではなかったか? m,nが整数なら
729 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 23:37:40 ]: 単に3と5の個数をデータとして持てばいいんじゃないの?

8,9,10,11,12が書き表せている時点で、次の5つ組
13,14,15,16,17はそれぞれさらに5を足せば作れ、
以降5つ組ごとに足す5を増やしていけばすべて作れるので、
8以上の正の整数でつくれないものはない。
730 名前：デフォルトの名無しさん [2008/10/22(水) 23:39:21 ]: ax+by=1を満たす整数x,yが存在する

d.hatena.ne.jp/gould2007/20071009
731 名前：デフォルトの名無しさん [2008/10/22(水) 23:41:50 ]: そしたら連続する3つ作れればそれ以降、全てつくれるってことだな
732 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:01:14 ]: その日のうちに答がもらえるとは思わなかった
とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました
733 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:50:53 ]: どうもおかしいと思った。

＞最初の5つはこんな感じ

6つあったのねw
734 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:09:36 ]: A Small and Fast IP Forwarding Table Using Hashing.
これ何度みても計算できねぇ助けて
735 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:53:54 ]: 一緒に考えてやるからその論文を見る方法を教えろ
736 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 02:07:20 ]: ttp://cial.csie.ncku.edu.tw/ppt/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.ppt
ttp://cial.csie.ncku.edu.tw/pdf/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.pdf
ぐぐった
合ってるかは知らん
737 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 11:10:39 ]: >>736
それっすそれっす
738 名前：しろうと [2008/10/26(日) 16:22:55 ]: 突然すみません。しろうとです。
バイナリーサーチの計算量はO(log n)ですが、その導き方について。
T(n)=O(1) n<=1
T(n)=T(n/2)+O(1) n>1

以上から、T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3...=T(n/2^k)+k。
ここまではわかるんだが、解説によると(n/2^k)=1とおいて、T(n)=log n+1
したがってT(n)=O(log n)となっている。なぜ、(n/2^k)=1とおくのでしょうか。
また、(n/2^k)=1をkについて解けばlog nにわかりますがlog n+1の1って何なんでしょうか？
739 名前：デフォルトの名無しさん [2008/10/26(日) 18:18:41 ]: アルゴリズムをよく考えてみ
k=１のとき、つまり1回分割したときはn/2
k=2のとき、つまり2回分割したときはn/4 = n/2^2
k=3のとき、つまり3回分割したときはn/8 =n/2^3
といって、求めたいのは、つまりnをk回分割したときの計算量だから
k=???のとき、つまりk回分割したときにn/2^k　→ ???を求める為には
数式頼みはよろしくないよ
740 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 18:49:12 ]: >>738
ひどい導出だ．O(1) の扱いが雑すぎる．
T(n) = O(1) (n <= 1) なんて意味不明すぎる記述．

もし本当に本にこう書いてあるなら捨てたほうがいい．
741 名前：くまさん [2008/10/26(日) 18:59:21 ]: プログラムの初心者です。
アルゴリズムの流れ図について、自然数ｍ、ｎに対して、
ｍのn乗を計算する効率の良いアルゴリズムのフローチャ
ート書くという問題です。
どなたかご教授ください。
742 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 19:37:22 ]: 流れ図の問題なんだな？そうなんだよな？
ではまず、効率の良いアルゴリズムを言ってくれ。
743 名前：くまさん [2008/10/26(日) 22:23:58 ]: ヒントと書かれていたのはｎ＝64のときは乗算はの回数は6回で済む。

n＾２＊ｎ＾２＊ｎ＾２
これがヒントだそうです。
どうしたら、よろしいのでしょうか？
お願いします。
744 名前：くまさん [2008/10/26(日) 22:44:42 ]: ｎの４乗はｎの２乗×ｎの２乗です。　ｎの８乗はｎの２乗×ｎの４乗ですから、展開するとｎの２乗×ｎの２乗×ｎの２乗です。

従い、ｎの６４乗はｎの２乗×ｎの３２乗ですから、ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗となります。
の2乗
これを利用して、ｍのｎ乗のアルゴリズムのフローチャートを書くみたいです。
745 名前：デフォルトの名無しさん [2008/10/26(日) 22:45:56 ]: よくわからんな、何だろ
ビット演算を絡ませたアセンブラ的な問題なのかな？
お前らどうする？これ放置していいん？
746 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 22:53:29 ]: 罠じゃねえの?

説明がデタラメだし。
747 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:18:56 ]: >>744
＞ｎの８乗はｎの２乗×ｎの４乗
ダウト。乗数は足し算です。

n^8
= n^(4+4)
= n^4 * n^4
= (n * n * n * n) * (n * n * n * n)
ね？

＞ｎの６４乗はｎの２乗×ｎの３２乗
同様に、ｎの３２乗×ｎの３２乗がｎの６４乗で
あえて言うなら（ｎの３２乗）の２乗がｎの６４乗

つまり
>>745
問題のヒントが出鱈目だから放置していい。
748 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:20:45 ]: >>736の問題助けてくれｗまじでｗ
749 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:27:51 ]: 要するに>>736を分かりやすく翻訳してくれって言ってる？
サマリー読む限り、別に問題提起ってわけではなさそうだけど……？
750 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:35:16 ]: >>749
4bitの集合を考え、具体例として以下で計算した場合
0000, 1100　0011, 0100, 0110, 0111, 1011, 0001.

1100まで計算した場合のV0とV1って
V0: 0 0 0 0
V1: 4 3 1 1
になりますかね？
751 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 00:12:25 ]: ４ページのExample 1の話？
752 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 20:28:44 ]: うん
753 名前：デフォルトの名無しさん [2008/10/28(火) 20:57:21 ]: kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/7885.txt
上記は疑似コードで書かれていますが、アルゴリズム１もアルゴリズム２も
配列の中から最小値を探し出す処理をしているそうですが、アルゴリズム１の
０２行目では配列をどうやってtempにぶちこめるのでしょうか？配列Aが例えば
{2, 6, 3, 7}だとすると、tempには最初に何が入るのですか？再帰なので、
A[1, 4]を呼び出そうとして、tempに値が入る前にA[1, 3]が呼び出され、やっぱり
A[1, 2]が呼び出され、最終的にA[1, 1]になって、A[1]の２が返されて処理が
終了しそうな気がするのですが、間違っているところを教えて下さい。
754 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 21:06:35 ]: >>753
リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。
要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。
755 名前：デフォルトの名無しさん [2008/10/29(水) 00:57:04 ]: 再帰の仕組みって勉強すればなんとかなるもんじゃないだろ
何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ

>>753
間違ってない、でも再帰の考え方をそうやって深部に潜ってく物だと考えるのは良くない
君の配列の書き方を使って書くと

A[1,4]の最小値は・・・A[1,3]の最小値とA[4]の小さい方！
じゃあA[1,3]の最小値って何さ　→　同じやり方で済むじゃん

みたいな考え方を適用すべき
756 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 01:01:16 ]: LISP学んだり、フラクタル図形書いてみたり
だまし絵とか見に行くといいんじゃないかな
757 名前：755 [2008/10/29(水) 01:09:03 ]: >>753
おっと、質問に答えてなかったので答えます
最初にtempに入るのは、A[1,3]の最小値なので2です。
758 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:22:29 ]: n個の要素から上位3つを選ぶアルゴリズムで速いのはなんですか？

ソートして先頭3つでやるのはなんかもったいない気がして・・・
759 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:41:45 ]: 端から舐めて上位3個を取り出す方法だろうなぁ
760 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:47:31 ]: それだと比較回数3n？
761 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:50:26 ]: ヒープ
762 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:53:24 ]: 20000個のデータで上位100なら、クイックソートとかしたほうが早いですかね？
763 名前：デフォルトの名無しさん [2008/10/29(水) 15:30:41 ]: >>757
ありがとうございました。
764 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 15:31:13 ]: nth_element, partial_sort
765 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:05:02 ]: >>762
上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい．
計算量は全データ数を n とすれば O(n log k)．
k は高々 n なので，計算量はデータ数によらずソートするよりも良い．

実用的にはデータの分布に依存するので，実測しないと何とも．
766 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:16:37 ]: >>765
全体ソートするのとオーダーかわらんじゃん
767 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:31:52 ]: っ「選択アルゴリズム」
768 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:33:23 ]: 選択アルゴリズムはk番目の値しか探せないぞ
769 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:38:05 ]: >>768はまったくプログラミングの才能が無いな。
770 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:41:47 ]: partial_sort使うのがいいんじゃない？
771 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:43:47 ]: >>770
それ、なんのこと言ってるの? C++前提なの?
772 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:50:02 ]: 「部分ソート」と呟いておく。
773 名前：デフォルトの名無しさん [2008/10/29(水) 19:03:55 ]: たとえば2万個から100個選ぶ場合、値の分布が0点-100点だとして
93点以上が100個程度であるとわかっていれば、93点以上を選べばいい。
774 名前：デフォルトの名無しさん [2008/10/29(水) 19:09:33 ]: もしくは、一回目の探索で分布を調べて、100個選ぶにはいくつ以上かを特定する。
次のループでそれ以上を選ぶ。
775 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 21:53:17 ]: v[0]が4にならねーよ
わからねー
776 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 06:19:01 ]: >>766
全体ソートは　O(n log n) だから log の値が違う
777 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 13:30:13 ]: Nは100～10000程度で、double x[N]; に適当な数が入っているとします。
任意の数aに最も近いx[k]を知りたいとき、普通はO(N)の時間がかかりますが、
あらかじめx[]をソートしておけば二分法を使ってO(log N)でできます。

ここからが質問なのですが、2次元の座標としてx[N],y[N]があるときに、
任意の直線との距離が最も小さい(x[k],y[k])を知りたいとします。
（与えられたa,bに対してa*x[k]+b*y[k]-1.0 の値が最も小さくなるkが知りたいということ）
このときに上の二分法のようなアルゴリズムはあるでしょうか？
普通にやるとO(N)が必要ですが、O(N)より速い方法を探しています。
778 名前：デフォルトの名無しさん [2008/10/30(木) 13:54:09 ]: ないな　O(N)で困る例はなんだよ
779 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 15:30:46 ]: >>778
ないこと証明できる？

困る例なんていくらでも思いつくでしょ。
まさか二分探索は不要だとか主張するつもり？
780 名前：デフォルトの名無しさん [2008/10/30(木) 15:43:21 ]: a,bの存在範囲毎に最小点を計算しておけば定数時間
781 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 16:07:07 ]: >>777
i11www.iti.uni-karlsruhe.de/~awolff/pub/dmsw-fpqgc-06.pdf
のイントロに書いてあるけど，
[CY84]: 前処理 O(n^2)，問い合わせ O(log n)
[LC85]: 前処理 O(n^2)，問い合わせ O(log n)
[MC95]: 前処理 O(n log n)，問い合わせ O(n^0.695)
[Mu03]: 前処理 O(n^1+ε)，問い合わせ O(n^{1/2 + ε})
くらいの結果はあるみたいね．

一通り目を通してみたけど，LC85 は特に簡単．双対変換すると
「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」
という関係になることに注意して，点位置決定問題に帰着するだけ．
782 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:50:08 ]: >>781
あるんですね。双対変換を使うという発想はなかったです。嬉しいです。
この方法はイメージがついたので、これからちゃんと考えてみます。

追加ですみませんが、
他の方法について、やり方または論文をネット上で見られるものはありますか？
783 名前：デフォルトの名無しさん [2008/10/30(木) 19:16:37 ]: そもそも何に必要なんだよ?
784 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 19:34:27 ]: >>782
私の大学からだとCY84以外は契約論文誌なので，Webから取れた．
もし必要ならどっかにアップロードするよ．

Mu03はciteseerからも取れたので，論文名で検索してみると良い．
785 名前：デフォルトの名無しさん [2008/10/30(木) 19:47:13 ]: 前処理って言うのが、一回限りだったら logn < √nだから、はじめので十分では?
786 名前：デフォルトの名無しさん [2008/10/30(木) 19:50:29 ]: 最後のやつだとこの辺に関連情報あるぞ
scholar.google.com/scholar?q=simplicial+partitions+determine+closest&lr=
787 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:04:09 ]: >>784
Mu03を見ることができたので、
これまでの材料で頑張ってみます。
ありがとうございました。

>>785
点を一個追加するとか、色々やりたくなるかもしれないので、
いくつかの方法を知っておきたいと思いました。
788 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:29:11 ]: >>785
O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。
n < 2^32 程度でも前処理しきれない。

なので、クエリ時間を増やしても n^2 より安い手法が存在する。
789 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 16:28:46 ]: マス目に二種類の記号を置いていった時、

AAA　　　　ABA
ABB　　　　ABA
AAA　　　　AAA

というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか？
790 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:43:56 ]: >>789
問題が不明瞭

マス目に記号が入ったものが二つ与えられたとき、
それが回転で移りあうかどうかをチェックしろということ？
791 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:54:59 ]: 簡単な方法はない。
地道に全回転・反転パターン（8通り）を網羅してチェックする。

プログラムが見通しよくなるように工夫がひつようかも。
792 名前：デフォルトの名無しさん [2008/10/31(金) 18:21:54 ]: 行同値的を出してそれを比較すれば・・・駄目か
793 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 18:37:25 ]: トランザクションメモリの実装
ここでやる夫的に説明してくれよ
794 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 19:41:21 ]: 　　　 .　'　　　_ 二二 _ .､
　　　　　　／　　　 /´ -‐…‐- .｀＼
　　　　　　 /　　　　 /´　　　 i　　 !｀ヽﾄ､
.　　　 ,ﾍ　 ,' 　 i　　 !　 !　 |　|i　　|ﾊ　i　ヽ　ｷﾘｯ
　　　/　ゝ!　ﾉ|　　! !::__!::ノ ´　￣　 i::.i ｜!
　　　＼　 .|　.:i i :i　i |´　　＼　　／　｀!､ﾊ:!　　
　　　｀ヽi　从 i　i | ニﾆﾐ　　　 .ﾆニ !:::::|　　＜トランザクションメモリの実装
.　　　　　 | 　ＹﾊｉﾊN　 {r::ﾘ｀　　´{r::ﾘ '::::N　　　　ここでやる夫的に説明してくれよ
.　　　　　 |　　ヽゝ　　 ´´　　　　　｀｀ﾊ!｀　
.　　　　　 |∧ 　 Ⅵ!　　　　　 ′　,':::|
　　　　　ｊ/∧　 _!::｝　、　　 ⊂'　..ｲ:::::|
　　　　　 ///∧´ ∨　　｀　,.... ィ´ﾞY:::::|
.　　　　 /////∧　ヽ　　　　{ﾄ､∧　|::::::!
　　　　 ,＜￣￣∧　 } ｀ヽ　　＞''}　{￣｀ヽ
.　　　 / 　｀ヽ:::::::::Y´ヽ　　　　　 i´｀∨::::∧
　　　/　　　 ∨:::::| .:: !　　　　 i .:.: !::::/　i

　　　　　　　　　　　＿＿＿_
　　　　　　　 ,. :'´: :,.　-―‐-ミ:ヽ、
　　　　　　／: : : :厶ｨ': ´￣￣ヾ : :＼
　　　　　 /: : : : : :.!: :M: : : : : }､: ヽﾄ､:.＼　　　＜じゃっておｗｗｗ
　　　　　ｉ: : :.!: : : ﾚ‐'　｀￣⌒　⌒" ﾄﾍ:ﾊ!
　　　ﾄ--|: : :.!: : ､|　　ｰ‐'' ´ ｀'ｰ　　}: :.ﾄ
　　ﾐ　ﾐ　ﾐ : :!: : : :!　z=≡　　　≡z.{: :.ﾊ　　　　ﾐ　ﾐ　ﾐ
　/⌒)⌒)⌒.ﾊ :_Nとつ　＼＼＼ C VVﾘ　　/⌒)⌒)⌒)
　|　/　/　/:弋こ　＼ヽ　＿＿,.　　　}　(⌒)/　/ / /／
　|　:::::::::::(⌒) : :}＼　　/　　　1　／　　ゝ　　:::::::::::/
　|　　　　　ノくf⌒Y ｀　{_　　_,ﾉイ| 　　　/　　）　　/
　ヽ　　　　/　ヽ　ﾍ,､　　_｢　|::!:::::} 　　/　　　　／　　　　バ
　　|　　　　|　　 l||l　从人 l||l.!::|ｲ:::ヽ_./ l||l 从人 l||l　　バ　　ン
　　ヽ　　　 -一''''''"~~｀`'ー--､/:::::ｲ;　 -一'''''''ー-､　　　　ン
　　　ヽ＿＿＿＿(⌒)(⌒)⌒)　):::/}　 (⌒＿(⌒)⌒)⌒))
795 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 21:00:10 ]: かんなぎは評価されすぎ。
796 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 03:17:29 ]: 無向グラフG=(V, E)の隣接リストがGが接続してようとなかろうとO(V+E)であることを証明せよ。
って意味のわかる人教えて下さい。
797 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 06:37:03 ]: 意味が分からんな。
「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。
798 名前：796 mailto:sage [2008/11/13(木) 06:40:40 ]: >>797
無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと
なかろうとO(V+E)であることを証明せよ。だったらどうですか？
799 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:13:30 ]: やはり意味不明。
今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。
800 名前：796 mailto:sage [2008/11/13(木) 07:25:04 ]: そうですか。失礼しました。忘れてもらって結構です。
801 名前：796 mailto:sage [2008/11/13(木) 07:31:12 ]: 別のやつですが、ダイクストラアルゴリズムは経路に負の数があった場合はうまく動作しない例ってのは
例えばどういうときかわかりますか？
802 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:42:43 ]: >>801
G = (V,E) を 3点 a,b,c からなるグラフとし，
頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し，
頂点 a から b への最短路を求めようとすると破綻する．
803 名前：796 mailto:sage [2008/11/13(木) 07:49:21 ]: なるほど。素早い回答ありがとうございます。
804 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 08:36:21 ]: >>802
その例では破綻しないぞ
805 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 11:31:33 ]: >>804
kwsk
806 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 21:00:49 ]: >>802の例だとd(a, b) = 0で探索終わらね？

正答が得られないって意味で破綻なんじゃね？
807 名前：デフォルトの名無しさん [2008/11/14(金) 22:07:03 ]: ユークリッド互除法の最悪時間計算量をLameの定理の結果を用いずに解析せよという問題がさっぱりわかりません。
ぜひ解答お願いしたいです。
スレチでしたらすみません。。
808 名前：びぎなぁ mailto:sage [2008/11/16(日) 05:22:26 ]: アルゴリズムの勉強を始めたのですが、用語が色々あって混乱しています。
（どの用語がどの用語の中に含まれているのかとか）
ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか？

木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子
木構造--------二分木---------------二分ヒープ・・・（１）根に最大値がくる、
　　　　　　　　　　　　　　　　　　　　　　　　　（２）N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい
木構造--------二分木---------------ヒープ・・・二分ヒープと同義？
木構造--------多分木
809 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:29:55 ]: >>808
ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』
を満たすもののことをいう．よって．一般の木上のヒープがありうる．
例えば多分木上のヒープとしてはd分ヒープはたまに使われるし，
より一般の木上のヒープとしてはフィボナッチヒープが有名．

ただ，最もよく使われるヒープは完全二分木上のヒープで，
何も断らずにヒープと言ったときこれを指す場合も多い．

場合によっては配列実装まで含めてヒープと言う場合もあるけど，
フォーマルには構造と実装は別に考えるので，
>>808 の二分ヒープの説明は本当はちょっとよろしくない．
810 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:53:51 ]: >>807
どれくらいの精度で解析すればいいの？

あと，Lameの定理の結果を用いないというのは
Lameの定理を証明して用いるのは良いということ？
それとも，フィボナッチ数で抑えること自体が禁止されるの？
811 名前：デフォルトの名無しさん [2008/11/16(日) 09:19:57 ]: >>810
どの程度の制度かまでは問題に書いてないので、わかりません。
Lameの定理を証明してもダメだと思います。
フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。
812 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 11:41:06 ]: >>811
互除法のアルゴリズムを
gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b)
として解析する（mod は割り算の余り）．a, b ≧ 0 の場合のみ考える．

補題．
a > b ≧ 0 について，gcd(a,b) が k (≧ 1) ステップで終わるならば
a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する．
証明．
k = 1 のときは自明．k-1 まで正しいと仮定．
gcd(a,b) が k ステップで終わるとき，
gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から
b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k，したがって
a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}．
系．
gcd(a,b) のステップ数は O(log min{a,b})．
証明．
a > b としてよく，log b = m とおけば補題より O(m) 回以下のステップ数で終わるため．
813 名前：811 mailto:sage [2008/11/16(日) 17:41:20 ]: ありがとうございます

a ≧ 1.1^{k+1}, b ≧ 1.1^k

この式をなぜ持ち出したのかがわかりません。
あと、系の証明が補題より証明できるあたりがいまいちわかりません。
よろしければ教えてください。
814 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 20:51:27 ]: >>813
上：なんとなく．
1.1 に必然性はなくて，1.0001^k でも 1.0000000001^k でも何でもいい．
(1+ε)^k で示せれば系が示せるので，適当に不等式が成り立ちそうな値にした．

本当に解析しようとしたらギリギリの不等式評価を作るべきなんだけど，
この場合にギリギリに評価するとフィボナッチ数が出てしまうので，
わざとガバガバに評価しているという事情がある．

下：
> できるあたりがいまいちわかりません。
そういうときは具体的にここが分からないとか言うもんだよ．
ただ，補題が少し不十分な書き方だったね．補題は
「k (≧ 1) ステップ以上かかるならば」に置き換えてよい（同じ証明が動く）ので，
そう置き替えておいて，対偶を取ると
「a < 1.1^{k+1} もしくは b < 1.1^k ならば k ステップ未満で終わる」になるので
b < 1.1^m なる m を見つけられれば m ステップ未満で終わる．
そのような m としては log b (の切り上げ) にでも取れば十分(log は 1.1底)．
815 名前：811 mailto:sage [2008/11/16(日) 21:04:38 ]: ありがとうございます。
もう一度問題と向き合って理解を深めたいと思います。
816 名前：びぎなぁ mailto:sage [2008/11/19(水) 07:05:43 ]: >>809
返事が遅くなりました。ありがとうございました。

ところで、最小全域木を求めるクラスカル法とプリム法の概要を理解出来たのですが、
計算量のところがウェブ（ウィキとか）で調べてもよく理解できません。
（１）クラスカル法
グラフの中で一番重みの小さい辺をMSTとして加えて行く。ただしその過程でcyclicに
なってしまうような辺は加えないようにする。計算量はO(E log E)またはO(E log V)

（２）プリム法
MSTに属する頂点とそうでないものの２グループに分け、まだMSTに属していない頂点から
最もコストの安く済む頂点をMSTに付け加えて行く。計算量は３種類あるみたい。
・隣接行列、探索→O(V^2)
・２分ヒープと隣接リスト→O(E log V)（←これはO((V+E)log(V))より）
・フィボナッチヒープと隣接リスト→O(E+V log (V))

ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが
もしわかりやすい説明とかありましたら参考に教えて欲しいです
817 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 08:22:57 ]: >>816
アルゴリズムの計算量を評価するためには
もっと正確にアルゴリズムを述べないといけないんだけど，
あなたの説明だと，良く分からない部分が多い．
（もちろん「普通の実装」というのがあるのだけれど，
　それがあなたの理解しているものと違う可能性もある）

なので，あなたが理解している形で，For やら If やらを使って
手続きが明確に分かるようにアルゴリズムを書いてくれるかな？
その計算量だったら評価するよ．
818 名前：びぎなぁ mailto:sage [2008/11/19(水) 16:22:32 ]: >>817
イントロダクショントゥアルゴリズム二版から抜粋です
---------------------------------------
MST-クラスカル（G, w）
A←0
for each vertex v∈ V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) ∈ E, taken in nondecreasing order by weight
do if FIND-SET(u)≠FIND-SET(v)
then A←A∪{(u, v)}
UNION(u, v)
return A
---------------------------------------
MST-プリム(G, w, r)
for each u∈V[G]
do key[u]←∞
π[u]←NIL
key[r]←0
Q←V[G]
while Q≠0
do u ← EXTRACT-MIN(Q)
for each v∈Adj[u]
do if v∈Q and w(u, v) < key[v]
then π[v]←u
key[v]←w(u, v)
---------------------------------------
819 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:49:58 ]: >>818
その本に計算量の説明が懇切丁寧に書いてあるよ
820 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:54:24 ]: ならし解析ですね分かりません。
821 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 00:37:39 ]: LC-Treisってどんな木なのですかね？
822 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:42:41 ]: >>819
了解です！
823 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:46:49 ]: 「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が
正の数だった場合、ダイクストラ法は失敗することがあるか？」

あれば例を教えて欲しいです
824 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 21:21:36 ]: 「開始点から離れて行く辺」の定義が必要なんじゃね？
825 名前：びぎなぁ mailto:sage [2008/11/20(木) 23:44:17 ]: sourceのことだと思います
826 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 19:02:46 ]: バイナリ木関連のアルゴリズム
詳細に書いてる本ってありますか？
827 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 20:00:17 ]: >>826
詳細ってどの程度？
必要なトピックを具体的にいくつか挙げてください。
828 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 09:34:20 ]: トポロジカルソートはなぜグラフがDAGであることが前提なのですか？
サイクリックなグラフでもソート出来ると思うのですが。
829 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 10:13:52 ]: >>828
トポロジカルソート（トポロジカルオーダリング）をどう定義してるの？
いくつか流儀があるから君の流儀が分からないと適切には答えられない．
830 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 13:40:19 ]: トポロジカルソート：
（１）DAGに対して、DFSを実行する。
（２）Finishing timeの大きい順に頂点を並べる。
というものですが、いかがでしょうか。
831 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 17:21:09 ]: >>830
それを定義に採用するなら，DAGでなくてもいいよ．
ただ，普通はそれを定義にはしない．
（それは，トポロジカルソートのひとつを求めるアルゴリズム）

普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで，
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど，
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する．
832 名前：デフォルトの名無しさん mailto:sage [2008/12/03(水) 04:53:21 ]: >>831
なるほど。わかったような気がします。
ありがとうございます。
833 名前：初心者プログラマ mailto:sage [2008/12/03(水) 16:31:24 ]: 突然すみません。これからプログラミングで一辺に対して指定した数分の円を正六角形の中に敷き詰めるプログラムを
書こうとしています。例えば１と指定した場合は六角形内に１個の円が描かれます。例として９を指定した場合の図を
添付します。
kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8194.zip

聞きたいのは、nの辺の数に対してどのような法則性があるかということです。
１辺の長さを仮に１とした場合、n=1なら中心から半径√3/2の円が描かれると思いますが、
n>=2のときはどのように半径は決まって行くのでしょうか。nが何個であっても普遍的な
法則などあるのでしょうか。アホな質問だったらすみません。
834 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 00:19:45 ]: >>833
数学板へどうぞ。
835 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 00:48:43 ]: >>833
(√3/2)/n
836 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 01:02:08 ]: >>833
>>835は間違い。

(√3/2)/(1+n√3)
837 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 01:02:56 ]: >>836
さらに間違えてた。orz

(√3/2)/(1+ (n-1)√3)
838 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 14:49:49 ]: 有り難うございました。
839 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 04:37:19 ]: ビッグ・オー記法の問題ですが、
a(n)=n^(1/2)
b(n)=10*log[2]n
どちらが大きいですか？導き方を教えて下さい。
840 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 07:34:40 ]: >>839
十分大きな n に対しては n^{1/2} > 10 log n．

lim_{x→∞} x^{1/2} / (10 log x) をロピタルなり何なりで示して
εδで書いてε = 1 にでも取れば良い．
841 名前：839 mailto:sage [2008/12/07(日) 13:57:54 ]: >>840
limがわかっていないのですが、limを使わずに導くことは可能でしょうか？
842 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 14:14:55 ]: δε論法
843 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 01:52:02 ]: わからないなら
a^n >> n^b >> log(n)
とでも暗記しておけ。
大概はこれだけ覚えてりゃ問題ない
844 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 03:53:27 ]: ノイズのある入力列の中から
A->B->C->A => 1
A->B->C->B => 2
A->C->C->C->D => 3
とかの並びが含まれていたら、それをパターンと識別して
=>の後の値に変換する処理を書いています。
今はパターンをトライ木に登録していて速度は問題ないのですが、
共通パターンが少ないとメモリを食うのが気になります。
もう少し効率の良い方法はあるでしょうか。
パターンの候補であるかはインクリメンタルに読み取れる必要があります。
845 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 04:41:33 ]: wiki見たら

基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、
トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。

だとか。もう少し見たら

HAT-trie は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。
時間計算量も領域計算量もハッシュテーブルに匹敵する。

とか。
846 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 06:33:09 ]: >>844
パトリシアではダメ？
847 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 08:28:21 ]: パトリシア木でもいいんですが、
何か別の方法がないか聞いて見ました。
HAT-trieは初めて聞きました。調べてみます。
848 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 12:02:22 ]: >>847
自分もかなり興味があるので調べているのですが、難しいです。。。

とりあえず、HAT-trieの発案者の一人であるDr. Nikolas Askitisのホームページを張っておきます。
goanna.cs.rmit.edu.au/~naskitis/

調べた結果を少しずつでも書いていったらうれしいです。人任せモードに入ってそばで見ております。。。
849 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 21:53:25 ]: 見た目はB-trieという(B木の変形の)変形で、ノードに該当するキーの
代わりに、キーの一部の文字そのものを使い、キーの残りに共通部が
なければ衝突のない小さな順序付きテーブルを作って葉に残りの
文字列を入れる。平衡木が深くなるのを避けつつ、
ハッシュ表と違い順序構造も維持できるって事でしょうかね。
テーブルの入れ方の指定とかチューニングとか書いてありますが、
実際に比較した実装も見せないで他のアルゴリズムとの比較グラフが
載ってるのは胡散臭いです。複雑さによる速度低下はありそうだし、
都合の良いデータなのかもしれません。
1つ言えることは、メモリは減るのかもしれないけど、
平衡木が絡んでくるだけでコード量は数倍に増えると思います。

今使ってるトライのコードは登録検索だけですが60行程度です。
パトリシアにするだけでコードは2倍以上に増えました。
メモリは半分以下になりますが速度は3割減ぐらいです。
850 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 02:43:00 ]: とりあえず、論文を概要まで翻訳してみました。(翻訳サイトありがとう)
間違いがあるかもしれませんが。。。

-----------------------------------------------------------
HAT-trie: キャッシュを考慮したトライベースの文字列のデータ構造

Nikolas Askitis Ranjan Sinha
School of Computer Science and Information Technology,
RMIT University, Melbourne 3001, Australia.
Email: {naskitis,rsinha}@cs.rmit.edu.au

概要

トライは文字列を扱うツリーベースの最速のデータ構造だが、メモリ食いである。
burst-trieはほとんど同じぐらい速いが、バケツの中へトライチェーンを押し込む事でメモリを節約する。
しかしながらこれは、キャッシュを考慮したアプローチではなく、現在のプロセッサでは
不十分なパフォーマンスにつながり得る。
この論文では、既存の手法とうまく組み合せたキャッシュを考慮した
トライベースのデータ構造であるHAT-trieを提案する。
いくつかの現実のデータセットを使用したり、他の高性能なデータ構造と比較して性能を評価する。
ほとんどの場合、キャッシュを考慮したハッシュテーブルに匹敵するぐらいの
実行時間とメモリ使用量の改善が見られた。
HAT-trieはソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。
851 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 11:22:50 ]: 引き続き翻訳してみます。
初めて本格的な翻訳作業をしますがなかなか面白いですね。
段落ごとにまったりとやっていきますので。。

----------------
3 The HAT-trie

現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと
アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001)
これらのデータ構造は検索と更新に必要な命令を最小にするので速いが
とくにキャッシュを考慮しているわけではない。
我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。
852 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 11:24:46 ]: 最後の「原因」は「問題」の方が良さそうです。
853 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 20:03:11 ]: アクセス時にmove-to-frontする
ってどういう事？
854 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 20:08:11 ]: あ、文字列のMTFじゃなくて自己組織化探索の方か。
855 名前：デフォルトの名無しさん mailto:sage [2008/12/13(土) 01:06:00 ]: 論文の英文和訳なんてこんなところでやらんでくれ。
856 名前：デフォルトの名無しさん mailto:sage [2008/12/13(土) 09:13:33 ]: >>853
翻訳が怪しくなりそうなところは英単語のままにしてあります。
アクセス時にmove-to-frontするというのは良く分かりませんが、直訳ぐらいにはなってるでしょうか。

>>855
すみません。今回は翻訳は置いといて（継続！？）
お詫びに、昨日お風呂の中でふと思いついたネタを投下します。

はじめに（論文っぽく）

ハッシュは完全ハッシュしか良いとは思っていません。例えば、>>844でいうと
1 <= A->B->C->A
2 <= A->B->C->B
3 <= A->C->C->C->D
という処理をハッシュでやると、右側を文字列として
int[][][][][] pattern;
pattern['A']['B']['C']['A'][0] = 1;
pattern['A']['B']['C']['B'][0] = 2;
pattern['A']['C']['C']['C']['D'] = 3;
という感じでやります。

しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
そこで最小完全ハッシュを考えます。最小完全ハッシュとはハッシュ値を
0からデータ数-1に割り振る事です。例えば'A'を1、'B'を2、'C'を3にする事を考えますと
すぐに思いつくものはkey['A'] = 1という感じでやれば出来ます。

このまま終わればそっちのネタになってしまいますが、ここからが本題です。
最小完全ハッシュの為のキーを返す処理にただの完全ハッシュを使うのでは本末転倒ですが
その処理を量子演算、量子アルゴリズムを使えば簡単に出来てしまうのではないか
という事を思いつきました。ただの思いつきではなくて見込みのある思いつきだと思います。

そこで量子演算、量子アルゴリズムについて話題を振りたいと思います。（おれ誰？）あ、出掛けます。。。
857 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 04:24:47 ]: ハッシュはキー全体が定まらないと使えないから>>844の条件には合わないよ
858 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 06:01:04 ]: >>856
そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ！」みたいなドツボにはまるだろう。

＞しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。

だってこの発想からだろｗ
続きはブログでやれ。ブログぐらい持ってるよな？ｗ
859 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 11:40:59 ]: ふつーにBM法？
860 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:18:46 ]: >>857
その通りでした。でも、完全ハッシュを説明する為の例なので、言いたい事が伝わればいいかなと思います。

>>858
ブログありますよ。だいぶ書いてないので、仕様で少し大きめの広告をのせられてますが。。。

>>859
BM法は今まで使う機会が無かったですが、>>844には良さそう（？）です。良く分かりませんが。

量子アルゴリズムには一匹も釣れ・・誰も反応しませんねぇ。改めてWebで調べたら思っていたのと
ちょっと違う感じでしたが、少し考えを進ませました。量子アルゴリズムは厳密ではなくても高速で
結果を知りたい場合に有効らしいので、それを元に考えてみました。例えば、キーが3bitで表せるとして
101, 000, 010のデータに最小完全ハッシュを施すのに、3bitの全パターンの全並び（順列）の中から
データがなるべく始めの方に固まっているパターンを見つけます。例えば100 000 010 101 001 111 110 011
という並びは、始めの4つまでに全データが現れるので、ハッシュの大きさは4つ分ですみます。
次に、全並びに番号をつけたとしてその並びの番号を覚えます。この場合は0～!(2^3)-1の番号をつけて974を
覚えます。そして、例えば000のキーが知りたい場合は、番号から並びをほぼ正確に復元して
データのある位置がキーになり、なるべく正しい位置を探します。
この処理のどこかに量子アルゴリズムを適応できるか。あと、格納は置いときます。

翻訳>>851のつづき
-------------------------------------------------------------------------------
burst-trieのボトルネックを解決する為、トライ走査のコスト(作成されるだろうトライノードの数)を
かなり削減しなければならないが、より重要なのはbucketsを探すコストであるが、
それらが現在アクセスする中で最もコストのかかる要素だからである。
そのような削減はbucketsの表現をlinked listからキャッシュを考慮した巨大な配列に
変える事でしか達成できない。したがって、それはキャッシュを考慮したハッシュテーブルの
bucketsの構造化を考えるとよい(Askitis & Zobel 2005)。
シンプルな配列と対照させてハッシュ配列を使う利点は、bucketsがはるかに効率的にscale muchでき、
さらに保持されるトライノード数を減らせることである。
861 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:47:32 ]: >>860
ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。
862 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:56:42 ]: 多少自分の英語に自身があるからといって、日本人は英語が出来ないとか見下している奴だろ。そのオーラがビンビンしてるじゃんｗ
なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。
863 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 12:04:51 ]: >>862 から僻み野郎の気配がビンビン感じられる件
864 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 16:41:59 ]: 流れはよく判らんけど訳すなら全部訳してくれると嬉しい
中途半端はよくないよ
865 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 20:58:14 ]: 全部訳してテキストか pdf にしてどこかのアップローダにあげてくれ。
多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。
866 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:29:56 ]: 木構造の葉ノードをIteratorパターンで順々に得る方法を実装したいのですが、どのようにすればいいでしょうか？
ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします

現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、
もっと効率よい方法があるんじゃないのかなー？って思ったんです
867 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:44:55 ]: 自分でスタック作ってそのハンドルをイテレータのインスタンスとして持ちまわる。
木構造のイテレータは全部それで実装したよ。
効率が良いとされる方法はB+木みたく葉を全部末端に集めて
線形に辿らせるぐらいしかないんじゃないの。
構造に依存するし付け替えも面倒だけど。
868 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:46:22 ]: あと昔のアルゴリズム事典に紐付き2分木というのがあったな。
末端の空きノードを利用するって事だったけど忘れた。
869 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:49:46 ]: まあ何も考えずスタックで組んだほうが保守も楽だし、
追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。
870 名前：デフォルトの名無しさん mailto:sage [2008/12/20(土) 01:36:40 ]: 昔GCのマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。
あれと同じようにすればいいんじゃないか。

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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