9

Matlabでの作業では、長さが異なるx座標の2つのベクトルがあります。例えば：

xm = [15 20 24 25 26 35 81 84 93];
xn = [14 22 26 51 55 59 70 75 89 96];

xmをxnにマップする必要があります。つまり、xnのどの座標がxmに最も近いかを見つける必要があります。したがって、これらの座標に関連付けられた値がある場合は、このマップをインデックスとして使用し、それらの値を相互に関連付けることができます。

両方のベクトルがソートされ、各ベクトルに重複はありません。

forループを使用して単純な関数を作成しました。

function xmap = vectors_map(xm,xn)
xmap = zeros(size(xm));
for k=1:numel(xm)
    [~, ind] = min(abs(xm(k)-xn));
    xmap(k) = ind(1);
end

上記の例では、

xmap =
    1     2     2     3     3     3     8     9    10

正常に動作しますが、長いベクトル（100,000ポイント以上）では時間がかかります。

このコードをベクトル化する方法はありますか？

4

6 に答える 6

5

おー！もう1つのオプション：2つのソートされたリスト間の密接な対応を探しているので、マージのようなアルゴリズムを使用して、両方を同時に調べることができます。これはO（max（length（xm）、length（xn）））-ishである必要があります。


match_for_xn = zeros(length(xn), 1);
last_M = 1;
for N = 1:length(xn)
  % search through M until we find a match.
  for M = last_M:length(xm)
    dist_to_curr = abs(xm(M) - xn(N));
    dist_to_next = abs(xm(M+1) - xn(N));

    if dist_to_next > dist_to_curr
      match_for_xn(N) = M;
      last_M = M;
      break
    else
      continue
    end

  end % M
end % N

編集：@yukのコメントを参照してください、上記のコードは完全に正しくありません！

于 2010-01-27T03:20:39.077 に答える
4

このベクトル化されたソリューションを考えてみましょう。

[~, xmap] = min( abs(bsxfun(@minus, xm, xn')) )
于 2010-01-26T22:48:02.607 に答える
3

この問題を解決するために私が知っている最速の実装はこれです（.mexファイルとしてコンパイルできるCコード。私にとっては、受け入れられた回答のrescdskのコードよりも約20倍高速です）。このような一般的な操作がMATLABの組み込み関数ではないのは驚くべきことです。

于 2014-07-04T19:58:20.780 に答える
1

入力ベクトルがソートされているようです。二分探索を使用して、最も近い一致を見つけます。これにより、実行時間がO（n ln n）になります。

于 2010-01-26T21:39:20.937 に答える
0

Davidが言うように、ソートを利用すると、ポイントが非常に多いため高速になりますが、参考までに、これをベクトル化する1つの方法は、meshgridを使用することです。

[X Y] = meshgrid(xn, xm);
diffs = X - y;
mins = min(diffs, [], 2);

これにより、メモリ内に2つの100,000 x 100,000アレイが作成されるため、おそらくより小さなデータセットでのみ実行可能であることに注意してください。

于 2010-01-26T21:52:32.780 に答える
0

xmとxnが並べ替えられます。これが一般的に当てはまる場合は、アレイ全体をステップオーバーするよりもはるかに優れた方法を実行できます。

xnの値ごとに、xmの値が他のどの値よりもその数に近い値の範囲があります。これらの間隔を事前に計算しておくと、両方のアレイを順番に実行できます。

于 2010-01-26T21:48:03.290 に答える