アルゴリズムオタク

アルゴリズムオタク ..

175:デフォルトの名無しさん
06/05/08 01:00:24
>>174
そこを自分で考えるのが楽しいんだろ？

176:デフォルトの名無しさん
06/05/08 15:13:52
>>175
そういうレスを返すヤツのことがサッパリ理解できない。

177:デフォルトの名無しさん
06/05/08 15:18:44
>>173
>>113

178:デフォルトの名無しさん
06/05/11 18:47:21
ドッキングツールバーの設計をやっているけれど、
なかなかいい構造が思いつかない。

179:174
06/05/11 21:46:41
>>178
こーゆーケースは理解できるし共感できる。

180:デフォルトの名無しさん
06/05/12 12:43:47
ところでアルゴリズムを相談するスレってどこ？

181:デフォルトの名無しさん
06/05/12 19:21:09
ここでいいよ

182:デフォルトの名無しさん
06/05/25 12:15:42
あげ

183:デフォルトの名無しさん
06/06/08 07:52:46
なあ、グランドにごっちゃに人集めて、
はい背の順に整列！
って時さ、
全員がクイックソート理解してたと仮定して、その通りに整列してもらうより
普通に整列させた方が速そうじゃない？

モデル化すると、要素全てが各々同時並列的に他の任意の要素の値を知れる場合
そして要素が同時並列的に移動できる場合

184:デフォルトの名無しさん
06/06/08 08:47:32
コンピュータモデルとの一番の違いはデータの移動のコストが低いことだな。

大雑把にソートした列に、後はデータ自身が自分の入るべき場所を見つけて両側のデータに対して
スペースを作るように要求する感じかね。
オブジェクト指向のいいテストケースになりそうだが。

185:デフォルトの名無しさん
06/06/08 15:51:28
>普通に整列
脳はだいたい基数ソートみたいなことをしているんだってさ

186:デフォルトの名無しさん
06/06/08 17:05:29 BE:69876566-#
「普通に整列」の手順を考えてみる。

周りのオブジェクト全部をみて整列する人はまずいない。
だいたい自分がどのくらいの序列になるか予想して、整列の初期には近くにいる数人の
オブジェクトのうち同じくらいの序列になる物同士で小グループを形成し、グループ内での
序列を決定した後に他の小グループと合体、境界付近を調整する。
小グループ同士が合体したあとにオブジェクトが余っている場合も、自分の序列がどれくらい
かを予想してそこに近い部分集合の中から自分の序列を決定する。

つーわけで、段階的にマージソートと挿入ソートを同時多発的にやっているような気がする。

187:デフォルトの名無しさん
06/06/08 18:33:14
>>186
>同じくらいの序列になる物同士で小グループを形成し
これがマージソートと根本的に違うところ．

簡単のため小グループとして「背の低いグループと背の高いグループ」
を取って，それぞれで再帰的に計算してやることにする．

マージソートだと，それぞれをソートした結果をマージするときに
前半のトップと後半のトップを比較して云々とやらないといけなくて，
マージの部分の計算量が O(n) になり，合計として O(n log n) になる．

しかし，「普通に整列」の場合は前半のほうが後半よりも小さいと
わかっているので単純にくっつければよく，マージの部分の計算量が O(1) ですむ．
その結果，合計として O(n) でソートできるようになる．

188:187
06/06/08 18:37:48
スマソ，長々と書いていながら誤読してた．
自分の経験から小さい人は前，大きい人は後ろに行って，そこでソート
をやってるもんだと思いこんでいた．

その逆の近くに居る人たちから結合することを考えていたのか．申し訳ない．

＃多分それでも「合体」の部分で適当にオラクルが利いて O(n) になるとは思うが

189:デフォルトの名無しさん
06/06/08 21:38:20
自分がどの程度の背の高さになるかは把握してるとするなら、
最初の移動は粒度の荒いバケツでバケツソートってことになる。
バケツ内での並び替えはどうやってるんかな。

100人の場合と1000人の場合で実験してみないとなんともいえないが・・・

190:デフォルトの名無しさん
06/06/09 00:23:26
だんだんバケツが小さくなる

191:デフォルトの名無しさん
06/06/09 07:50:53
マジレスすると、

１）全生徒はそれぞれ「自分及び他人が（同年代の中で）どの程度の背の高さか」を感覚的に知っている。恐らくはクラスの背の順等の経験から。１０％程度の粒度で。
２）全生徒はそれぞれ個別に（＝同時に）自分が特定の他者より高いか低いかを判断してそれらしい位置に移動することが出来る。
３）数が多くなればなるほど、身長の近い者が逆順に並んでいても問題にしない。

以上の要因から、ＣＰＵ一個が無情報で正確にソートしなければならないことを前提としたアルゴリズムに時間的に優っているのである。

192:デフォルトの名無しさん
06/06/09 09:57:16
>>191
3)に関しては相手にお前何センチって聞けばいんじゃね

193:デフォルトの名無しさん
06/06/09 11:38:13 BE:108696487-#
>>191
機械がやる場合、たとえば標準偏差を与えて記憶や経験の代わりに予想の根拠とすることは
できるような気がする。

194:デフォルトの名無しさん
06/06/09 11:53:31
n 人で整列するとして、

・頭が n 個あるので log n 時間で整列が可能。
・人間が寝ている場合には、　n 台のロボットを使って log n 時間で整列可能。

ただし、

n が大きくなってくると、入れ替えるために移動させるためにかかる時間の方が
支配的になってくるので、O(n) になる。

195:デフォルトの名無しさん
06/06/09 20:29:46
たとえば、探索の場合には、
線形探索や二分探索という位置決めがデータによらない手法に対して、
データの種類によって次の探索位置を変える内挿探索という手法がある。

196:デフォルトの名無しさん
06/06/09 21:22:52
３次元空間上に２つの直線があって、
もしその２直線が交点を持つなら、
交点を計算するアルゴリズムってどうなりますか？
２次元平面上での交点計算みたいに方程式作ってもうまくいかないんですが・・・
なんかヒントくれるとありがたいです。

197:デフォルトの名無しさん
06/06/09 21:34:09
方程式で解くんじゃないの？
直線A：(x(s), y(s), z(s))
直線B：(x(t), y(t), z(t))
とパラメータ表示して、連立方程式
x(s)=x(t), y(s)=y(t)
から s, t を求める。
ここで解があれば、さらにz座標の式にいれてすべての座標が一致するかどうか確かめる。

