3次元配列のループによる比較の回数を減らす

質問

以下は正の整数が入った3次元配列form[30][20][8]で、中身が一致している2カ所に-1を代入してループを抜けるというプログラムの一部分なんですが、無駄なループを減らすにはどういった変更をすればいいでしょうか？
form[30][20][8]は変更しない方向でお願いします。

check:
for(int i=0;i<30;i++){
for(int j=0;j<20;j++){
for(int k=0;k<8;k++){
for(int l=0;l<30;l++){
for(int m=0;m<20;m++){
for(int n=0;n<8;n++){
if(form[i][j][k]==form[l][m][n]&&!(i==l&&j==m&&k==n)form[i][j][k]!=-1)
count++;
form[i][j][k]=-1;
form[l][m][n]=-1;
break check;
}
}
}
}
}
}
}

回答No.1

nag0720 · ベストアンサー

１次元配列とみなしてfor文を２つにし、それぞれのインデックスを計算する方法がありますが、
かえってインデックスの計算に時間が掛かってしまうでしょう。

int size = 30*20*8;
check:
for(int p=0;n1<size-1;n1++){
for(int q=p+1;n2<size;n2++){
int i=p/160;
int j=(p/8)%20;
int k=p%8;
int l=q/160;
int m=(q/8)%20;
int n=q%8;
if(form[i][j][k]==form[l][m][n] && form[i][j][k]!=-1){
・・・・
}
}
}

別の方法として、lをiからにし、(i,j,k)＜(l,m,n)に限定するというやりかたがあります。

for(int i=0;i<30;i++){
for(int j=0;j<20;j++){
for(int k=0;k<8;k++){
for(int l=i;l<30;l++){
for(int m=0;m<20;m++){
for(int n=0;n<8;n++){
if(i==l && (j==m && k<n || j<m) || i<l) {
if(form[i][j][k]==form[l][m][n] && form[i][j][k]!=-1){
・・・・
}
}
}
}
}
}
}
}

回答No.3

racene

#1 の方の手法だと見た目ではループが減っていますが計算量は変わってないですね。一応半分にはなっていますが。

高速に探索したいのであれば、form の他にハッシュテーブルを作って form の中身をそこに格納して、ハッシュテーブルの同じエントリに属するものだけを比較すればよいでしょう。
そうすることで、データ数をnとしたときの計算量が O(n) になります。（元の手法は O(n^2)）

おまけ: http://okwave.jp/qa/q2722011.html
これも同じような方法です。ただしこちらはハッシュテーブルではなく値の領域分のテーブルを作っています。

お礼

返信ありがとうございます。
ハッシュテーブルを知らなかったのでググって見ましたが、なかなか面白そうですね。
実際のところ、今回のif文は簡略化したもので、実際はもう少しめんどくさい条件がついているので、自分の技量では使えそうに無いですが、機会があれば使って見たいと思いました。

回答No.2

teketon

中身が一致するのは２カ所だけか、３カ所以上を考慮しなくて良いのかですね。
３カ所以上を考慮する必要が有る場合、もう全探索が必要なので、form[30][20][8]を変えるしかありません。
2カ所だけなら、＃１の方が回答しているとおりです。

お礼

一致箇所は2箇所になります。
3箇所以上は無いです。