アルゴリズムオタク
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2006/03/07(火) 23:06:03エレベーターを待っているときは、動きを制御するアルゴリズムを考えたり
既存のサブルーチンのアルゴリズムを考えたり、ゲームをやってても敵の
動きのアルゴリズムを考え、ストーリーなどは全く頭に入らない
愛読書は「アルゴリズムとデータ構造？」
言語なんて関係ない！アルゴリズムが好き！
0153デフォルトの名無しさん
2006/05/01(月) 21:28:18研究用途ならそういう結論になるかもしれないな。
だが計算量を記述できなければ実用の道をほとんど閉ざすことになる。
0154137
2006/05/01(月) 21:38:14どれくらい頑張れるかは不明な場合が多いのです。
私は仕様を書いたら即動くものができるというようなことは考えていません。
実装する際に何らかの役に立てばいいと思っています。
0155デフォルトの名無しさん
2006/05/01(月) 21:48:480156デフォルトの名無しさん
2006/05/01(月) 22:00:19世の中にはスピードが問題になることも多々あるわけだが。
理論上は可能、ただし、処理に１０億年掛かります、とかね。
そもそも仕様が適当すぎ。荒らしに来たとしか思えない。
0157デフォルトの名無しさん
2006/05/01(月) 22:02:12このスレ(の住人)に何を求めてるの？
0158137
2006/05/01(月) 22:14:20原理的にＰＡＳＣＡＬでかけないものなんて無いでしょう。
もうちょっと楽にならないかなという程度のことです。
>>156
スピードを仕様に盛り込んだとしても達成できなければ意味が無いのです。
たとえばソートをO(logn)でやれといっても無理な話です。
結局できることといったら存在する実装から一番いいものを選ぶだけなんです。
>>157
まあ、一緒になって考えていただければ。
0159デフォルトの名無しさん
2006/05/01(月) 22:38:10このひとが全然アルゴリズムを理解していないことが分かる。
0160137
2006/05/01(月) 22:45:07解くべき問題を記述したいのです。
ソートには色々な計算量のソートがありますが、目的はどのソートも同じです。
その同じな部分を扱いたいのです。
0161デフォルトの名無しさん
2006/05/01(月) 22:56:440162デフォルトの名無しさん
2006/05/01(月) 23:02:520163デフォルトの名無しさん
2006/05/02(火) 00:12:14>まあ、一緒になって考えていただければ。
情報を小出しにし、わけの分からない仕様を提示し、アルゴリズムの話ですらないのに
その上、出て来た意見を片っ端から否定しといて「一緒になって」も無いだろ
0164137
2006/05/02(火) 00:16:19リップサービスと言う言葉の意味を考えてみたらどうだ?
0165デフォルトの名無しさん
2006/05/02(火) 00:16:350166デフォルトの名無しさん
2006/05/02(火) 00:32:180+0=0
0+1=1
1+0=1
1+1=0
だけであらゆるプログラムを作れるんだろうな。
0167デフォルトの名無しさん
2006/05/02(火) 02:33:34http://pc2.2ch.net/test/read.cgi/tech/1013507313/l50
こういうスレが欲しかったんだろ？ さあ逝ってきな
0168デフォルトの名無しさん
2006/05/05(金) 13:02:09対応する十進数（例えば[4バイトBCD] × [10のN乗|Nは1バイト符合付き整数]）
に変換するのはどうしたらいいかな。
当然、与えられた浮動小数の符合付き整数部のMSBは1に、
結果のBCDの最上位ニブルは0以外に正規化（？）されているものとする。
8ビットマイコンのアセンブラ想定でよろしく。
0169デフォルトの名無しさん
2006/05/05(金) 13:18:25どっちかいうと実装テクニックじゃない
0170デフォルトの名無しさん
2006/05/05(金) 14:53:07アルゴリズムとそうでないものの違いは「俺様が関心があるかどうか」
の違いではないでしょうw
0171デフォルトの名無しさん
2006/05/05(金) 14:55:270172デフォルトの名無しさん
2006/05/05(金) 14:56:09a*2^N = a*b*10^M とやって正規化するくらいだね
0173デフォルトの名無しさん
2006/05/07(日) 18:59:040174デフォルトの名無しさん
2006/05/07(日) 22:05:07希に「そこを自分で考えるのが楽しいんだろ」ていう部分を
メーリングリストや掲示板で「どうやったらいいんでしょうか？」とかって
訊いてくるヤツのことがサッパリ理解できない。
0175デフォルトの名無しさん
2006/05/08(月) 01:00:24そこを自分で考えるのが楽しいんだろ？
0176デフォルトの名無しさん
2006/05/08(月) 15:13:52そういうレスを返すヤツのことがサッパリ理解できない。
0178デフォルトの名無しさん
2006/05/11(木) 18:47:21なかなかいい構造が思いつかない。
0180デフォルトの名無しさん
2006/05/12(金) 12:43:470181デフォルトの名無しさん
2006/05/12(金) 19:21:090182デフォルトの名無しさん
2006/05/25(木) 12:15:420183デフォルトの名無しさん
2006/06/08(木) 07:52:46はい背の順に整列！
って時さ、
全員がクイックソート理解してたと仮定して、その通りに整列してもらうより
普通に整列させた方が速そうじゃない？
モデル化すると、要素全てが各々同時並列的に他の任意の要素の値を知れる場合
そして要素が同時並列的に移動できる場合
0184デフォルトの名無しさん
2006/06/08(木) 08:47:32大雑把にソートした列に、後はデータ自身が自分の入るべき場所を見つけて両側のデータに対して
スペースを作るように要求する感じかね。
オブジェクト指向のいいテストケースになりそうだが。
0185デフォルトの名無しさん
2006/06/08(木) 15:51:28脳はだいたい基数ソートみたいなことをしているんだってさ
0186デフォルトの名無しさん
NGNG周りのオブジェクト全部をみて整列する人はまずいない。
だいたい自分がどのくらいの序列になるか予想して、整列の初期には近くにいる数人の
オブジェクトのうち同じくらいの序列になる物同士で小グループを形成し、グループ内での
序列を決定した後に他の小グループと合体、境界付近を調整する。
小グループ同士が合体したあとにオブジェクトが余っている場合も、自分の序列がどれくらい
かを予想してそこに近い部分集合の中から自分の序列を決定する。
つーわけで、段階的にマージソートと挿入ソートを同時多発的にやっているような気がする。
0187デフォルトの名無しさん
2006/06/08(木) 18:33:14>同じくらいの序列になる物同士で小グループを形成し
これがマージソートと根本的に違うところ．
簡単のため小グループとして「背の低いグループと背の高いグループ」
を取って，それぞれで再帰的に計算してやることにする．
マージソートだと，それぞれをソートした結果をマージするときに
前半のトップと後半のトップを比較して云々とやらないといけなくて，
マージの部分の計算量が O(n) になり，合計として O(n log n) になる．
しかし，「普通に整列」の場合は前半のほうが後半よりも小さいと
わかっているので単純にくっつければよく，マージの部分の計算量が O(1) ですむ．
その結果，合計として O(n) でソートできるようになる．
0188187
2006/06/08(木) 18:37:48自分の経験から小さい人は前，大きい人は後ろに行って，そこでソート
をやってるもんだと思いこんでいた．
その逆の近くに居る人たちから結合することを考えていたのか．申し訳ない．
＃多分それでも「合体」の部分で適当にオラクルが利いて O(n) になるとは思うが
0189デフォルトの名無しさん
2006/06/08(木) 21:38:20最初の移動は粒度の荒いバケツでバケツソートってことになる。
バケツ内での並び替えはどうやってるんかな。
100人の場合と1000人の場合で実験してみないとなんともいえないが・・・
0190デフォルトの名無しさん
2006/06/09(金) 00:23:260191デフォルトの名無しさん
2006/06/09(金) 07:50:53１）全生徒はそれぞれ「自分及び他人が（同年代の中で）どの程度の背の高さか」を感覚的に知っている。恐らくはクラスの背の順等の経験から。１０％程度の粒度で。
２）全生徒はそれぞれ個別に（＝同時に）自分が特定の他者より高いか低いかを判断してそれらしい位置に移動することが出来る。
３）数が多くなればなるほど、身長の近い者が逆順に並んでいても問題にしない。
以上の要因から、ＣＰＵ一個が無情報で正確にソートしなければならないことを前提としたアルゴリズムに時間的に優っているのである。
0192デフォルトの名無しさん
2006/06/09(金) 09:57:163)に関しては相手にお前何センチって聞けばいんじゃね
0193デフォルトの名無しさん
NGNG機械がやる場合、たとえば標準偏差を与えて記憶や経験の代わりに予想の根拠とすることは
できるような気がする。
0194デフォルトの名無しさん
2006/06/09(金) 11:53:31・頭が n 個あるので log n 時間で整列が可能。
・人間が寝ている場合には、 n 台のロボットを使って log n 時間で整列可能。
ただし、
n が大きくなってくると、入れ替えるために移動させるためにかかる時間の方が
支配的になってくるので、O(n) になる。
0195デフォルトの名無しさん
2006/06/09(金) 20:29:46線形探索や二分探索という位置決めがデータによらない手法に対して、
データの種類によって次の探索位置を変える内挿探索という手法がある。
0196デフォルトの名無しさん
2006/06/09(金) 21:22:52もしその２直線が交点を持つなら、
交点を計算するアルゴリズムってどうなりますか？
２次元平面上での交点計算みたいに方程式作ってもうまくいかないんですが・・・
なんかヒントくれるとありがたいです。
0197デフォルトの名無しさん
2006/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座標の式にいれてすべての座標が一致するかどうか確かめる。
0198デフォルトの名無しさん
2006/06/09(金) 21:40:16先に2次元で解いておいて、3次元にしてもOKか見るわけですね。
なんか頭混乱してて、こんなこともわからなかったです・・・
ありがとうございました。
0199デフォルトの名無しさん
2006/06/09(金) 21:52:390200デフォルトの名無しさん
2006/06/09(金) 22:05:540201デフォルトの名無しさん
2006/06/09(金) 22:25:300202デフォルトの名無しさん
2006/06/10(土) 16:23:04(最大値 - 俺の値)/(最大値 - 最小値)
で数直線上の何%くらいに位置するか検討をつけ、
この場合は身長の分布を思い出して、区間の人数割合を想像してから
自分の属する区間あたりにまず向かう。
適当に整列されて来たら
自分より背の高い奴がすぐ前にいればそいつの前に出る。
0203デフォルトの名無しさん
2006/06/12(月) 21:23:27質問なんだけど、BPマッチングっていうアルゴリズムって存在する？検索してもそれらしいのがヒットしないんだが
0204デフォルトの名無しさん
2006/06/13(火) 01:30:010205デフォルトの名無しさん
2006/06/13(火) 15:41:110206デフォルトの名無しさん
2006/06/13(火) 15:42:010207デフォルトの名無しさん
2006/06/13(火) 16:07:210208デフォルトの名無しさん
2006/06/13(火) 16:15:300209デフォルトの名無しさん
2006/06/13(火) 16:32:320210デフォルトの名無しさん
2006/06/13(火) 16:33:400211デフォルトの名無しさん
2006/06/13(火) 17:06:19もっとも速く処理が終る(もとと同じリストを吐き出す)ソートは？
0212デフォルトの名無しさん
2006/06/13(火) 21:37:45挿入ソート、バブルソート
どちらも一回の走査で終了を検出できてO(N)
0213デフォルトの名無しさん
2006/06/14(水) 10:40:110214デフォルトの名無しさん
2006/06/15(木) 16:17:06ただ，ちょっと賢くマージをすると O(n) になる．
0215デフォルトの名無しさん
2006/06/26(月) 18:41:04ここで質問してもいいでしょうか？
記号列 S1={aabbbcccceefffggggxxxxyzzzz} S2={xxxyzzzzzzzzqqqqcceeff} みたいなのがあり、
それぞれの記号列の中で一致している長さX(可変、無限に長くしたい)以上の部分列を全て挙げる
この例では、X=5としたら {cceeff} {xxxyzzzz} を挙げる。
これを、できるだけ計算量とメモリを節約してやるアルゴリズムは？
それから、このアルゴリズム（この問題）には名前みたいなのあります？
0216デフォルトの名無しさん
2006/06/26(月) 20:12:01S1とS2の半直線部分文字列を、マージ後ソートして比較する
メモリは、文字列を記憶するメモリ＋文字数×（sizeof(ポインタ)+記号列を特定するIDなど)
速度は、クイックソートでも使えば速そう
半直線部分文字列のソート後には
abbbcccceefffggggxxxxyzzzz(S1)
...
cceeff(S2)
cceefffggggxxxxyzzzz(S1)
...
xxxyzzzz(S1)
xxxyzzzzzzzzqqqqcceeff(S2)
...
zzzzzzzzqqqqcceeff(S2)
てな感じに並んでるかな、文字列がメモリ中にあればポインタだけソートすればOK。任意の長さの一致が全て判明する。
0217デフォルトの名無しさん
2006/06/26(月) 21:27:480218デフォルトの名無しさん
2006/06/26(月) 21:30:05S1,S2のSuffix Arrayを生成してからマージするような形で判定していけば良いと思う。
まぁ、ぶっちゃけ>>216のマージとソートの順序が逆になっただけだけど。
0219デフォルトの名無しさん
2006/06/26(月) 21:31:11Xが何の長さなのかわからんし、何が一致しているのかわからん
総じて何を言いたいのかさっぱりわからん
0220219
2006/06/26(月) 21:35:29意味はわかったが、アルゴリズムは全然思いつかない
0221デフォルトの名無しさん
2006/06/27(火) 12:17:48とりあえずバカ正直な方法は
ａａｂｂｂｃｃｃｃｅｅｆｆｆｇｇｇｇｘｘｘｘｙｚｚｚｚ（s1）
ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ （s2_0）
・・・
ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ （s2_3）
・・・
ｃｅｅｆｆ ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃ（s2_10）
と、一方の文字列をずらしていって、一致する部分を探すことかな。
初めに文字のパターンを調べて、例えば a, b といった文字は片方にしか含まれないから
そういう位置ではパターン検索を省略できるとかくらいかな。
0222215
2006/06/27(火) 15:33:41221 だと計算量 は |S1|×|S2|×|短い方| ぐらいなると思うんですが、
216 だともっと計算量減るでしょうか
>>217
それも解候補です。
本当は"極大"な解だけにしたいんですが、 今は全部出していいです。
例として aaabbbccc.. なんていうのを出してしまいましたが、
本当はもっとランダムな任意の記号列でやりたいのです。
0223デフォルトの名無しさん
2006/06/27(火) 16:01:48aabbbcccceefffggggxxxxyzzzz から
a: aabbb, abbbc,
b: bbbcc, bbccc, bcccc
・・・
y: yzzzz
（説明のために5文字だけだけど、当然、最長パターンまで作っても良い）
次に、もう一方の文字列から、一文字読み込んで、
そこから始まる文字列パターンが「辞書」に登録されてるか調べる。
メモリは食いそうだが、総当たりで調べるよりは少なくなる気がする
0224デフォルトの名無しさん
2006/06/27(火) 20:09:13処理時間の大部分はソートの時間、クイックソートを使うとして
O(N log(N)) Nは|S1|+|S2|
特殊な例外を除いて計算量は減る。
問題は、文字数×8バイト(32bitマシンで)のポインタ領域が必要なこと
0225デフォルトの名無しさん
2006/06/28(水) 09:48:42マージしてからソートはよくわからなかったから
ソートしてからマージで書いた．きちんと証明してないから
正当性はよくわからん．
Suffix Array の構成は O(n) でできることが知られていて，
マージの部分も同じ文字列を何度も比較するのをやめれば
O( (n+m)*min(n,m) ) でできる．合計して O( (n+m) * min(n,m) )．
0226デフォルトの名無しさん
2006/06/28(水) 09:58:26長い文字列の比較はそれ自身コストが高いということを忘れてない？
0227デフォルトの名無しさん
2006/06/28(水) 16:44:35もしかして最後の文字まで比較してると思ってる？
0228デフォルトの名無しさん
2006/07/03(月) 06:56:520229デフォルトの名無しさん
2006/07/03(月) 12:45:58は、n-gram統計における「長尾・森の方法」だな。
岩波のソフトウェア科学の15巻参照
100万字での任意長重複列挙が1秒(Pen-M 1.5GHz)ってとこ。
ソートは文字列専用のソートを利用(単純なクイックソートをちょいと工夫)
>>224や>>228のいう「特殊な例外」（たとえばS1とS2が等しかったり、S1が
S2を包含する場合)では計算量は他の方法並みに大きくなる。
0230デフォルトの名無しさん
2006/07/08(土) 16:49:560231デフォルトの名無しさん
2006/07/08(土) 17:04:06その手の問題は、最適解を見つけるアルゴリズムは見つかってないか、
アルゴリズムが存在しないことが証明されてる（すべての組み合わせを調べるしかない）
ただし、最適解じゃないけど、そこそこ良い組み合わせを得る方法が研究されてる。
0232デフォルトの名無しさん
2006/07/08(土) 17:11:330233デフォルトの名無しさん
2006/07/10(月) 10:27:22使える動画を 6 種類ローテで回して、単なる水着を一つ入れておくってどう？
これで一週間回せると思うけど。
0234デフォルトの名無しさん
2006/07/10(月) 14:51:210235デフォルトの名無しさん
2006/07/10(月) 15:49:37荷物を全部入れる必要はない。
この質問は、荷物の全体が決まってて袋の数を最小にするって問題で、荷物を全部入れる必要がある。
だから問題としては違うんじゃないの。
アルゴリズムの本質的なテクニックは同じなのかも知れないけど。
0236デフォルトの名無しさん
2006/07/10(月) 18:44:501枚用意して、そこに全動画を保存したと思い込めばok
0237デフォルトの名無しさん
2006/07/10(月) 21:36:04ことについて初心者でも分かるように説明させて
くださいませんでしょうか？お願いいたします。
0238デフォルトの名無しさん
2006/07/10(月) 22:36:14バブルソートや挿入ソートで遅くなるケースを回避しやすいから．
0239デフォルトの名無しさん
2006/07/10(月) 23:47:370240デフォルトの名無しさん
2006/07/11(火) 07:53:200241デフォルトの名無しさん
2006/07/11(火) 07:56:350242デフォルトの名無しさん
2006/07/17(月) 16:04:35その全ての組み合わせのパターンを算出
するアルゴリズムってないですか？
カレー 餃子 牛丼 ラーメン
カレー 牛丼 餃子 ラーメン
牛丼 餃子 ラーメン カレー
・・・
・・・
・・・
0243デフォルトの名無しさん
2006/07/17(月) 16:10:440245デフォルトの名無しさん
2006/07/17(月) 16:11:460246デフォルトの名無しさん
2006/07/17(月) 16:11:57ルール説明が雑すぎ
0247デフォルトの名無しさん
2006/07/17(月) 16:51:29順列の計算習うのって中学だっけ高校だったっけ。
0248デフォルトの名無しさん
2006/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空間 に敷き詰める動作をさせたいです）
0249デフォルトの名無しさん
2006/07/19(水) 19:52:440250デフォルトの名無しさん
2006/07/19(水) 20:08:25全部の組み合わせを評価するってのはダメなの？
一つの正方形に1,000個落とすって、枠に対する長方形の大きさが小さすぎて、
現実的に意味なくない？ ランダムに落としても、さほど差がないように思う
けれど。
0251デフォルトの名無しさん
2006/07/19(水) 20:18:41それは、箱の中に数個の点を置きそれをちょっとづつ大きくしてくのだったかな・・・・？
これでやるときは、ランダムに座標を取って、ちょっとづつサイズを大きくしていき
当たり判定で、やるんだっけか？
まあ、プログラミング習ったばっかで読んだから忘れた
0252デフォルトの名無しさん
2006/07/19(水) 20:19:55■ このスレッドは過去ログ倉庫に格納されています