データ構造のアドバイスをお願いします。


2×2の格子の辺の数は全部で12本になります。
辺は「ある」か「ない」かの2つの状態をとります(4048(2の12乗)通り)
ここでさらに
・90,180,270度回転
・上下、左右反転
の状態を重複チェックするのに最適なデータ構造を思いつけません。

■データ自体のシンプルさ
に加えて
■計算上シンプル
であることを考慮した気の利いたデータ構造はありませんか?

具体的なアドバイス(200ポイント以上用意しています)の他に、
データ構造の基本がわかっていないので、格子のデータ構造を詳しく説明しているサイトのリンクなども歓迎します。

ちなみに、以下よりはマシなものがあると期待しての質問になります。
●始点座標、終点座標の組み合わせ(始xy終xy,始xy終xy,..)例(0010,0110,1121,....)など
●中心座標と方向(x座標y座標方向,x座標y座標方向,....)例(103,111,214,...)など
●辺に番号をつける(辺1,辺2,・・・,辺12)例--(11000000000)など

回答の条件
  • 1人3回まで
  • 登録:2007/03/10 00:22:57
  • 終了:2007/03/17 00:25:02

回答(6件)

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112007/03/10 06:24:53

ポイント19pt

3点×3点(2辺×2辺)固定で、静的構造でいきたいなら、中心を原点にして、時計回りの原則で辺に2次元の番号をつけると思います。

漢字だと逆回りになりますが(それでもいいけど趣味の問題)以下のごとく。

(0,0)(0,1)(0,2)(0,3)が(十)

(1,0)(1,1)(1,2)(1,3)が加わって(卍)、

(2,0)(2,1)(2,2)(2,3)が加わって格子(田)

それぞれが値を持つのなら2次元の配列で扱う。こうすれば反転や回転の同一性がみやすいかなと。

4点×4点(3辺x3辺)以上に拡張することを将来想定するなら、上記の手は破綻しそうなので、□を単位として、あえて16本に増やしたデータ構造にして、4本が重複していることは別途処理にすると思います。

□□

□□

各□の位置は(0,0)(0,1)(1,0)(1,1)で表現して、□の各辺に(0,1,2,3)の番号つけて、

左上の□の右辺(0,0,1)と右上の□の左辺(0,1,3)が共通であることは

メソッドを通じて常に同時更新を保証するような感じで。

(0,0,1)=(0,1,3), (0,0,2)=(1,0,0), (0,1,2)=(1,1,0), (1,0,1)=(1,1,3)

id:quiz-t

>4点×4点(3辺x3辺)以上に拡張することを将来想定

まさにそれを想定しているのですが、シンプルな何かがあるかと思ったんですよね。

後半のは面白そうですね。10×10は想定するとして、かなりのチェックになりますが。。。

2007/03/10 19:40:09
id:imo758 No.2

imo758回答回数121ベストアンサー獲得回数192007/03/10 06:19:59

ポイント19pt

どう考えても辺に番号付けて存在ビットがよさそうです。なので役立たないと思ったらポイントはお返しします。ビット・ローテーション命令とビット順反転命令が使えれば楽のようです。

記述が楽なのでここでは漢字と矢印で名づけます。

┏亥┳丑┓

戌‥↑‥寅

┣←╋→┫

申‥↓‥辰

┗未┻巳┛

ここで→を寅=辰の特殊な型とみなし、以下同様に↓:巳未、←:申戌、↑:亥丑とみなすと、→↓←↑の処理を{丑寅 辰巳 未申 戌亥}とほぼ同一に出来ます。つまり{→↓←↑}は{↑→→↓ ↓←←↑}としておきます。するとどの大きさの格子も{丑寅 辰巳 未申 戌亥}の組に分解できます。

ここで回転は{丑寅 辰巳 未申 戌亥}8ビットに対し2ビット・ローテーションします。こうすればテーブルを使わずに済みますが、使えない場合はテーブル化もやむを得ません。

0000 0000→{0000 0000}→0000 0000

0100 0000→{0000 0001}→0000 0100

1000 0000→{0000 0010}→0000 1000 etc. 256通り

