Finden der minimalen Differenz zwischen jedem Element von einem Vektor und einem anderen Vektor

Question

Ich habe zwei Vektoren von ganzen Zahlen, und für jedes Element des zweiten Vektors mag ich den minumum Abstand zu jedem Elemente des ersten Vektors finden - zum Beispiel

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

Rückkehr

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

Gibt es eine effizientere Art und Weise? Ich mag dies Tausende Scale-up (Millionen?) Beide obj1 & obj2.

Danke, Aaron

Answer 1

würde ich eine Sprungfunktion auf dem ersten Vektor sortierte verwenden. Dadurch wird vermieden, Loops und ist ziemlich schnell in R.

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

Jetzt myfun(1) geben Sie den Index des größten Elements von sorted.x, dessen Wert kleiner als 1. In meinem Fall

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

Damit Sie wissen, dass das nächste Element entweder sorted.x[myfun(1)] oder sorted.x[myfun(1) + 1] ist. Folglich (und Polsterung für 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

Start durch Sortieren obj1

, dann können Sie eine binäre Suche in obj1 tun für jedes Element von obj2. zu wissen, wo würde das Element sein, können Sie den Abstand zu den beiden in der Nähe Elemente von obj1 vergleichen, können Sie den Mindestabstand zu geben.

Laufzeit (wobei n1 = | obj1 | und n2 = | obj2 |): (N1 + n2) log (n1)