198:デフォルトの名無しさん
06/06/09 21:40:16
あ～、なるほど。
先に2次元で解いておいて、3次元にしてもOKか見るわけですね。
なんか頭混乱してて、こんなこともわからなかったです・・・
ありがとうございました。

199:デフォルトの名無しさん
06/06/09 21:52:39
数学板で聞けば一発計算できる公式とか教えてくれそう

200:デフォルトの名無しさん
06/06/09 22:05:54
大学受験の頃は一発で出せる公式も勉強したかもしれんが、もう忘れたな。

201:デフォルトの名無しさん
06/06/09 22:25:30
忘れたなら何度でも導けばいい

202:デフォルトの名無しさん
06/06/10 16:23:04
俺なら
(最大値 - 俺の値)/(最大値 - 最小値)

で数直線上の何%くらいに位置するか検討をつけ、
この場合は身長の分布を思い出して、区間の人数割合を想像してから
自分の属する区間あたりにまず向かう。

適当に整列されて来たら
自分より背の高い奴がすぐ前にいればそいつの前に出る。

203:デフォルトの名無しさん
06/06/12 21:23:27
アルゴリズムの達人が集まってるスレはここですか？
質問なんだけど、BPマッチングっていうアルゴリズムって存在する？検索してもそれらしいのがヒットしないんだが

204:デフォルトの名無しさん
06/06/13 01:30:01
Bipartite Matchingかな

205:デフォルトの名無しさん
06/06/13 15:41:11
DPマッチングの読み間違いとか

206:デフォルトの名無しさん
06/06/13 15:42:01
クイックsortより速いソート挙げて

207:デフォルトの名無しさん
06/06/13 16:07:21
スーパーウルトラデラックスsort

208:デフォルトの名無しさん
06/06/13 16:15:30
基数ソート

209:デフォルトの名無しさん
06/06/13 16:32:32
バケツソート

210:デフォルトの名無しさん
06/06/13 16:33:40
あらかじめソートされたデータだけしか扱わないようにする

211:デフォルトの名無しさん
06/06/13 17:06:19
ソート済みリストをソートしようとしたら
もっとも速く処理が終る(もとと同じリストを吐き出す)ソートは？

212:デフォルトの名無しさん
06/06/13 21:37:45
>>211
挿入ソート、バブルソート
どちらも一回の走査で終了を検出できてO(N)

213:デフォルトの名無しさん
06/06/14 10:40:11
マージソートでは？

214:デフォルトの名無しさん
06/06/15 16:17:06
マージ部分で手を抜くと O(n log n)．
ただ，ちょっと賢くマージをすると O(n) になる．

215:デフォルトの名無しさん
06/06/26 18:41:04

ここで質問してもいいでしょうか？

記号列　S1={aabbbcccceefffggggxxxxyzzzz} S2={xxxyzzzzzzzzqqqqcceeff}　みたいなのがあり、
それぞれの記号列の中で一致している長さX(可変、無限に長くしたい)以上の部分列を全て挙げる

この例では、X=5としたら {cceeff}　{xxxyzzzz} を挙げる。

これを、できるだけ計算量とメモリを節約してやるアルゴリズムは？

それから、このアルゴリズム（この問題）には名前みたいなのあります？

216:デフォルトの名無しさん
06/06/26 20:12:01
名前があるか知らんが、ちょこっと考えたもの
S1とS2の半直線部分文字列を、マージ後ソートして比較する
メモリは、文字列を記憶するメモリ＋文字数×（sizeof(ポインタ)+記号列を特定するIDなど)
速度は、クイックソートでも使えば速そう

半直線部分文字列のソート後には
abbbcccceefffggggxxxxyzzzz(S1)
...
cceeff(S2)
cceefffggggxxxxyzzzz(S1)
...
xxxyzzzz(S1)
xxxyzzzzzzzzqqqqcceeff(S2)
...
zzzzzzzzqqqqcceeff(S2)
てな感じに並んでるかな、文字列がメモリ中にあればポインタだけソートすればOK。任意の長さの一致が全て判明する。

217:デフォルトの名無しさん
06/06/26 21:27:48
{ceeff}とか{cceef}とか{xxxyz}とかは解の候補にならないの？

218:デフォルトの名無しさん
06/06/26 21:30:05
>>215
S1,S2のSuffix　Arrayを生成してからマージするような形で判定していけば良いと思う。
まぁ、ぶっちゃけ>>216のマージとソートの順序が逆になっただけだけど。

219:デフォルトの名無しさん
06/06/26 21:31:11
>>215
Xが何の長さなのかわからんし、何が一致しているのかわからん

総じて何を言いたいのかさっぱりわからん

220:219
06/06/26 21:35:29
すまん、「以上」を読み落としてた

意味はわかったが、アルゴリズムは全然思いつかない

221:デフォルトの名無しさん
06/06/27 12:17:48
マージしてソートってよくわからん。
とりあえずバカ正直な方法は

ａａｂｂｂｃｃｃｃｅｅｆｆｆｇｇｇｇｘｘｘｘｙｚｚｚｚ（s1）
ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ　　　　　（s2_0）
・・・
　　　ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ　　（s2_3）
・・・
ｃｅｅｆｆ　　　　　ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃ（s2_10）

と、一方の文字列をずらしていって、一致する部分を探すことかな。
初めに文字のパターンを調べて、例えば a, b といった文字は片方にしか含まれないから
そういう位置ではパターン検索を省略できるとかくらいかな。

222:215
06/06/27 15:33:41
すみません >>221 と同じく、>>216の方法よくわかりませんでした。
221 だと計算量は |S1|×|S2|×|短い方|　ぐらいなると思うんですが、
216 だともっと計算量減るでしょうか

>>217
それも解候補です。
本当は"極大"な解だけにしたいんですが、今は全部出していいです。

例として aaabbbccc.. なんていうのを出してしまいましたが、
本当はもっとランダムな任意の記号列でやりたいのです。

