3次元の最短距離計測 ＭＦＣ６．０ 使用

今　３次元における　最短距離の測定を　しています
現状を説明します

struct POINT {
double x;
double y;
double z;
}
//グローバル宣言
POINT upper[18000];
POINT lower[18000];

int main (void){
　　double min=10000000000000000000.0;//あからさまに　大きくしておく
　　double differ;
　　for(int i=0;i<18000;i++){

　　 for(int k=0;k<18000;k++){
　　 differ = (upper[i].x-lower[k].x)^2+(upper[i].y-lower[k].y)^2+(upper[i].z-lower[k].z)^2;
　　 if(min>differ){
　　 min = differ;
　　 }
　　 }

　 //ここで　準備していたMeasure　に　min　を代入
　 Measure[i]=min;
　}

}

大体これで　２分かかります。
この　単純な方法で　今までよかったのですが、少々　時間が　かかりすぎているので　不都合が　生じています。

もっと　早く処理できる　アルゴリズムを　教えてください。

お願いします

No.3 ベストアンサー 回答者： matyrcry 回答日時： 2005/01/05 20:28

前の方とほとんど同じですが、

発見済みの最短距離とその２乗を控えておいて、
１）Ｘ座標の差分が最短距離よりも大きい
２）Ｙ座標の差分が最短距離よりも大きい
３）Ｚ座標の差分が最短距離よりも大きい
４）ＸとＹの２乗合計が最短距離の２乗よりも大きい
と演算途中でループを抜ける処理を組み込んで
いってはどうでしょうか。
浮動小数の乗除算は整数乗除に比べて遙かに重いので、
かける前に比較で分かるものはハネたほうがいいと思います。

No.7 回答者： yamaichiro 回答日時： 2005/01/08 17:12

大小判断はNo.6の方に賛成です。

で、よけいなお世話なのですが、どうもminの初期化
が気になります。

double min = (upper[0].x-lower[0].x) * (upper[0].x-lower[0].x);
min += (upper[0].y-lower[0].y) * (upper[0].y-lower[0].y);
min += (upper[0].z-lower[0].z) * (upper[0].z-lower[0].z);
とするか、for分の中でi==0 && k==0ならminに代入、
それ以外は大小判別する方が、汎用性があります。

No.6 回答者： JaritenCat 回答日時： 2005/01/08 14:50

計算量を減らすアルゴリズムを研究するのが目的ではなくて計算時間を短縮したいのであれば、計算機を高速なものに変更することをお勧めします。

プログラム上で高速化する手として思いつくのは、
・構造体の配列をバラの配列にする
・２乗和の計算を３つに分けて途中で最小値と比較する
ぐらいです。。

サンプルプログラム
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

//グローバル宣言
double upper_x[18000];
double upper_y[18000];
double upper_z[18000];
double lower_x[18000];
double lower_y[18000];
double lower_z[18000];

double ans;

void f1(void){
int i,k;
double min=10000000000000000000.0;//あからさまに 大きくしておく
double differ;

for(i=0; i<18000; i++) {
for(k=0; k<18000; k++) {
differ = (upper_x[i]-lower_x[k])*(upper_x[i]-lower_x[k]); if (differ>min) continue;
differ += (upper_y[i]-lower_y[k])*(upper_y[i]-lower_y[k]); if (differ>min) continue;
differ += (upper_z[i]-lower_z[k])*(upper_z[i]-lower_z[k]); if (differ>min) continue;
min = differ;
}
}
ans=min;
}

void ini(void) {
int i;
srand(13);
for (i=0; i<18000; i++) { /* 擬似乱数 -RAND_MAX/2 ～ RAND_MAX/2 */
upper_x[i] = (double)(rand()-RAND_MAX/2);
upper_y[i] = (double)(rand()-RAND_MAX/2);
upper_z[i] = (double)(rand()-RAND_MAX/2);
lower_x[i] = (double)(rand()-RAND_MAX/2);
lower_y[i] = (double)(rand()-RAND_MAX/2);
lower_z[i] = (double)(rand()-RAND_MAX/2);
}
}

int main(void) {
clock_t begin, end;

ini();

begin=clock();
f1();
end=clock();

printf("ans=%g %f sec.\n",sqrt(ans),(end-begin)/CLOCKS_PER_SEC);

return 0;
}

No.5 回答者： keikan 回答日時： 2005/01/06 09:30

doubleではなくてlong intにてはいかが？＾＾

No.4 回答者： sha-girl 回答日時： 2005/01/05 22:58

インラインアセンブラで

SSE命令を使ってはどうでしょうか？
SSE命令を使えば
複数の浮動小数点の計算を同時で行えます

ただしCPUがPentium3以上である必要があります。

参考URL：http://www1.kcn.ne.jp/~robe/pf/pf009.html,http:/ …

この回答へのお礼

どうやら　つかえないようです。
ありがとうございました。

お礼日時：2005/01/05 23:58

No.2 回答者： ranx 回答日時： 2005/01/05 19:39

何をなさりたいのかが今一つ分からないのですが、

18000個の各点について、別の18000個の点のうち最も近いものまでの
距離を求めるということでしょうか。
18000個の点がランダムなものなら、X,Y,Z各方向の差分値が大きなものを
除外して、自乗和を計算する時間を省くことができると思います。
18000個の座標値に何らかの規則性があるのなら、それを利用してさらに
計算を省くことができるかもしれません。
いずれにせよ、現状は18000×18000=324000000回も自乗和を計算している
わけですから、何とか工夫して、この回数を減らす必要があるのだと
思います。

この回答への補足

>>何をなさりたいのかが今一つ分からないのですが、
18000個の各点について、別の18000個の点のうち最も近いものまでの
距離を求めるということでしょうか。


はい。そのとおりです。

>>18000個の点がランダムなものなら、X,Y,Z各方向の差分値が大きなものを
除外して、自乗和を計算する時間を省くことができると思います。

差分地が大きいものを除外　というのは　どういうことでしょうか？Ｘ　Ｙ　Ｚ　すべての差が　おおきいものですか？どれか　おおきいものですか？

>>18000個の座標値に何らかの規則性があるのなら、それを利用してさらに
計算を省くことができるかもしれません。

今のところＺ方向のみ　小→大　という順番にならんでいます。

補足日時：2005/01/05 23:48

No.1 回答者： Tacosan 回答日時： 2005/01/05 18:49

「2分かかる」といわれてもスペックもわからなければどのくらい最適化しているかもわからないので, 「本当にそれだけかかってしまう」のか「単にプログラムが遅いだけ」なのか判断のしようがないんですが.

ちなみに ^ を使うのは変ですね.

この回答への補足

スペック？？とは　なんでしょうか？

最適化？　現在　Ｚ　方向のみに注目して　小→大に　ならんでいます。

補足日時：2005/01/05 23:55