【アルゴリズム・データ構造】相談室

アルゴリズム＋データ構造＝プログラム
です。

相談室が流行ってるのか？

そんじゃ、
パトリシア木の長所について教えてください。

>>2
そう、だんです。
さぶっ

このスレは４のお陰で終了しました。
有難うございました。

アルゴリズムの計算量ってどのくらい信用できるものなんですか？
O(n)はnに比例するってだけで比例定数が
100か0.01かではすごい違いがあると思うんですが…

アルゴリズムのオーダーって、係数の値が些細なこととして無視できる
くらい、nの値が大きい場合を想定して比較するものじゃないの？
ただリソースが貧弱だった15年くらい前の本「Programming Pearls」
を見ると、アルゴリズムを比較している表で係数までかかれている。
（3NlogN, 17N^2みたいに）

二つの文字列の一致部分と不一致部分を取り出すアルゴリズムで、
必要用メモリ量がO(M*N)よりも小さいものを教えてください。
速度は遅くなっても構いません。

これだと、テキストがバカ長い場合に、二次元配列の大きさで死にそう
ですよ、カテジナさん。

>>4
昔、ソードオブ相談っていう洋クソゲーがありましたが…

割り算ってどうやって実装してるんですか？
124/12
なんかを計算させるのに、足し算引き算しかできないコンピュータに…

引き算をループさせてるだけじゃむちゃくちゃ遅そう…
剰余の実装も気になる…

>>10 普通の人間が筆算でやるのと同じ方法で実装されてるのが普通だと思うが。

>>6 O(n)は比例定数を比較するもんじゃなくて
中の項で比較するための表記なんで比例定数を比較するのは
ナンセンス。
O(logn)<O(n)<O(n^2)<O(n!)
とかみたく。

6の指摘は正しいよ

いや、6はちょっと大げさすぎるし、13の方が的を得てるぞ。

どちらにせよオーダーだけでアルゴリズムの良し悪しを決定するのはナンセンス。

洩れの質問に答えられる剛の者はおらんのか･･･

>>10
ええと、筆算で求めるように求めてるんだけど
x/y =a 余り b を求めたい時、a=b=0を初期値として
レジスタをNbit幅 とすると
x +(a*y + b)*2^N の両辺を２倍=(x,a,bを２倍)しながら
1. xが2^N 以上なら bを1増やしてxから2^N を減らす
2. b>=y なら aを１増やして bからyを１回除く
という処理をN回繰り返すと
全体が2^Nされます。この時 変数ｘはゼロになります
つまり a*y+b=x初期値となるa,bが求まります

他に定数割算の概算だけ欲しい場合は、掛け算で代用します
余りだけ欲しい場合は２進分解します。

>>10
今時のPCプログラマが除算ルーチンを自分で書くことはないので
忘れてください。

組み込みでZ80を使い続けてる人とかは、まだ俺式乗除算ルーチンを
各人持ってるんですか？

Cが普通だと思う。俺除算なんかしない。
コード生成が把握できてればASMなんか
ちょっとしか書かないね。

じょ、除算ルーチンを自分で作るんですか?

8bitｼﾞﾀﾞｲﾉﾑｶｼﾉｺﾄｻ

なんか、アルゴリズム相談室というよりも、ジジイの昔話スレっぽく
なってきたのでsage。

ちなみに、洩れは>>8の質問を書いたものです。
誰か答えてくださいよ、カテジナさん！
偽春菜の機能拡張に良いアルゴリズムが必要なんです、カテジナさん！

よくわかんないけどBoyer-Moore法とかじゃだめなん？
ttp://www.inet-lab.org/ted/program/prog109.html

>>8
> 二つの文字列の一致部分と不一致部分を取り出すアルゴリズム
スマソ。↑の厳密な定義が想像できなくて・・・

>>8
ん、意図が正確には掴めないね。

D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Comm. A.C.M. 18(6) p341-343, 1975

あたりが使えるのかな。
基本的には Edit Distance を求めるアルゴリズムが使えそうなんで
Edit Distance もしくは Longest Common Subsequence(LCS) あたりをキーに探すとよろし。

みんなすごいなあ、俺なんか、全く意図が掴めないよ >>8 は

diffみたいな処理がしたいのか？　あるいはfileCompみたいな処理？

>> 8
> 必要用メモリ量がO(M*N)
どんな処理にこんなメモリが・・・

