77コメント27KB

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

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

0001Wirth

NGNG

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

0002デフォルトの名無しさん

NGNG

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

0003デフォルトの名無しさん

NGNG

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

0004デフォルトの名無しさん

NGNG

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

0005デフォルトの名無しさん

NGNG

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

0006デフォルトの名無しさん

NGNG

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

0007デフォルトの名無しさん

NGNG

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

0008デフォルトの名無しさん

NGNG

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

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

0009デフォルトの名無しさん

NGNG

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

0010デフォルトの名無しさん

NGNG

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

001110

NGNG

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

0012デフォルトの名無しさん

NGNG

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

0013デフォルトの名無しさん

NGNG

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

0014デフォルトの名無しさん

NGNG

6の指摘は正しいよ

0015デフォルトの名無しさん

NGNG

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

0016デフォルトの名無しさん

NGNG

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

00178

NGNG

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

0018デフォルトの名無しさん

NGNG

>>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が求まります

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

0019デフォルトの名無しさん

NGNG

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

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

0020ななしさん

NGNG

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

0021デフォルトの名無しさん

NGNG

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

0022デフォルトの名無しさん

NGNG

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

00238

NGNG

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

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

0024デフォルトの名無しさん

NGNG

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

0025デフォルトの名無しさん

NGNG

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

0026デフォルトの名無しさん

NGNG

>>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) あたりをキーに探すとよろし。

0027デフォルトの名無しさん

NGNG

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

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

0028デフォルトの名無しさん

NGNG

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

0029ＳＡＧＥ

NGNG

例えば ABCDEFGHIJK と ABCXYZGHIJK を比較して

ABC
DEF XYZ
GHIJK

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

0030デフォルトの名無しさん

NGNG

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

00318

NGNG

>>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
まさにそういう感じ。

00328

NGNG

お礼を書くの忘れてた。

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

0033デフォルトの名無しさん

NGNG

>>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 ならば情報科学・工学部のあるまともな大学の図書館に行けばあるよ。

00348

NGNG

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

0035デフォルトの名無しさん

NGNG

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

0036デフォルトの名無しさん

NGNG

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

盤は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 ); // 右斜め下

}

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

0037デフォルトの名無しさん

NGNG

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

0038ＳＡＧＥ

NGNG

>>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 );
}

0039デフォルトの名無しさん

NGNG

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

0040デフォルトの名無しさん

NGNG

>>39
わり算

004139

NGNG

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

0042デフォルトの名無しさん

NGNG

CRCの亜種

0043デフォルトの名無しさん

NGNG

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で、偶数奇数その他割とバラけるらしい。ゲーム向きらしい。

004436

NGNG

>>38さん、

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

004539

NGNG

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

0046デフォルトの名無しさん

NGNG

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

0047デフォルトの名無しさん

NGNG

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

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

0048デフォルトの名無しさん

NGNG

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

0049デフォルトの名無しさん

NGNG

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

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

0050デフォルトの名無しさん

NGNG

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

0051デフォルトの名無しさん

NGNG

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

0052デフォルトの名無しさん

NGNG

じゃ、自作のライブラリから引っ張ってきた
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;
}

0053デフォルトの名無しさん

NGNG

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

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

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

0054デフォルトの名無しさん

NGNG

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

0055デフォルトの名無しさん

NGNG

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

005653

NGNG

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

0057デフォルトの名無しさん

NGNG

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

0058デフォルトの名無しさん

NGNG

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

005953

NGNG

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

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

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

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

0060ＶＡＮ

NGNG

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

0061ゆたんぽ

NGNG

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

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

0062なむっこ

NGNG

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

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

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

　　ＡＡＡ
　　ＡＢＢＢ
　　ＡＡＡ

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

0063なむっこ

NGNG

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

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

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

0064なむっこ

NGNG

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

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

0065退化途中

NGNG

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

0066デフォルトの名無しさん

NGNG

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

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

0067デフォルトの名無しさん

NGNG

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

0068なむっこ

NGNG

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

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

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

0069デフォルトの名無しさん

NGNG

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

0070デフォルトの名無しさん

NGNG

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

0071デフォルトの名無しさん

NGNG

優良スレなのでage

0072デフォルトの名無しさん

NGNG

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

0073デフォルトの名無しさん

NGNG

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

0074デフォルトの名無しさん

NGNG

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

0075デフォルトの名無しさん

NGNG

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

0076　　　　　　　　　

NGNG

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

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

0077デフォルトの名無しさん

NGNG

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

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

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

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