223:デフォルトの名無しさん
06/06/27 16:01:48
まず、一方の文字列から「辞書」を作る
aabbbcccceefffggggxxxxyzzzz から
a: aabbb, abbbc,
b: bbbcc, bbccc, bcccc
　・・・
y: yzzzz
（説明のために5文字だけだけど、当然、最長パターンまで作っても良い）
次に、もう一方の文字列から、一文字読み込んで、
そこから始まる文字列パターンが「辞書」に登録されてるか調べる。

メモリは食いそうだが、総当たりで調べるよりは少なくなる気がする

224:デフォルトの名無しさん
06/06/27 20:09:13
>>222
処理時間の大部分はソートの時間、クイックソートを使うとして
O(N log(N)) Nは|S1|+|S2|
特殊な例外を除いて計算量は減る。
問題は、文字数×8バイト(32bitマシンで)のポインタ領域が必要なこと

225:デフォルトの名無しさん
06/06/28 09:48:42
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)

マージしてからソートはよくわからなかったから
ソートしてからマージで書いた．きちんと証明してないから
正当性はよくわからん．

Suffix Array の構成は O(n) でできることが知られていて，
マージの部分も同じ文字列を何度も比較するのをやめれば
O( (n+m)*min(n,m) ) でできる．合計して O( (n+m) * min(n,m) )．

226:デフォルトの名無しさん
06/06/28 09:58:26
>>224
長い文字列の比較はそれ自身コストが高いということを忘れてない？

227:デフォルトの名無しさん
06/06/28 16:44:35
>>226
もしかして最後の文字まで比較してると思ってる？

228:デフォルトの名無しさん
06/07/03 06:56:52
最後まで比較せずに済むという保証はどこにもない。

229:デフォルトの名無しさん
06/07/03 12:45:58
>>216
は、n-gram統計における「長尾・森の方法」だな。
岩波のソフトウェア科学の15巻参照
100万字での任意長重複列挙が1秒(Pen-M 1.5GHz)ってとこ。
ソートは文字列専用のソートを利用(単純なクイックソートをちょいと工夫)

>>224や>>228のいう「特殊な例外」（たとえばS1とS2が等しかったり、S1が
S2を包含する場合)では計算量は他の方法並みに大きくなる。

230:デフォルトの名無しさん
06/07/08 16:49:56
大量のエロ動画をRに焼こうと思うが、Rが最小枚数で済む様に最適化するアルゴリズム（もしくは応用できそうなアルゴリズム）ってある？

231:デフォルトの名無しさん
06/07/08 17:04:06
ビン詰め問題とかいう名前であった気がする。
その手の問題は、最適解を見つけるアルゴリズムは見つかってないか、
アルゴリズムが存在しないことが証明されてる（すべての組み合わせを調べるしかない）
ただし、最適解じゃないけど、そこそこ良い組み合わせを得る方法が研究されてる。

232:デフォルトの名無しさん
06/07/08 17:11:33
Hopfieldニューラルネットワークの最適化問題とか。

233:デフォルトの名無しさん
06/07/10 10:27:22
>>230
使える動画を 6 種類ローテで回して、単なる水着を一つ入れておくってどう？
これで一週間回せると思うけど。

234:デフォルトの名無しさん
06/07/10 14:51:21
ナップサック問題とはどう違うの？

235:デフォルトの名無しさん
06/07/10 15:49:37
いわゆる「ナップサック問題」は、袋の最大値が決まってて荷物の総価値が最大にするように選ぶって問題だよね。
荷物を全部入れる必要はない。
この質問は、荷物の全体が決まってて袋の数を最小にするって問題で、荷物を全部入れる必要がある。
だから問題としては違うんじゃないの。
アルゴリズムの本質的なテクニックは同じなのかも知れないけど。

236:デフォルトの名無しさん
06/07/10 18:44:50
どうせRに保存した動画なんてこの先見やしないので、
1枚用意して、そこに全動画を保存したと思い込めばok

237:デフォルトの名無しさん
06/07/10 21:36:04
どなたか、シェルソートとバブルソートの処理時間に差が出る
ことについて初心者でも分かるように説明させて
くださいませんでしょうか？お願いいたします。

238:デフォルトの名無しさん
06/07/10 22:36:14
適当にかき混ぜながらソートするので，
バブルソートや挿入ソートで遅くなるケースを回避しやすいから．

239:デフォルトの名無しさん
06/07/10 23:47:37
もちろん速くなるケースも回避しやすい．

240:デフォルトの名無しさん
06/07/11 07:53:20
で，結局どれくらいになるかは根性で期待値計算すると O(n^{3/2}) とか見えてくる，

241:デフォルトの名無しさん
06/07/11 07:56:35
よって初心者でも分かるように説明するのは無理．

242:デフォルトの名無しさん
06/07/17 16:04:35
以下のような単語がいくつかあった場合、
その全ての組み合わせのパターンを算出
するアルゴリズムってないですか？

カレー餃子牛丼ラーメン

カレー牛丼餃子ラーメン
牛丼餃子ラーメンカレー
・・・
・・・
・・・

243:デフォルトの名無しさん
06/07/17 16:10:44
総当りするしかないだろ。

244:笹井奈琴
06/07/17 16:10:57
>>242
宿題スレの方が

245:デフォルトの名無しさん
06/07/17 16:11:46
std::next_permutation？

246:デフォルトの名無しさん
06/07/17 16:11:57
>>242
ルール説明が雑すぎ

247:デフォルトの名無しさん
06/07/17 16:51:29
>>242
順列の計算習うのって中学だっけ高校だったっけ。

248:デフォルトの名無しさん
06/07/19 19:50:12
様々な大きさの矩形を整列させるアルゴリズムって既に有名な方法があります？

具体的には、横:sx 縦:syの大きさを持つ長方形を、なるべく無駄が出ないように
正方形の中に敷き詰めるような動作です。

//-----------------------------------------------------------------
struct SIZE { int sx; int sy; };
struct POINT { int x; int y; };