例えば ABCDEFGHIJK と ABCXYZGHIJK を比較して

ABC
DEF XYZ
GHIJK

みたいに分割ってことか？ 違うか。

>>8
ギコ猫相談室に同じ話題があるな
http://piza.2ch.net/test/read.cgi?bbs=tech&key=980521175&st=103

>>24
なんか、違う問題のような気が…

>>26
そのキーワードで色々と探してみました。こんなのとか。

Longest Common Subsequences
http://www.ics.uci.edu/~eppstein/161/960229.html

ここのコードを参考に、DBCS対応や不一致文字列の取り出しなんかも
できるコードを書いてみました。

しかし、紹介されているアルゴリズムは一つを除いて全て、O(M * N)のメモリが必要。
例外の一つはLCSの長さだけしか取り出せない(ように見える)。

O(M + N)くらいのメモリ消費で一致部分と不一致部分を全部取り出せる
アルゴリズムってありませんか？

>>27
diffやfcは同じアルゴリズムも文字単位じゃなく行単位で適用してる
んではないでしょうか？

>>29
まさにそういう感じ。

お礼を書くの忘れてた。

ありがとうございます、カテジナさん！

>>31
>しかし、紹介されているアルゴリズムは一つを除いて全て、O(M * N)のメモリが必要。
>例外の一つはLCSの長さだけしか取り出せない(ように見える)。

26で挙げた Hirschberg のやつが正に望むものだと思うんだけど。
31 の挙げたリンク先にも

>In 1975, Dan Hirschberg showed how to find not just the length, but the longest common subsequence itself, in linear space and O(mn) time. The idea is as above.

このように、長さだけでなく LCS もリニアスペースで見付ける、とあるね。
恐らくここで言っているのが 26 で挙げた論文じゃないかな。
中身を正確には覚えていないので自分で読んでみるよろし。
CACM ならば情報科学・工学部のあるまともな大学の図書館に行けばあるよ。

>>33
ありがとうございます。
さっそく探してみますよ、カテジナさん！

ソードオブソダンを買った友人がいたよ。

チェスのクイーンの"利き"(移動範囲)を再帰で表現したい。
クイーンの移動範囲は将棋の飛車、角を合わせたものです。
たて、よこ、ななめ。

盤は8x8です。座標はapplet左上が(1,1)右下が(8,8)です。
/* System.out.println()はデバッグ用で実際はグラフィックです */
で、
public void drawArea( int x, int y ) {
　 System.out.println( x + ", " + y );

　if( x - 1 > 0 ) drawArea( x - 1, y ); // 左よこ
　if( x + 1 < 9 ) drawArea( x + 1, y ); // 右よこ
　if( y - 1 > 0 ) drawArea( x, y - 1 ); // 上
　if( y + 1 < 9 ) drawArea( x, y + 1 ); // 下
　if( x - 1 > 0 && y - 1 > 0 ) drawArea( x - 1, y - 1 ); // 左斜め上
　if( x - 1 > 0 && y + 1 < 9 ) drawArea( x - 1, y + 1 ); // 左斜め下
　if( x + 1 < 9 && y - 1 > 0 ) drawArea( x + 1, y - 1 ); // 右斜め上
　if( x + 1 < 9 && y + 1 < 9 ) drawArea( x + 1, y + 1 ); // 右斜め下

}

終了条件をどうすればよいのかわからないのですが。
このままだとスタックオーバーフローです。

>>35
ほぅ…。それは興味深い。ぜひ感想を聞かせてもらいたいものだ。

>>36
なんかそれじゃあ盤面全部埋め尽くしません？

public void drawArea( int x, int y ) {
　drawLinearArea( x, y, -1, -1 ); //左上
　drawLinearArea( x, y, -1, 0 ); // 左
　drawLinearArea( x, y, -1, 1 ); // 左下
　drawLinearArea( x, y, 0, -1 ); // 上
　drawLinearArea( x, y, 0, 1 ); // 下
　drawLinearArea( x, y, 1, -1 ); // 右上
　drawLinearArea( x, y, 1, 0 ); // 右
　drawLinearArea( x, y, 1, 1 ); // 右下
}

public void drawLinearArea( int x, int y, int dx, int dy ){
　if( x<1 || 8<x || y<1 || 8<y )
　　return;
　System.out.println( x + ", " + y );
　drawLinearArea( x+dx, y+dy, dx, dy );
}

