Trouver la différence minimale entre chaque élément d'un vecteur et un autre vecteur

Question

J'ai deux vecteurs d'entiers, et pour chaque élément du second vecteur je veux trouver la distance minimale à un élément du premier vecteur - par exemple

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

retours

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

est-il un moyen plus efficace? Je veux mettre à l'échelle jusqu'à des milliers (millions?) Des deux obj1 & obj2.

Merci, Aaron

Answer 1

J'utiliser une fonction pas triées sur le premier vecteur. Cela évitera des boucles et est assez rapide dans R.

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

maintenant myfun(1) vous donnera l'index du plus grand élément de sorted.x dont la valeur est inférieure à 1. Dans mon cas,

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

Vous savez donc que l'élément le plus proche est soit sorted.x[myfun(1)] ou sorted.x[myfun(1) + 1]. Par conséquent (et le remplissage pour 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

départ par le tri obj1

vous pouvez faire une recherche binaire dans obj1 pour chaque élément de obj2. sachant où l'élément serait, vous pouvez comparer la distance aux deux éléments voisins de obj1, en vous donnant la distance minimale.

exécution (n1 = | obj1 | et n2 = | obj2 |): (n1 + n2) log (n1)