反転は{丑寅 辰巳 未申 戌亥}の左右が{亥戌 申未 巳辰 寅丑}になります。上下は不要。ビット順反転命令が使えれば楽ですが、使えない場合はやはりテーブルの出番でしょう。

{0000 0000}←→0000 0000

{0000 0001}←→1000 0000

{0000 0010}←→0100 0000 etc. 256通り

各々{↑→→↓ ↓←←↑}でも大丈夫なことを確かめてください。

この演算を駆使して回転反転で同一視できる8つ(か4つか2つか1つ)のもののうち、辞書順で最小のものを選び代表データとすればいいと思います。

【結論】{{↑→→↓ ↓←←↑}{丑寅 辰巳 未申 戌亥}}の16ビットをお勧めします。

id:quiz-t

返信したつもりでいました。

どう考えても・・・とおっしゃるように、私もこれが一番かなと思っていたのですが、

いざ回転操作などをするとどうもしっくりこないんですね。

いろいろ書いていただいているので、ポイントはお支払いしますが、ちょっとややこしそうです。

marudai0523さんが3,4で提案している「回転して行列に格納」よりも優れているとお考えの場合は再回答お願いいたします。

2007/03/11 04:30:19
id:marudai0523 No.3

marudai0523回答回数5ベストアンサー獲得回数02007/03/10 15:07:52

ポイント18pt

45度回転して、辺の有り無しを行列に格納するのはどうですか?

□/\□

/\/\

\/\/

□\/□

と見るわけです。

たとえば、上の図のようにすべて辺がある場合には

0110 1111 1111 0110になります。

回転しての一致を調べるのは楽です。上下・左右の反転は

多少面倒かな。

id:quiz-t

面白いですね。

45度回転しなくても、行列には格納できそうですが、

わざわざ回転したのはどうしてですか?

直感的には、縦辺・横辺などの違いが吸収されるあたりよさそうですが

90、180、270度まわしたときはどうしたらいいのでしょう?

2007/03/12 23:01:23
id:marudai0523 No.4

marudai0523回答回数5ベストアンサー獲得回数02007/03/10 23:36:17

ポイント18pt

行列への格納の仕方はいろいろあるでしょうけど、45度回転式だと直感的だし、格子数数が増えた場合も自然に拡張できるので悪くないと思います。

90度ほかの回転の比較はこんなやり方できれいに書けるかと。

回転0の基底ベクトルがx0 = [1,0], y0 = [0, 1]、90度の場合はx1 =[0, 1], y1 = [-1, 0], 180度はx2 = [-1,0], y2 = [0, -1], 270度がx = [-1,0], y = [1,0]とおけて、

for(i=0;i<3;i++) for(j=0; j<3;j++) if (mat( i * x0 %4, j * y0 % 4) == mat(i * x1 % 4 , j* y1 % 4) ) {一致している}

などといったループで一致をみるわけです。%は剰余。

上下左右反転の場合も基底ベクトルをいじればできると思います。

id:quiz-t

丁寧な解説ありがとうございます。一行目だけ見ても

□/\□

□//□

□\\□

□×\□

などの場合もあるんですね。

格子ということなら関係ないか

格子数の2倍の行列を確保しなきゃいけないのは悩みどころですが

2007/03/14 22:25:34
id:Z9M9Z No.5

Z9M9Z回答回数343ベストアンサー獲得回数112007/03/11 09:14:57

ポイント18pt

なるほど。束(ラティス)はやはりこの方向で見るべきなんですね^o^

上下反転は y=x を中心に反転する行列、

左右反転は y=-x を中心に反転する行列でよさそうですね。

(逆か?まあ本質的ではない^o^)

10x10程度なら、ビット毎比較ではねなくても、反転や回転を施してから引き算してもメモリからの読み出しとかの方が大きそうですから、そこでの工夫は効果が薄そうです。

辺の本数のような回転や反転での不変量をインデクスに使うのは良い手段で、計算量向上に役にたつと思います。

全体の辺の本数のほか、中心部分の部分格子、つまり中心から距離1以内の本数、2以内の本数、といった量も回転や反転に対して変化しないので使えるでしょう。でも、全体の辺の本数によほど偏りがなければ、母集団が1000組や1万組になってから考えてもいいと思います。

