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 souhaite trouver la distance minimale par rapport à 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

retourne

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

Existe-t-il un moyen plus efficace? Je souhaite faire évoluer ce nombre jusqu'à des milliers (millions?) D'obj1 & amp; obj2.

Merci, Aaron

Answer 1

Je voudrais utiliser une fonction step triée sur le premier vecteur. Cela évitera les boucles et est assez rapide en 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 trié.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 trié.x [myfun (1)] ou trié.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

commencez par trier obj1

alors vous pouvez faire une recherche binaire dans obj1 pour chaque élément de obj2. sachant où se trouverait l'élément, vous pouvez comparer la distance aux deux éléments voisins de obj1, ce qui vous donne la distance minimale.

runtime (où n1 = | obj1 | et n2 = | obj2 |): (n1 + n2) log (n1)