const int nBoxCount = 1000;
SIZE box[nBoxCount] = {{10,10}, {7,5}, {3,8}, ...こんな感じで1000個

POINT pos[nBoxCount]; // ←ここに整列後の位置座標を保存する
//-----------------------------------------------------------------

敷き詰め先の正方形のサイズは問いません。
（後でスケールを調整して、0.0～1.0の浮動小数点座標に変換するので）

「なるべく無駄なく」「正方形に」敷き詰める事を重視してます。
とはいえ、整列時に矩形の辺同士を無理にくっつける必要はありません。

上記を満たすようなアルゴリズムが既に存在しているようなら、
そのアルゴリズム名を教えていただけませんか？

（話を単純化させるため、こんな書き方をしましたが、最終的には
　3D空間内全ての４頂点ポリゴンを平面投影し、それらを
　正方形面＝テクスチャUV空間　に敷き詰める動作をさせたいです）

249:デフォルトの名無しさん
06/07/19 19:52:44
遺伝的アルゴリズムでそんな研究が合ったような気がするなあ……

250:デフォルトの名無しさん
06/07/19 20:08:25
>>248
全部の組み合わせを評価するってのはダメなの？
一つの正方形に1,000個落とすって、枠に対する長方形の大きさが小さすぎて、
現実的に意味なくない？　ランダムに落としても、さほど差がないように思う
けれど。

251:デフォルトの名無しさん
06/07/19 20:18:41
なんか、丸の問題なら見たなー
それは、箱の中に数個の点を置きそれをちょっとづつ大きくしてくのだったかな・・・・？
これでやるときは、ランダムに座標を取って、ちょっとづつサイズを大きくしていき
当たり判定で、やるんだっけか？
まあ、プログラミング習ったばっかで読んだから忘れた

252:デフォルトの名無しさん
06/07/19 20:19:55
と書き終わってみたら、長方形じゃ無理か・・・・・

253:デフォルトの名無しさん
06/07/19 20:36:33
ネスティング(Nesting) アルゴリズムで検索してみ
普通は任意形状の配置だけど

254:デフォルトの名無しさん
06/07/19 20:40:36
>>248じゃないけど。

>>250
> 全部の組み合わせを評価するってのはダメなの？

理論的には出来るけど、何通りになると思う？
1000個の長方形を単純に一列にならべるだけで1000! 通り（大きすぎてよくわからん）
各長方形の縦横の向きまで考えれば、上の組み合わせにさらに2^1000をかけたものになる。

255:248
06/07/19 20:47:59
>>249-254の方々、色々な情報ありがとうございました。

>>253
素晴らしいです！
かなりヒントになりました。
この辺キーワードで検索かけまくって、お勉強いたします。

256:デフォルトの名無しさん
06/07/19 20:54:38
Expose?

257:デフォルトの名無しさん
06/07/20 04:06:59
↓こんな処理を考えています。

// 「 former は latter よりも前にこなければならない」という順序付け
struct ordering { int former, latter; };

// M 個の順序付け orderings に基づいて [0, N) の整数を並べ替えた結果を
// sorted に格納する。
// ただし orderings の全ての要素について former != latter であることが
// 保証されており、矛盾する順序付けも含まれていないとする。
void sort_by_ordering_set( int sorted[] , int N
, struct ordering const orderings[] , int M );

・この処理（問題）に、何か良く知られた名前が付いていればおしえてください。
・N, M に対する複雑度はどれぐらいになるでしょうか？
・お勧めのアルゴリズムがあれば教えてください。

ここ数日、仕事の片手間にいろいろ考えているんですが、
速度を無視した実装すらできていません。
今は make のソースでも見たらいいんだろうか、とか思っています。

258:デフォルトの名無しさん
06/07/20 04:34:04
トポロジカルソートでぐぐれ

259:デフォルトの名無しさん
06/07/20 12:46:21
>速度を無視した実装すらできていません。
Javaでやってみました。

void sortByOrderingSet(int[] sorted, int[][] orderings) {
　　boolean[] visited = new boolean[sorted.length];
　　for (int p = 0; p < sorted.length;) {
　　　YET:
　　　　for (int i = 0; i < sorted.length; i++) {
　　　　　　if (visited[i]) continue;
　　　　　　for (int j = 0; j < orderings.length; j++)
　　　　　　　　if (i == orderings[j][1] && !visited[orderings[j][0]])
　　　　　　　　　　continue YET;
　　　　　　visited[sorted[p++] = i] = true;
　　　　}
　　}
}

260:デフォルトの名無しさん
06/07/20 13:38:35
>>257
アルゴリズムの話じゃないが "latter" は "later" に直しとかないと
恥かくんじゃないか？

261:デフォルトの名無しさん
06/07/20 13:59:10
半順序関係ってかっこいいよね

262:デフォルトの名無しさん
06/07/20 14:27:04
>>260
former / latter はごくごく一般的な単語
恥かいてるのはあんただよ

263:257
06/07/21 00:46:55
>>258, >>259
ありがとうございます。道が開けました。

264:デフォルトの名無しさん
06/07/30 09:44:29
おまいら、半順序木からデータを探すとき、どのくらいの時間がかかるますか？
0(n)くらい？それともちょっとくらいは速くできる？

265:デフォルトの名無しさん
06/07/31 01:32:32
半順序木だけでやるなら計算量の意味では O(n) が限界。
ランダマイズとかすると減るかもしれんが。

構築段階から手を加えて良いなら、半順序木に要素が追加されるときに
ハッシュか何かにその要素を追加し、以後木に編集がかかったときに
ハッシュと同期する、とかいうのが常套手段。

266:デフォルトの名無しさん
06/08/08 20:46:26
x が与えられたとき，2^(a+1) > x ≧ 2^a となる 2^a を高速に(ループ等を使わ
ず，できればビット演算のみで)求める方法を探しているのですが，そういうア
ルゴリズムご存じの方いらっしゃらないでしょうか？
言語は C です．

267:デフォルトの名無しさん
06/08/08 20:58:58
それは俺も知りたい。

(int)(log(x)/log(2))
じゃマズいよな。

268:デフォルトの名無しさん
06/08/08 21:35:37
最上位ビット以外を0にすれば良いわけだな。
(x & x-1) ^ x
で最下位ビットが取り出せるので、前後でビットを逆に並べ替えれば良いんだが、
思いつかん。

269:デフォルトの名無しさん
06/08/08 22:48:06
>>266
ビット演算スレがあるから覗いてみたら?

270:デフォルトの名無しさん
06/08/08 22:52:02
>>268
ま、どうでもいいけどx&-xのほうがクール

271:デフォルトの名無しさん
06/08/08 22:59:39
>>270 それだと負の数の表現形式が問題になって嫌な予感。

272:デフォルトの名無しさん
06/08/08 23:08:41
>>266
ビット数決めうちなら以下の手がある(CPU依存の命令使うという手もあるが省略)。
x　|=　x>>1
x　|=　x>>2
x　|=　x>>4
x　|=　x>>8
x　|=　x>>16
x　^=　x>>1

273:デフォルトの名無しさん
06/08/08 23:09:04
>>296
情報有り難うございます．書き込んでみました．

274:デフォルトの名無しさん
06/08/08 23:12:36
>>272
有り難うございます．

定石があるものとばかり思っていたのですが，意外と難しいんですね...
これから解読してみます．

275:272
06/08/08 23:19:30
>>274
実は上のコードはビット演算マニアから言えば定石だったりする。
もし、詳細が知りたければ「ハッカーの楽しみ」という本を読めばいい。
無駄に深い知識を得ることが出来る。

276:デフォルトの名無しさん
06/08/08 23:25:27
>>275
そういえば積ん読してあったなぁ，と思って探してみたら出てきました．
p.51 のやつですね．

理解にかかる時間が節約できそうです．有り難うございました．

277:デフォルトの名無しさん
06/08/09 20:05:19
おまいらマニアつーかヲタクです。

278:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/09 20:51:18
んで、変換対象のデータが複数ある場合はSSE2を使うと。

static const __m128 fp_mask = { 0xFF800000, 0xFF800000, 0xFF800000, 0xFF800000 };

__asm cvtdq2ps xmm0, xmmword ptr [vsrc] ;//32bit整数×4をロードし単精度×４に変換
__asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
__asm cvtps2dq xmm0, xmm0 ;//32bit整数×４に変換
__asm movdqa xmmword ptr [vdest], xmm0 ;//結果をストア

対象データが大量にある場合、まっとうな方法よりこれが一番スループット出るんだよね
ソフトパイプラインでレイテンシ埋めれば完璧。

279:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/09 20:52:44
× __asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア

○ __asm andps xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア

演算結果から言えば同じなんだけど

280:デフォルトの名無しさん
06/08/10 11:13:28
>>279
素朴な疑問なんだけど、その両者の違いは32ビット単位か64ビット単位かってことだよね。
実際のCPUの動きとしては、何か違うの?

それと、対象データが大量にあるなら>278のfp_maskはxmmレジスタにロードした方がいいのかな?

281:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/10 20:32:47
CPUの実装にもよるんじゃないかな。

たとえばCore 2 Duoの技術情報には、SIMD整数命令とSIMD浮動小数命令を
同じレジスタ上で混ぜて使うとペナルティが生じるという趣旨のことが書かれてる。
見映え的にも型に合ってない命令を無闇に混ぜないほうがいいかな、と。

「movapsとmovapdとmovdqaって何が違うんだ？」と思ってロード帯域計ってみた
ことがあるけど、若干差が生じるんだよな、なぜか。
でもCPUによっては生じないかも知れない。

> fp_maskはxmmレジスタにロードした方がいいのかな?

基本的にはそう。
ロード帯域に余裕がある場合は、レジスタを定数1個のために占有するよりは
処理の並列化のために使った方がいい場合も無くはない。

282:280
06/08/11 01:50:01
>>281
なるほど、解説THX。

283:デフォルトの名無しさん
06/08/13 11:31:18
ある２つの文字列が「どの程度同じか」を見つけるアルゴリズムを教えて下さい。
例えば「aあいうえおbbb」と「ccあいうえおeeee」は『大体同じ』と判断したいのです。
この例の場合「あいうえお」の部分が同じな訳ですが、これが「あいうえお」とか
「あいう-えお」でも、「あいうえお」と同じとみなしたいです。
人間が目で見れば、「大体同じ文字列」というのはすぐ分かるのですが、
これをどうやってプログラムで実現すればいいのか・・・

284:デフォルトの名無しさん
06/08/13 11:39:05
LCSとは違うの？

285:デフォルトの名無しさん
06/08/13 12:11:11
>>284
ＬＣＳって何でしょうか・・・？
ググッてもよく分からない・・・

286:デフォルトの名無しさん
06/08/13 12:23:38
Longest Common Subsequence

287:デフォルトの名無しさん
06/08/13 12:43:03
>>286
成る程、深く研究されているんですね・・・
Windows 上で使えるプログラムやライブラリ、
DLL 等があれば教えて下さい。
比較する文字列を 2 つ渡すと、何 % 一致しているかを
返す関数みたいなのがあるといいのですが・・・

288:デフォルトの名無しさん
06/08/13 13:35:09
ライブラリは知らんが、O(nm) の実装なら
URLﾘﾝｸ(en.wikipedia.org)
にある。そんなに複雑ではないので、参考にして書いてみたらどう？

289:デフォルトの名無しさん
06/08/13 16:31:43
Smith-Watermanかな
あとDNA配列の一致を調べるのと似てるからそれ関係を見てみると面白いかも
BLASTとかFASTAとかだっけかな・・・

290:デフォルトの名無しさん
06/08/13 21:37:50
URLﾘﾝｸ(www.topcoder.com)
のアルゴリズム部門に挑戦してみようという人はいないか？

現在、日本は、21位だぞ。
URLﾘﾝｸ(www.topcoder.com)

291:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/13 21:50:09
AGREPはどーよ

URLﾘﾝｸ(www.tgries.de)

292:SOURCE ◆tAo.kQ2STk
06/08/13 23:48:19
>>290-291
英語は苦手だ。

293:デフォルトの名無しさん
06/08/14 00:03:48
インテルで最適化コンテストやってなかったっけ?
#あれだとアルゴリズムレベルでの工夫の余地はないのかな。

294:デフォルトの名無しさん
06/08/14 01:42:06
>>293
でもまあ機械語いじるのもパズル的な部分はあるし面白そう
オレは無理だが

295:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/14 02:00:58
ソースコード読むのに英語か日本語かなんて関係ないだろ

296:・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6
06/08/14 02:01:48
英語のドキュメントが読めないって致命的になるから勉強したほうがいいよ。

297:デフォルトの名無しさん
06/08/14 02:06:51
ﾜﾛpｗｗｗ

298:デフォルトの名無しさん
06/08/14 11:30:45
>296 言語による

299:デフォルトの名無しさん
06/08/14 13:35:15
>>283
URLﾘﾝｸ(hp.vector.co.jp)
は？

経路を記憶するコードを追加すればdiffも簡単にできる。
一致度の%も、定義によって異なってくるが間単に計算できる。

300:デフォルトの名無しさん
06/08/14 14:24:54
>>299
自分でそのコードを書く事は出来そうもないので、>>287 の様な
「比較する文字列を 2 つ渡すと、何 % 一致しているかを返す」
様なツールというか関数を探してます・・・
でもないみたいですね。

301:デフォルトの名無しさん
06/08/14 14:48:05
自分で書けよ……

302:デフォルトの名無しさん
06/08/14 17:48:51
擬似コードが載っているんだから書けるべ。
>299見て書けないならプログラマに向いてないよ。

303:デフォルトの名無しさん
06/08/14 19:27:46
>>300
出鱈目書いてよこすが、こんなもんでいいだろうか？
double cmpstr(char *buf1,char *buf2,int size){
int i,j
j=0;
for (i==0;i>=size-1;i++){
if (buf1[i]==buf2[i]){
j++;
}
}
return j/(size-1);
}

304:デフォルトの名無しさん
06/08/14 19:29:01
あ、最後から2行目
return j/size;
だ。

305:デフォルトの名無しさん
06/08/18 19:20:05
>>300
phpのsimilar_textのソース読んでみてはどうだろう。
O(n^3) くらいだったような気がするが。

306:デフォルトの名無しさん
06/08/21 18:26:00
スローすぎてあくびが出るぜ

307:デフォルトの名無しさん
06/08/21 21:15:47
おまいら自分用のアルゴリズムライブラリとか持ってますか？

308:デフォルトの名無しさん
06/08/22 17:20:55
日本語でおｋ

309:デフォルトの名無しさん
06/08/23 21:44:59
脳内訂正能力の低下が顕著

310:デフォルトの名無しさん
06/08/26 22:50:35
脳内訂正能力を利用した圧縮アルゴリズム

311:デフォルトの名無しさん
06/08/26 23:06:40
昔々、あるところに、おじいさんとおばあんがいました。
おじいさんは山へ芝刈りに、おばあさんは川へ洗濯に行きまた。
おばあさん洗濯をしていると、
大きな桃がどんぶらこっこどんぶらっこと流れてきました。

312:デフォルトの名無しさん
06/08/27 19:34:13
そこで、おばあさんは
「おお、なんと大きな桃じゃ！」
と言い、嬉しそうに丸呑みにしました。

313:デフォルトの名無しさん
06/08/28 00:51:56
>>311
脳内訂正能力を利用した圧縮ですよね？

おばあん　←　１文字圧縮
芝刈り　　←　”柴刈り”を暗号化
行きまた　←　１文字圧縮
おばあさん洗濯　←　１文字圧縮
どんぶらこっこどんぶらっこ　←　１文字圧縮

314:デフォルトの名無しさん
06/08/28 21:51:15
暗号化は意図しない動作でした

315:デフォルトの名無しさん
06/08/29 18:42:20
二次元平面において、線分と単純多角形が与えられたとき、
線分が多角形の内部を通るかどうかを判定する簡単な方法があれば教えてください。

幾つか自分でもやってみたのですが、線分が多角形の端点と重なる場合などで
正しい結果が出ませんでした。どなたかお願いします。

316:デフォルトの名無しさん
06/08/29 19:29:07
>>315
「単純多角形」の定義は何？

317:デフォルトの名無しさん
06/08/29 19:43:53
「多角形の端点」もおかしい。

318:デフォルトの名無しさん
06/08/29 19:51:56
「線分が多角形の端点と重なる場合など」（頂点や辺の意味だろうけど）を
内部を通ることにするかしないか自分の定義しだいじゃないのか？

319:デフォルトの名無しさん
06/08/29 21:24:34
グラフの自動レイアウト関係で参考になるアルゴリズムや考え方はありますか？
重力・斥力でやっているけれどいまいち効率の挙動が悪いんで素。

320:315
06/08/29 21:27:34
>>316
単純多角形とは自己交差を持たない穴の開いていない多角形のことです。
このとき、多角形は境界をなす頂点の列を用いて表現できます。

>>317
単純多角形の境界をなす頂点のことを「端点」と表現しました。

>>318
それを曖昧にしないように、「内部」という言葉を使ったのですが、説明不足でした。
境界と共有点を持つケースは、交わらないと判定したいのです。

よろしくお願いします。

321:デフォルトの名無しさん
06/08/29 22:22:40
>>307
10年以上育ててたのが、HDと共に逝った

322:デフォルトの名無しさん
06/08/29 23:12:41
まず >>318 の言うとおり自分でどういう判定をしたいのか定義する
あとはひたすら図を書いて場合分けするしかないよ

323:デフォルトの名無しさん
06/08/29 23:14:29
>>321 悲惨。それも10年以上。当然、こんなときどうするかバックアップなどのアルゴリズムは考えあるんだろうね？

324:デフォルトの名無しさん
06/08/29 23:55:14
>>315
つURLﾘﾝｸ(www.google.co.jp)

325:デフォルトの名無しさん
06/08/30 00:19:19
>>315
0　　線分の始点が多角形内部にあるときは交差あり
1　　多角形を反時計回りに正規化
2　　多角形の全ての頂点を登録(配列1)
3　　線分の始終点を頂点として登録(配列2)
4　　線分と多角形の交点を(配列1)と(配列2)に新しい頂点として順序良く挿入。
　　ただし別の頂点と重なるときは登録しない。
5　　全ての交点(配列1の点Nと配列2の点Mが同じ座標とする)について、
　　(配列1)の前後の頂点と合わせた３点N-1,N,N+1、(配列2)の頂点Mに着目して
6　　M-1が存在してM→M-1がN-1→N→N+1の左側に出て行く線なら交差あり
7　　同様にM→M+1がN-1→N→N+1の左側に出て行く線なら交差あり
　　 N-1→N→N+1は折れ線の場合もあるので注意。外積と内積を組み合わせて判定。

線分と多角形の辺が頂点以外で交差する典型的ケースをあらかじめ判定してもOK

326:デフォルトの名無しさん
06/09/13 01:29:07
aはビットフラグで、メモリ、FDD、HDD、FANなどの故障状態を表しています。
bは条件です。FDDとHDDが両方故障なら2進で11です。
FDDとHDDが両方故障であるのを得るために2進の11がdefineしてあるのは
変更できませんが、FDDとHDDが両方故障であるのを調べるために
if ( a & b == b )
を実行するのには何か無駄がある気がしますが、もっとよい方法はありますか？

327:デフォルトの名無しさん
06/09/13 01:39:38
>>326
if ((a & FDD) && (a & HDD))

328:デフォルトの名無しさん
06/09/13 02:14:27
>>327
bの値もプログラム中で決定するので327のようにソースに直接書けません。
bを使ったプログラムにします。
bの条件を追加してFDDとHDDとUSBの3つとも故障で2進で111とした場合
もっとよい方法があれば教えてください。

329:デフォルトの名無しさん
06/09/13 02:47:44
>>326
「何か無駄がある気がします」なんて言われたら
どんな答えを出してもそういわれそうな気がして答える気にならない。
具体的に何が不満なんだ？

330:デフォルトの名無しさん
06/09/13 04:11:56
データ構造選んだ時点で
どのアルゴリズムが使えて
どのアルゴリズムが使えないかが決まってくるわけで

331:デフォルトの名無しさん
06/09/13 05:04:37
最適になるようにアルゴリズムとデータ構造を選択するのがプログラマの仕事。

ヒント：青い鳥
だな。理想を求めるのはいいけど、いつまでたっても納品できない悪寒。

ヲレライブラリを失わないためのヲレ危機管理アルゴリズムが不十分だったという検証ができたというヲチか。
バックアップぐらい危機管理の基本中の基本だぜ。

プログラマって人生設計も立てられずに人生のアルゴリズムもなくイベントドリブンで生活してそうだな。

332:デフォルトの名無しさん
06/09/13 05:12:48
なかなか厳しいな～
特にイベントドリブンテところが痛いな～

そんなプログラマに救いの手を♪

333:デフォルトの名無しさん
06/09/13 12:56:27
反復部分文字列の検索アルゴリズムを考えてます。

反復部分文字列とは一つの文字列中に複数回出現する文字列のことで
1.同じ反復部分文字列同士は重なりあわない(ABCABCABC => ABCと抽出 ABCABCは抽出しない)
2.反復部分文字列の部分文字列も反復部分文字列だがそれは抽出しない(ABCDEABCF => ABCと抽出 A B C AB BC は抽出しない)
という条件付きで2回以上出現するもので長さn以上の文字列を検索したいのです。

現在ドットマトリックス(str[i]==str[j]の値の行列を作り対角線方向に検索する方法)による検索しか思いつきませんが何か高速なアルゴリズムはありませんでしょうか？
SEQUITURアルゴリズムをいじれば早くなるかと思ったのですが条件を満たす文字列の一部しか見つけられないので悩んでます。

334:デフォルトの名無しさん
06/09/13 13:19:13
2つの任意の整数の組(a,b)が任意の数だけあるとする。
ただしa<bは常に満たされる。
『例えば「(2,4)(2,3)(1,6)(4,8)」の場合、
(2,4)(2,3)(4,8)は(2,3,4,8)という組を作る。』
というアルゴリズムを考えているのですが、いい方法が全く思いつきません。
分かる方、ヒントをください！

335:デフォルトの名無しさん
06/09/13 13:32:15
ハッシュ辞書使って、検索早めるのはどうよ。
gif なんかの LZW エンコードのソースに書かれているよ。

336:333
06/09/13 13:43:52
>>335
なるほど！圧縮でも部分配列の検索を利用しますね。そちら方面で調べてみます。

337:デフォルトの名無しさん
06/09/13 13:45:10
>>334
意味が今ひとつわからん。
かっこの中の数字のペアを数学で言うところの同値関係と考えて
その同値類に分けた集合をつくるってことか？

338:デフォルトの名無しさん
06/09/13 13:52:17
グラフのレイアウトで参考になるアルゴリズムはありませんか？
ノード間に関係を表すエッジが複数あるとしてランダムに表示されたノードを関係あるものを近くに表示させたいと思っています。
バネモデルなどを使った力学的モデルを使った配置の考え方は見つけたのですが、実行してみるとかなり遅くなってしまいます。
別に見つけた商用ライブラリyFilesのサンプルを使ってみるとあっという間に終わり何か別種のアルゴリズムを使っているとしか思えません。
URLﾘﾝｸ(www.yworks.com)
何か考え方のヒントになるようなものでも助かるので何かないでしょうか。

339:デフォルトの名無しさん
06/09/13 23:14:17
>>326
URLﾘﾝｸ(oshiete1.goo.ne.jp)
ふてぇ野郎だ。

340:338
06/09/14 23:56:30
おしえてGoo煮出してみます。
スレ汚しすいませんでした。

341:334
06/09/15 04:22:02
>>337
ちょっと調べたのですが、同値関係？同値類？という状態です。

いま作ろうとしているのはN体問題に衝突･合体を組み合わせるため、
『どの物体が、どの物体へ衝突したか』
を判定するアルゴリズムです。
衝突したことが直接判定できるのは2つまで(物体a,物体b)で、
3つ以上が同時に衝突する場合、衝突に関与した物体はこの(a,b)の組み合わせから
判断しなければなりません。
「(2,4)(2,3)(1,6)(4,8)」の場合、合体して新たな物体を生じるのは
(2,3,4,8)(1,6)であることを見つけ出そうとしています。

なんだか長くなってしまいましたが、少し自分でも考えてみます。

342:デフォルトの名無しさん
06/09/15 07:53:27
>>341
「衝突・合体」だけだったら Union Find．

分離もしたくなったら，単一要素を分離するだけなら Union Find Split，
接続している要素の切断なら Euler Tour Tree とか Topology Tree とか．

343:デフォルトの名無しさん
06/09/15 20:46:34
>>341
Pythonで作ってみた
（実際の言語固有の便利さを、どこまで使っていいのか良くわからん）

Data = ((2,4), (2,3), (1,6), (4,8))
ResultLists = []
TmpHash = {}

for (X,Y) in Data:
　if not (X in TmpHash):
　　if not (Y in TmpHash): #両方の数字が初めて出てきた場合
　　　　TmpHash[X] = [X, Y] #新しくリストを作成
　　　　TmpHash[Y] = TmpHash[X] #もう一方の数のハッシュを作成
　　　　ResultLists.append(TmpHash[X]) #結果リストに追加
　　else: #片方の数字(X)のみが初めて出てきた場合
　　　　TmpHash[Y].append(X) #既出の数字のハッシュのリストに初めての数字を追加
　　　　TmpHash[X] = TmpHash[Y] #初めての数字のハッシュを作成
　else:
　　if not (Y in TmpHash): #片方の数字(Y)のみが初めて出てきた場合（以下同様）
　　　　TmpHash[X].append(Y)
　　　　TmpHash[Y] = TmpHash[X]

print ResultLists

344:デフォルトの名無しさん
06/09/16 06:12:16
>>343
間違ってる．そのプログラムを
Data = [ (1,2),(2,3), (4,5),(5,6), (3,4) ]
で実行すると
[[1, 2, 3], [4, 5, 6]]
になるが，正しくは
[[1, 2, 3, 4, 5, 6]]
になるべき．

345:デフォルトの名無しさん
06/09/16 07:15:24
Python で作ってみた．Python よく知らんので拙いコードな気がする．

URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)

