2

20組の座標があり、そのx値とy値は次のようになります。

x   y
27  182
180 81
154 52
183 24
124 168
146 11
16  90
184 153
138 133
122 79
192 183
39  25
194 63
129 107
115 161
33  14
47  65
65  2
1   124
93  79

ここで、15ペアの座標（x、y）をランダムに生成し、上記の20ペアの座標と比較したい場合、ネストされたループなしでこれを最も効率的に行うにはどうすればよいですか？

4

3 に答える 3

3

ランダムに生成された 15 の座標ペアのいずれかが元の 20 の座標ペアのいずれかと等しいかどうかを確認しようとしている場合、簡単な解決策は次のように関数ISMEMBERを使用することです。

oldPts = [...];  %# A 20-by-2 matrix with x values in column 1
                 %#   and y values in column 2
newPts = randi(200,[15 2]);  %# Create a 15-by-2 matrix of random
                             %#   values from 1 to 200
isRepeated = ismember(newPts,oldPts,'rows');

の行が存在する場合は1 で、それ以外の場合は 0isRepeatedの 15 行 1 列の論理配列になります。newPtsoldPts

于 2011-05-03T19:19:52.033 に答える
1

座標が1）実際には整数であり、2）スパンが妥当である場合（それ以外の場合はスパース行列を使用）、単純な真理値表を使用します。好き

x_0= [27 180 ...
y_0= [182 81 ...
s= [200 200]; %# span of coordinates
T= false(s);
T(sub2ind(s, x_0, y_0))= true;
%# now obtain some other coordinates
x_1= [...
y_1= [...
%# and common coordinates of (x_0, y_0) and (x_1, y_1) are just
T(sub2ind(s, x_1, y_1))
于 2011-05-04T13:13:50.010 に答える
0

元の20ポイントが変更されない場合は、それらをO（n log n）でソートすると、効率が向上します。次に、O（log n）検索を使用して、各ランダムポイントがリストに含まれているかどうかを確認できます。

「元の」ポイントリストが変更された場合（挿入/削除）、バイナリツリーで同等のパフォーマンスを得ることができます。

ただし、作業しているポイントの数が質問の数と同じくらい少ない場合は、ダブルループが最速の方法である可能性があります。Big-O曲線が低いアルゴリズムは、データ量が非常に多くなるにつれて高速になりますが、多くの場合、1回限りの速度低下（この場合は並べ替え）が必要になります。データポイントは15x20しかありません...人間が知覚できる違いにはなりません。システムクロックでタイミングを合わせている場合は、1つ表示されることがあります。またはあなたはそうではないかもしれません。

お役に立てれば！

于 2011-05-03T18:52:00.900 に答える