Mapeo de 2 vectores - ayuda a vectorizar

Trabajando en Matlab Tengo 2 vectores de coordenadas x con longitudes diferentes. Por ejemplo:Mapeo de 2 vectores - ayuda a vectorizar

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

necesito para mapear xm para x n, o, en otras palabras, para encontrar las coordenadas en x n estamos mucho más cerca xm. Entonces, si tengo valores asociados con esas coordenadas, puedo usar este mapa como índice y correlacionar esos valores.

Ambos vectores están ordenados y no hay duplicados en cada vector.

I escribió una función simple con for-loop:

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

Para el ejemplo anterior es retornos

xmap = 
    1  2  2  3  3  3  8  9 10

Funciona bien, pero toma un tiempo con vectores largos (más de 100.000 puntos) .

¿Alguna idea de cómo vectorizar este código?

Fuente

2010-01-26 yuk

Estoy usando la nueva ~ sintaxis en la última versión de Matlab para omitir una variable no utilizada. Si tiene una versión anterior, simplemente sustituya ~ con tmp. – yuk

Solo para aclarar, ¿quiere para cada xm [i] el índice j tal que xm [i] esté más cerca de xn [j]? –

Sí. Buen resumen, gracias. – yuk

Oh! Otra opción: dado que está buscando correspondencias cercanas entre dos listas ordenadas, puede examinarlas simultáneamente, utilizando un algoritmo tipo fusión. Esto debería ser O (max (longitud (xm), longitud (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: comentario Ver @ Yuk, el código anterior no es totalmente correcto!

Fuente

2010-01-27 03:20:39 rescdsk

¡Genial! Este código me da una mejora de velocidad de más de 50 veces con vectores de 10.000 de longitud y 1500 (!) Veces con vectores de 100.000 lenth. Puede devolver el error si varios últimos elementos de xn se mapearon a xm (end). Cambié las líneas 6-7 a: si M yuk

Parece que no puedo formatear el código en los comentarios. :( – yuk

¡Genial! ¡Yay! ¡Me alegro de que funcione para ti! Sí, esa es una de las cosas divertidas de la informática, cuando de repente creas algo un billón de veces más rápido ... – rescdsk

Parece que sus vectores de entrada están ordenados. Usa una búsqueda binaria para encontrar la coincidencia más cercana. Esto le dará un tiempo de ejecución O (n ln n).

Fuente

2010-01-26 21:39:20

¿Podría proporcionarnos algún código de Matlab, por favor? – yuk

Sí, los vectores están ordenados. – yuk

¡Ahh, búsqueda binaria! No pensé en eso. +1 – John

Su xm y xn están ordenados. Si este es generalmente el caso, entonces puede hacer mucho mejor que pisar toda la matriz.

Para cada valor en xn, habrá un rango de valores para el cual un valor en xm estará más cerca de ese número que cualquier otro. Calcule estos intervalos de antemano y luego puede recorrer ambas matrices de forma secuencial.

Fuente

2010-01-26 21:48:03 John

Tomando ventaja de ser ordenados, como dice David, será más rápido ya que tiene tantos puntos, pero como referencia una forma de vectorizar esto sería utilizar meshgrid:

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

Tenga en cuenta que esto creará dos matrices de 100.000 x 100.000 en la memoria, por lo que probablemente solo sea posible para conjuntos de datos más pequeños.

Fuente

2010-01-26 21:52:32 rescdsk

Sí, requiere mucha memoria y mucho más lento que mi función con vectores pequeños. – yuk

considerar esta solución vectorizado:

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

Fuente

2010-01-26 22:48:02 Amro

Buena vectorización. Gracias. Sin embargo, es aproximadamente dos veces más lento que mi función y también requiere más memoria, pero es mejor que el código anterior. – yuk

La implementación más rápida que conozco que resuelve este problema es this one (código C que se puede compilar como un archivo .mex, para mí es 20 veces más rápido que el código de rescdsk en la respuesta aceptada). Es sorprendente que una operación tan común no sea una función incorporada de MATLAB.

Fuente

2014-07-04 19:58:20

Gracias. Todavía no lo he probado pero parece una gran solución. – yuk

Mapeo de 2 vectores - ayuda a vectorizar

Respuesta

Cuestiones relacionadas