
今
struct POINT{
double x;//x座標
double y;//y座標
}
struct Model{
POINT point[18000];
}
というふうな 構造体を宣言し、
Model upper;
Model lower;
を 宣言します。
upper.point[0] から 一番近い点 を lowerから みつけたいのですが、lower.point[0]からlower.point[17999]まで 順番に探して より小さいものがみつかれば それを (例えば)m に 代入すると いった風にしています。しかし それをupperの点すべてにそれぞれ 一番近いてんをlowerから 探そうと すると プログラムが 固まってしまって うまく うごきません。 なにか いいアイデアは ありませんでしょうか?アルゴリズム など なにか 知っている方が いれば 教えて下さい。
No.4ベストアンサー
- 回答日時:
もし距離を調べるのにsqr((x-a)^2+(y-b)^2)を使っているので有れば、平方根を取らないで2乗のままにしましょう。
ちょっとした間違いがあっても良いのなら、abs(x-a)+abs(y-b)で距離を近似するという手も有ります。
さらに言うと、upper.point[x]、lower.point[n]それぞれにupper.i[x]、lower.i[n]という整数を宣言しておき、距離を計算するときに、まずupper.i[x]、lower.i[n]で距離を計算し、mに近ければあらためてupper.point[x]、lower.point[n]で距離を測定するという手が有ります。
(まず8bitか10bit程度の整数での距離計算で篩い分けします。)
upperの中心の点、lowerの中心の点をModel Uc,Lc;と宣言します。
upper、lowerそれぞれ移動する毎にUc、Lcを計算します。
upper.point[x]とlower.point[n](n=0~17999)の距離を
調べるのに、まずlower.point[n]のx座標がLcのx座標よりupper.point[x]のx座標に近く、次にlower.point[n]のy座標がLcのY座標よりupper.point[x]のy座標に近いものだけ調べることにします。
うまくすれば、計算時間が1/4になるはずです。
No.5
- 回答日時:
「プログラムが固まる」といっても, 動かしている PC の速度もわからなければどのくらいの時間がかかるのかもわからないので比較にはなりませんが....
手元の PC (Pentium3 1GHz) で動かしてみたところ, 全点間の距離を調べるプログラムで実行時間は約2分でした.
No.3
- 回答日時:
18000程度なら工夫なしでもそんなに時間がかかるとは思えませんが。
。。工夫のしかたとては、例えば座標を3x3の9つのグループに分けて、真ん中のグループじゃないときは、同じグループか隣のグループから探すとか。
とりあえず工夫なしのコード。。。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct POINT{
double x;//x座標
double y;//y座標
};
struct Model{
struct POINT point[18000];
};
struct Model upper;
struct Model lower;
/* 距離を計算 */
double kyori(int i, int j) {
return sqrt((upper.point[i].x-lower.point[j].x)*(upper.point[i].x-lower.point[j].x)
+(upper.point[i].y-lower.point[j].y)*(upper.point[i].y-lower.point[j].y));
}
/* upperから一番近いlowerを探す */
int sagasu(int n) {
int i,res;
double d;
double dd;
res=n; d=kyori(n,n); /* とりあえず1個距離を求めて仮の最小値とする */
for (i=0; i<18000; i++) {
dd = kyori(n,i);
if (d>dd) { res=i; d=dd; }
}
return res;
}
int main(void) {
int i,j;
double d,dd;
int min1,min2;
/* 乱数で座標セット */
for (i=0;i<18000;i++) {
upper.point[i].x = (double)rand();
upper.point[i].y = (double)rand();
lower.point[i].x = (double)rand();
lower.point[i].y = (double)rand();
}
min1=0; min2=sagasu(min1); d=kyori(min1,min2);
/* 各upperに対して探す */
for (i=1;i<18000;i++) {
j=sagasu(i);
dd=kyori(i,j);
printf("%d %d %g\n",i,j,dd);
if (dd<d) { d=dd; min1=i; min2=j;}
}
printf("min: upper=%d lower=%d distance=%g\n",min1,min2,d);
return 0;
}
この回答への補足
いえ ものすごい 時間かかります。最初は こおったのかと おもってたんですが、実は そうではありませんでした。
質問内容を もう少し詳しく いうと
struct POINT{
double x;
double y;
double z;
}
実は POINT は 3次元です。
struct Model upper;
struct Model lower;
と宣言した場合
upper.point[0]の点と 一番近い点をlower から探す。
upper.point[1]の点と 一番近い点をlower から探す。
upper.point[2]の点と 一番近い点をlower から探す。
upper.point[3]の点と 一番近い点をlower から探す。
upper.point[4]の点と 一番近い点をlower から探す。
.
.
.
.
.
upper.point[17998]の点と 一番近い点をlower から探す。
upper.point[17999]の点と 一番近い点をlower から探す。
このような 感じです。
かなり 時間がかかります。単純に考えて 18000×18000 です
どう 工夫すればいいか 教えてください。お願いします。あと 私が 工夫せずに おこなっていたのは JaritenCat と 似たような 内容です。
(あとで 線形探索 だと わかりました。)
No.1
- 回答日時:
簡単にするために第1象限限定して考えると、
全部の点を調べるのが前提であれば、upperおよびlowerをそれぞれ原点に近い順にソートしておき、
upper[0]をlower[0]から順に距離を調べていきます。
で、探し当てたlower[n]を基準にupper[1]を探していきます。
このときlower[n-1]、lower[n-2]・・・lower[n-i]とlower[n]より近い物がある間、戻って調べ、lower[n-1]よりlower[n]が近ければlower[n+1]側もより近い物がある間調べていきます。
ソートされていることにより、lowerもupperも、後になればより原点より遠くなっていくので、調べる範囲も絞れるのではないでしょうか?
第1象限に限定しましたが、座標においてオフセットをとってやれば同じ事になると思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Java java 引数 戻り値のあるメソッド 3 2023/02/12 06:23
- C言語・C++・C# 未解決の外部シンボル _printfが関数_mainで参照されました 1 2022/09/18 15:28
- 英語 "by a ~ 0.5 percentage point"が単数となる理由等について 2 2023/05/11 10:41
- iPhone(アイフォーン) 楽天モバイル iPhone SE (第3世代) の24,000ポイント還元はMNPで新規のみですか? 1 2022/07/02 01:00
- ポイントサービス・マイル docomoポイントについてです。 今まで9000pointあったのが いきなり120pointにな 6 2022/07/01 10:59
- Excel(エクセル) RANK.EQとCOUNTIFSの組み合わせで同ポイントの場合、違う条件を加えて順位を付けたい。 1 2022/08/30 19:49
- スーパー・コンビニ イオンカードで、レジでWAON POINTを使って支払いたい時、電子マネーWAONカードのように機械 1 2023/03/12 05:44
- その他(プログラミング・Web制作) Pythonでのアニメーション 1 2023/06/01 15:58
- 英語 NO plays the role of an "aerocrine" messenger betw 2 2022/09/21 21:37
- 英語 「it takes 期間 to do/doing」の意味やニュアンスの違いについて 1 2023/01/15 14:02
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
プログラミングについて。 1つ...
-
gccを行ってもexeファイルが生...
-
c言語
-
visual studio 2022でのC#プロ...
-
C# DatagridviewにExcelシート...
-
mallocについて
-
C言語って古いですか?
-
C言語関数違いについて。
-
逆コンパイルと逆アセンブルの...
-
プログラムの実行時に'<'でリダ...
-
パソコン
-
CPUが16bitでも32bitOSでコンパ...
-
Python、プログラミングについ...
-
だれがとけるの?
-
バッチファイルで以下のような...
-
Notepad++の関数リスト表示の変...
-
VisualStudio2022でC言語プログ...
-
License='MIT' ってなんでmitな...
-
C言語 ストリームについて。
-
c言語でイベントフラグを使った...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
c言語
-
gccを行ってもexeファイルが生...
-
大量のデータを読み込んで表示...
-
visual studio 2022でのC#プロ...
-
C++でデスクトップGUIアプリ開...
-
【C言語】全角文字の配列を、全...
-
Windows Formアプリからコンソ...
-
VisualStudio2022でC言語プログ...
-
C#でログファイルにファイルパ...
-
C#でTreeViewのCheckBoxのサイ...
-
c#のTLS1.2での通信について
-
VisualStudioでC++クラスを追加...
-
C言語について。
-
int16_t の _t は何?
-
プログラマー達は何故、プログ...
-
逆コンパイルと逆アセンブルの...
-
C言語の関数のextern宣言
-
c言語でイベントフラグを使った...
-
C言語 関数、変数の宣言について
-
[C言語]fputsとfprintfの違い
おすすめ情報