Mappatura di 2 vettori - aiuto per vettorizzare

Question

Lavorando in Matlab I ho 2 vettori di coordinate x con lunghezza diversa. Per esempio:

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

ho bisogno di mappare xm per xn, o in altre parole per trovare quale le coordinate nel xn sono più vicini a xm. Quindi se ho dei valori associati a quelle coordinate, posso usare questa mappa come indice e correlare questi valori.

Entrambi i vettori sono ordinati e non ci sono duplicati in ciascun vettore.

Ho scritto una semplice funzione con ciclo 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 

Per l'esempio di cui sopra è rendimenti

xmap = 
    1  2  2  3  3  3  8  9 10 

Funziona bene, ma richiede un po 'con lunghe vettori (oltre 100.000 punti) .

Qualche idea su come vettorializzare questo codice?

Answer 1

Oh! Un'altra opzione: dal momento che stai cercando corrispondenze ravvicinate tra due elenchi ordinati, puoi passarli entrambi contemporaneamente, usando un algoritmo di tipo merge. Questo dovrebbe essere O (max (lunghezza (xm), lunghezza (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 

EDIT: commento vedere @ Yuk, il codice di cui sopra non è del tutto corretto!

Answer 2

Sembra che i vettori di input siano ordinati. Usa una ricerca binaria per trovare la corrispondenza più vicina. Questo ti darà un tempo di esecuzione O (n ln n).

Answer 3

xm e xn sono ordinati. Se questo è generalmente il caso, allora puoi fare molto meglio di passare l'intero array.

Per ciascun valore in xn, ci sarà un intervallo di valori per i quali un valore in xm sarà più vicino a quel numero rispetto a qualsiasi altro. Calcola preventivamente questi intervalli e puoi quindi passare attraverso entrambi gli array in sequenza.

Answer 4

Approfittando di essere ordinato, come dice David, sarà più veloce visto che hai così tanti punti, ma per riferimento un modo per vettorizzare questo sarebbe quello di utilizzare meshgrid:

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

Si noti che questo creerà due 100.000 x 100.000 matrici in memoria, quindi è probabilmente fattibile solo per i set di dati più piccoli.

Answer 5

prendere in considerazione questa soluzione vettorizzati:

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

Answer 6

L'implementazione più rapida di cui sono a conoscenza che risolve questo problema è this one (codice C che può essere compilato come file .mex, per me è circa 20 volte più veloce del codice di rescdsk nella risposta accettata). È sorprendente che un'operazione così comune non sia una funzione incorporata di MATLAB.