346:334・341
06/09/17 05:13:19
ありがとうございます！
アルゴリズムの本を何冊か当たっても出なかった問題が
即座に出てくるなんて、2chの中の人すげー
いまからPython勉強します

347:デフォルトの名無しさん
06/09/17 06:35:03
いまだに>>334の数字にペアがなにを表してるかわからない自分は逝ってよしですか・・・orz

348:デフォルトの名無しさん
06/09/17 06:45:33
>>347
・物体 {1, ..., n} がある．
・物体同士の衝突を検査する関数 check(a,b) がある．
・衝突した物体は粘土のように合体する．

という設定で，

衝突している物体対のリスト [ (a_1,b_1), (a_2,b_2), ... , (a_m,b_m) ] が与えられる．
衝突して合体した結果，どのようになるか調べよ．

という問題．

349:デフォルトの名無しさん
06/09/17 09:56:40
C#でやったらこんなんになった。逝ってくる・・・orz
URLﾘﾝｸ(uploader.erv.jp)

350:デフォルトの名無しさん
06/09/17 10:30:32
複数の物体があるとして関係があるもの(これはユーザーの定義などにより設定される)はある程度近くなり、また物体同士で近すぎるものはある程度の距離を保つようにしたいと思います。

ここで計算して少し動かしてまた計算してとやってたんですが、微分積分などを使って一発でやることって可能ですか？

