Cartographie 2 vecteurs - aide à vectoriser

Question

Travailler dans Matlab J'ai 2 vecteurs de coordonnée x avec différentes longueurs. Par exemple:

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

Je dois carte xm pour xn, ou en d'autres termes pour trouver les coordonnées dans le plus proche de xn sont xm. Donc, si je les valeurs associées à ces coordonnées, je peux utiliser cette carte comme indice et établir une corrélation entre ces valeurs.

Les deux vecteurs sont triés et il n'y a pas de doublons dans chaque vecteur.

J'ai écrit une fonction simple pour boucle:

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

Pour l'exemple ci-dessus est retourne

xmap =
    1     2     2     3     3     3     8     9    10

Il fonctionne bien, mais prend un certain temps avec de longs vecteurs (plus de 100 000 points).

Toutes les idées comment vectoriser ce code?

Answer 1

Oh! Une autre option: puisque vous êtes à la recherche de correspondances étroites entre deux listes triées, vous pouvez passer par les deux en même temps, en utilisant un algorithme de fusion semblable. Cela devrait être O (max (longueur (xm), la longueur (x))) -. 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

EDIT: Voir le commentaire de @ Yuk, le code ci-dessus ne sont pas tout à fait correct!

Answer 2

Considérez cette solution vectorisé:

[~, xmap] = min( abs(bsxfun(@minus, xm, xn')) )

Answer 3

La mise en œuvre plus rapide, je suis conscient de cela résout ce problème est celui-ci (code C qui peut être compilé en tant que fichier .mex, pour moi il est environ 20 fois plus rapide que le code de rescdsk dans la réponse acceptée). Il est surprenant qu'une telle opération commune n'est pas une fonction Matlab intégrée.

Answer 4

On dirait que vos vecteurs d'entrée sont triés. Utilisez une recherche binaire pour trouver la plus proche. Cela vous donnera un O (n ln n) temps d'exécution.

Answer 5

Votre XM et sont classés Xn. Si cela est généralement le cas, alors vous pouvez faire beaucoup mieux que d'enjamber le tableau entier.

Pour chaque valeur xn, il y aura une gamme de valeurs pour lesquelles une valeur sera plus proche xm de ce nombre que tout autre. Calculer ces intervalles d'avance et vous pouvez ensuite passer les deux tableaux de façon séquentielle.

Answer 6

Profitant d'être triés, comme dit David, sera plus rapide puisque vous avez tant de points, mais pour référence d'une façon vectoriser ce serait d'utiliser meshgrid:

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

Notez que cela va créer deux 100 000 x 100 000 tableaux en mémoire, il est donc probablement possible pour petits ensembles de données.