人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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)など

●質問者: quiz-t
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:とりま アドバイス サイト シンプル データ
○ 状態 :終了
└ 回答数 : 6/6件

▽最新の回答へ

1 ● Z9M9Z
●19ポイント

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)

◎質問者からの返答

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

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

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


2 ● imo758
●19ポイント

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

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

┏亥┳丑┓

戌‥↑‥寅

┣←╋→┫

申‥↓‥辰

┗未┻巳┛

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

ここで回転は{丑寅 辰巳 未申 戌亥}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ビットをお勧めします。

◎質問者からの返答

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

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

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

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

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


3 ● marudai0523
●18ポイント

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

□/\□

/\/\

\/\/

□\/□

と見るわけです。

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

0110 1111 1111 0110になります。

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

多少面倒かな。

◎質問者からの返答

面白いですね。

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

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

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

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


4 ● marudai0523
●18ポイント

行列への格納の仕方はいろいろあるでしょうけど、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) ) {一致している}

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

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

◎質問者からの返答

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

□/\□

□//□

□\\□

□×\□

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

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

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


5 ● Z9M9Z
●18ポイント

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

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

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

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

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

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

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

◎質問者からの返答

行列派ですね。

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

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


1-5件表示/6件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