16BitCPUで使える、
早くてコンパクトな乱数生成アルゴリズムを教えてちょ。

>>39
わり算

>>40
わけわかんない(T T)

CRCの亜種

static uint16 last_rnd = 0;

uint16 random_next(void)
{
　　last_rnd ^= 0x9630U;
　　last_rnd -= 0x6553U;
　　last_rnd = (last_rnd << 2) | (last_rnd >> 14);
　　return (uint16) last_rnd;
}

昔fj.lang.cだったかで見たやつ。
クロサワ式乱数（自称）とか言うらしい。
周期2^16で、偶数奇数その他割とバラけるらしい。ゲーム向きらしい。

>>38さん、

ありがとうございます。
いま実行して望み通りに動くことを確認しました。
再帰という考え方が苦手なのでこれからじっくり考えます。

うおっ。これすげｰ。
テーブル使わないんですね。
感激しました。
ありがとー＞43

>>43
定数がどっから出てきたのかに、ちと興味あり。

>>46
ひたすら大量の実験を繰り返した結果によるものらしいです（コード自体が）。
確かに、なかなか美しいばらけっぷりだったので
68の同人ソフトに使わせてもらいました。

今のPCなら大人しくめるせんぬついすたーを使うかな。

>>43の乱数は種は無いの？

クロサワ乱数なんて使ってるヤツは糞、広めるヤツは死刑。
Pset( Rand(), Rand() )とかしてみろ。

「クロサワ乱数は規則性に優れており、Ｍ系でも最低レベルに値します。
標準関数使ったほうが１億倍マシです」

>標準関数使ったほうが１億倍マシです
だって>>39の前提条件があるんだもん。

標準関数のは、M系列乱数にすらなってなかったりするので頭が痛いナリよ。
ま、Mersenne Twisterあたりでも使えばいいナリが。

じゃ、自作のライブラリから引っ張ってきた
static unsigned　randbuf[4]={0x1234,0x5678,0x9abc,0xdef0};
unsigned　rand16(void) // p=55 τ=55-7=48
{
static unsigned　rw=3;　　　　　　　　　 /* 上位Wordから 開始　 */
　　unsigned　topb　=randbuf[rw　];　　　/*最上位wordを取り出し */
　　unsigned　nw=(rw+4-1) & 3;　　　　　 /*次はその右隣　　　　 */
　　unsigned　nextb =randbuf[nw　];　　　/*右隣を取り出し　　　 */
　　topb　= (topb<<9)|( nextb>>(16-9) ); /*ビット位置を合わせる */
　　topb^=nextb;
　　topb&=0xffff;　　　　/* 16bitでない処理系でテスト出来るよう */
　　randbuf[rw]=　topb ; /*新しいMSBwordとして格納　　　　　　　*/
　　　　　　rw =nw;　　　/*読書点を右隣に移動　　　　　　　　　 */
return　topb;
}

二つの文字列 A と B に共通する全ての部分文字列を抜き出したいんだけど、どうやればいい？

--abc--defgh------
---def--fgg--abc--

なら abc, def, fg が出てるくようなの。

a,b,c,ab,bc,d,e,de,ef,f,g も出てくるの?

条件はないの？なるべく高速にとか、遅くてもいいから
メモリを使わないようにとか。

あ、出てきます。
実際にはあんまり短かいのはいらないですけど。

>>53
順番が違う部分文字列も抜き出したいの？
最長部分文字列の抽出コードなら、ここにあるけど。
http://www.ics.uci.edu/~eppstein/161/960229.html

>19
Palmで使われているDragonBallはCPUが除算をサポートしていないみたいです。

ごめんなさい、さっきはリロードの加減で55読んでなかったっす。

>>55
＞条件はないの？なるべく高速にとか、遅くてもいいから
＞メモリを使わないようにとか。

両方とも欲しいです。
どちらかというと速い方が欲しい。
やりたいのは全ての共通部分文字列とその頻度をリストアップする事です。
まじめに考えるとけっこう大変そうなので既に方法があれば頼りたいです。

>>57
ありがとです。
ちょっと見てきます。

