找到一個矢量的每個元素與另一個矢量之間的最小差異

Question

我有兩個整數向量，對於第二個向量的每個元素，我想找到與第一個向量的任何元素的最小距離 - 例如

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

回報

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

有沒有更有效的方法？我想把這個比例擴大到數千（數百萬）的obj1 & obj2。

感謝， 亞倫

Answer 1

我會使用排序在所述第一向量的階梯函數。這將避免循環，並且在R.

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

蠻快的現在myfun(1)會給你其值小於1的sorted.x最大元素的索引。就我而言，

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

所以，你知道最近的元素是sorted.x[myfun(1)]或sorted.x[myfun(1) + 1]。因此（和填充爲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

開始通過排序OBJ1

那麼你可以做的OBJ1爲obj2的每個元素的二進制搜索。知道元素將在哪裏，您可以將距離與obj1的兩個附近元素進行比較，爲您提供最小距離。

運行時（其中n1 = | OBJ1 |和n2 = | OBJ2 |）： （N1 + N2）的日誌（N1）