id:quiz-t

行列派ですね。

ビット毎比較<メモリからの読み出し

なんでしょうか。imo758さんとは逆?

2007/03/14 22:31:20
id:imo758 No.6

imo758回答回数121ベストアンサー獲得回数192007/03/13 08:32:56

ポイント18pt

確かにデーター・回転計算・反転計算をシンプルにしようとすれば行列は最適だと思います。しかし重複チェックをしようとするとどうしても数バイトにわたってしまいます。

しかし16ビット(12ビット)格納方式ならそのまま16ビット整数値の比較だけで済みますし、重複チェックのためにテーブル参照方式を使うことになっても64KB(か4KB)だけと負担少なく使用できます。

個人的には格子が巨大化したときの計算量の増大も気になります。行列式だと実装次第では回転反転計算量は辺の本数の1~3乗に比例しかねませんが、予め格子全体を{丑}{寅} {辰}{巳} {未}{申} {戌}{亥}という8つのリストに分解しておけば、回転反転計算量はポインタの交換操作分だけ、つまり常に定数にできます。まあこの質問では計算量は考慮外のようですが。

id:quiz-t

ビット毎比較>メモリからの読み出し

でZ9M9Zさんとは逆ですか?どちらが正しいのでしょう?

2×2の場合と、5×5の場合とで違ったりしますか?

実はWEB上でやりたいので計算量は考えたいのです。

おっしゃっていることはperlやphpでもできますか?

・テーブル参照方式

・ビット・ローテーション命令

・ビット順反転命令

あたりがちょっとピンときません。

>ポインタの交換操作

C言語あたりと絡んでくるんですかね。

perl、phpでできる方法を解説してもらえると嬉しいです。

2007/03/14 22:32:36
  • id:Ma2
    回転・反転して交換される辺を集めて1グループとし、
    グループごとにビット集合にするのがよいでしょう。
    このケースだと外側の辺8個で1バイト、内側の辺4個で1バイトの
    配列になります。
    こうすると、回転・反転それぞれについて、変換前の状態に対する変換後の状態を持つ配列を作ることができます。
    (1バイト*256で、256バイト、8個用と4個用で2種類)
    この配列を参照するだけで回転・反転操作ができるので非常に速い計算ができるわけです。
    90度回転の配列を作っておけば、回転を繰り返すだけで180・270度は計算できます。
    辺の数を増やす拡張も容易ですね。
  • id:quiz-t
    一週間で終了なんですね。
    ポイントが勝手に配分されてしまいましたが、応えてくださった回数に応じてということでよかったと思います。
    想定していたポイントがあまってしまいましたが・・・。
    -----------------------------------------------------------
    >Ma2さん
    アイデアとしてみなさまの回答の中では一番良さそうですね。
    ポイント送信させていただきました。
  • id:imo758
    テーブル参照:予め
    @lotation_shift_2bit_left=(0,4,8,12,...);
    @lotation_shift_2bit_right=(...);
    @reverse_bit=(...);
    のようにテーブルに計算結果を格納しておくこと。

    ビット・ローテーションはアセンブラには
    あるようですが、PerlやCには基本的にはないのかな…。
    Phpはビット周りあまり触ったことないですのでわかりません。
    ビット順を反転させる命令はもっとレアみたいですね。

    Perlで8ビット整数$aを左に2bitローテーションするには
    $a = ($a << 2) | (($a & 0xc0) >> 6);
    でよかったと思います。

    ビット逆順はこれでたぶんいいかと(Perl)
    sub bit8_reverce{
    my ($a, $b) = ($_[0] & 0xAA, $_[0] & 0x55);
    $a = ($a >> 1) | ($b << 1);
    $b = $a & 0x33;
    $a &= 0xCC;
    $a = ($a >> 2) | ($b << 2);
    $b = $a & 0x0F;
    return ($a >> 4) | ($b << 4);
    }
    そのテストルーチンはこちら
    foreach($n=0; $n<256; $n++){
    printf("%08b %08b \n", $n, &bit8_reverce($n));
    }
    ただやっぱりルーチンだと少し重いと思います。
    処理量などにもよりますが配列(テーブル)に覚えさせたほうがいいかと。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません