Encontrar la diferencia mínima entre cada elemento de un vector y otro

Question

Tengo dos vectores de números enteros, y para cada elemento del segundo vector quiero encontrar la distancia mínima a cualquier elemento del primer vector - por ejemplo

obj1 <- seq(0, 1000, length.out=11) 
obj2 <- 30:50 
min_diff <- sapply(obj2, function(x) min(abs(obj1-x))) 
min_diff 

vuelve

[1] 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 

¿hay una manera más eficiente? Quiero ampliar esto hasta miles (¿millones?) Tanto de obj1 & obj2.

Gracias, Aaron

Answer 1

me gustaría utilizar una función escalonada ordenados en el primer vector. Esto evitará bucles y es bastante rápido en R.

x <- rnorm(1000) 
y <- rnorm(1000) 
sorted.x <- sort(x) 
myfun <- stepfun(sorted.x, 0:length(x)) 

Ahora myfun(1) le dará el índice del elemento más grande de sorted.x cuyo valor es menor que 1. En mi caso,

> myfun(1) 
[1] 842 
> sorted.x[842] 
[1] 0.997574 
> sorted.x[843] 
[1] 1.014771 

para que sepa que el elemento más cercano es o bien sorted.x[myfun(1)] o sorted.x[myfun(1) + 1]. En consecuencia (y relleno para 0),

indices <- pmin(pmax(1, myfun(y)), length(sorted.x) - 1) 
mindist <- pmin(abs(y - sorted.x[indices]), abs(y - sorted.x[indices + 1])) 

Answer 2

inicio clasificando obj1

entonces usted puede hacer una búsqueda binaria en obj1 para cada elemento de obj2. sabiendo dónde estaría el elemento, puede comparar la distancia a los dos elementos cercanos de obj1, que le da la distancia mínima.

tiempo de ejecución (donde n1 = | obj1 | y n2 = | obj2 |): (n1 + n2) log (n1)