351:デフォルトの名無しさん
06/09/17 20:09:21
>>346
あたる本がよろしくないんだな．
セジウィック「アルゴリズムC」，CLR 「アルゴリズムイントロダクション」など
まともなアルゴリズムの本なら最小全域木との繋がりでたいてい書いてあるよ．

352:デフォルトの名無しさん
06/09/17 20:24:17
>>350
問題設定がよくわからん．
「物体」とか「関係」とか言わずに，どんな問題を解きたいかを
はっきり述べてくれたほうがよい．

問題だけ見ると >>338 と同じような気がするんだが．

353:デフォルトの名無しさん
06/09/18 13:07:51
>>350
３体問題を解決してフィールズ賞取れよ、って言ってるのかな？

簡単にできる場合と難しい場合があることくらいまでは俺にも分かるが、できない場合があることを証明するのは俺には荷が重いな。

354:デフォルトの名無しさん
06/09/18 13:09:27
>>352　あー同じようなもんです。
>>353　やっぱりそういう話ですよね。

355:デフォルトの名無しさん
06/09/18 14:07:45
B木をファイルとして実装する方法で詳しいサイトないですか

356:デフォルトの名無しさん
06/09/18 17:31:47
>>350
じゃあ 352 と同じ問題だと思って回答するぞ．