アルゴリズムで分からないですが。ランパートってゲームご存知でしょうか。
ブロックで自分の城を囲んだ後に相手の船を撃沈するゲーム。
ブロックが城を囲んだ、というのを判断するにはどういう風に組めばよいのでしょうか。
超初心者ですみません。できればCで教えていただければ幸いです。

>>53
全ての半直線文字列をソートして比較する
速度は利用するソートアルゴリズム次第
1000万文字×1000万文字で5分は切れると思います(PIII 500MHz)
必要メモリは全てのテキストを読み込む領域＋
ポインタサイズ×文字数＋α

もっと速いアルゴリズムもあると思いますが、ここ数年
テキスト処理から遠ざかっているので分かりません。

Mr.ﾄﾞﾘﾗｰもどきを作りたいんですけど、
ブロック落下のアルゴリズムはどうすれば最適なんでしょうか？

do {
　for (下から順番) {
　　proc(繋がっているブロックを可能なら、１ステップ落とす)
　}
} while (ブロックが１つでも落ちた)

今のところこの手順でやってますが、

　　ＡＡＡ
　　ＡＢＢＢ
　　ＡＡＡ

こういう配置の場合困ってしまうんですよね。。。
（このパターンでもっと複雑な場合もある）

ブロック１つ１つの落下判定がポイントだとは思うのですが、
今のところ
　　１つ下が空き＝落下可能
　　１つ下が同じ色＝更に再帰で調べる
　　１つ下が違う色＝落下不能

という単純な方法で調べてます。でもこれに処理を入れすぎると重くなるし・・・

凄腕プログラマのみなさんおたすけお。

>>60
ランバートは知らないですが、囲まれてるかどうかチェック出来たらいいんですよね？
塗りつぶしと同じでは？ここらへん参照。
ttp://www.people.or.jp/~fussy/argo.htm
チェック時に１度でもフィールド外まで出れば囲まれていないと判定。
ナナメ方向にも完全に囲まれてる必要があるなら、ナナメのチェックも追加すればＯＫ。

うちの問題も誰かヒント教えてください。。。

ランパートは知りません。
迷路を探す右手法で解決すると思います
ブロックを壁と見立てて、城から出発します。
壁にあたれば、その位置を記録し、
そこから右手を常に壁につけるように移動。
最初に壁に接触した位置に戻れば閉じている
途中で外に出れば閉じてない

>>62
こんなのしか考え付きませんでした。

proc(絶対に落ちないブロックに印つけとく)
do {
　for (下から順番、印のついてないブロック) {
　　if (繋がってるブロックが、印付きブロックに乗っかってるか) {
　　　proc(そのブロックにも印つける)
　　}
　}
} while (ブロック全部)
proc(印のついてないブロックを全部１ステップ落とす)

>>61
なるほどなるほど。
でもソートした後の処理なんかが面倒そうっす。
自己マッチをどう排除するとか。
でも面白そうだからちょっと考えてみる。

>>66
おお！ありがとう御座います。
試してみると、うまくいきました！

私は考え方が逆でしたね。
落下させるべきブロックの事ばかり考えてました（汗

今は落下前のぐらぐらを実装中。。。
ぐらぐら中に同色ブロックが横を通過したら・・とか結構ややこしいッス。
作業前は「簡単簡単！」と思っていたのですが(;´Д`)ァゥァゥ

つながってるブロックのうちひとつでも下に自分の一部でない
他のブロックがある場合は落ちない
で、いいんですかね？

>>67
文字列1由来の部分列だったら尻尾に1を、
文字列2由来だったら2をつければいいです。

優良スレなのでage

昔使ってた乱数発生器
　A = A*5+1 % 256
お手軽だよ。規則性は保証つき。一応0〜255全部使うし。

"(A*5 + 1) % 256"?

なにがわからないんだ?>73

あげちゃった
どうしよ・・・

すいません。
Visio, Tgif, DIAなどなど
ああいったドローツール／カードツールでは
ツリー型のリストとコールバックのような仕組みを利用しているのでしょうか？
たとえばWindowsの親ウィンドウと子ウィンドウのように

ソースみたほうがはやいですか？

>ツリー型のリストとコールバックのような仕組み

それはもしかして、今風(藁)の言い方に翻訳すると、
「Compositeデザインパターンと仮想メソッドによる多態」
つまり「メッセージの伝播」って話を
言いたかったのかな？

というわけで、OOP憂鬱本読むと幸せになれるぞきっと。