Trovare la differenza minima tra ciascun elemento di un vettore e un altro vettore

Question

Ho due vettori di numeri interi e per ogni elemento del secondo vettore voglio trovare la distanza minima da qualsiasi elemento del primo vettore, ad esempio

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

ritorna

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

C'è un modo più efficiente? Voglio ridimensionare fino a migliaia (milioni?) Di entrambi obj1 & amp; obj2.

Grazie, Aaron

Answer 1

Vorrei usare una funzione passo ordinata sul primo vettore. Questo eviterà loop ed è abbastanza veloce in R.

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

Ora myfun (1) ti darà l'indice dell'elemento più grande di sort.x il cui valore è inferiore a 1 . Nel mio caso,

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

Quindi sai che l'elemento più vicino è sort.x [myfun (1)] o sort.x [myfun (1) + 1] . Di conseguenza (e riempimento per 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

inizia ordinando obj1

allora puoi fare una ricerca binaria in obj1 per ogni elemento di obj2. sapendo dove sarebbe l'elemento, puoi confrontare la distanza con i due elementi vicini di obj1, dandoti la distanza minima.

runtime (dove n1 = | obj1 | e n2 = | obj2 |): (n1 + n2) log (n1)