力学モデルは十分実用的のはずで，小規模系で遅いとしたら
時間刻みが細かすぎるか，用いてる力学モデルが致命的に悪い．
特に時間刻みは重要で，別にシミュレーションするわけじゃないんだから
かなり大雑把に計算しても大丈夫．数値安定性が保たれる限界くらいの
刻みに選んでも平気．

大規模系で遅いとしたら，アルゴリズムの改良が必要．
たとえば高速多重極展開なんかは有力な解決になりうる．

357:デフォルトの名無しさん
06/09/18 17:33:31
352 は 338 のミス

358:デフォルトの名無しさん
06/09/18 20:11:35
>>356
表示しながら収束状況を見てると、ノードが行ったり来たりしてるのは問題外ですよね・・・

359:デフォルトの名無しさん
06/09/19 11:44:17
>>338
こういうのって初期配置も結構重要だと思うんだけど、その辺意識してるのかな？

360:デフォルトの名無しさん
06/09/19 15:07:25
yEdすげー

361:デフォルトの名無しさん
06/09/19 17:46:49
.kjm;:,ok:k,;uhbvxew6te4z64c

362:デフォルトの名無しさん
06/09/20 00:11:27
>355

363:338
06/09/20 01:17:57
>>359
やってるうちに初期配置がかなり重要なことはわかってきました。
今は初期配置をうまくやるアルゴリズムを一つ思いついたので今度試してみるところです。
ただ、初期配置をうまくやってその後収束させる方向が正しいのか、全く違うやり方があるんじゃないかとヒントを探してるところです。

364:デフォルトの名無しさん
06/09/20 09:06:03
>>363
ノードを同心円状に配置するのはどうだろう。
グラフのあるノードを中心として、距離1のノードは半径1の円周上に等間隔に配置。
距離2のノードは半径2の円周上に…という感じ。
この方法で以前試した時は、そこそこうまくいった覚えがあるが、
グラフがツリーに近い形状だったからかもしれない。

力学モデルを使っていて遅いとのことだけど、
パラメータを弄ってやって、最初は移動量を大きくとって大まかな形をつくり、
それから移動量を小さくして微調整すると良いと思う。
もう既にやってるかもしれないしけど…

あと、遅くなる原因としてもう一つ。
これは自分がやったミスで、
収束するのが遅い遅いと思っていて、原因を探るために処理ごとの所要時間を取ってみたら、
実はグラフの収束を確認するための描画に時間がかかっていただけという情けないのもあった。
1回動かすたびに毎回描画なんてしてたから当たり前なんだけど。

次ページ