找到一个向量的每个元素与另一个向量之间的最小差异

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＆amp; OBJ2。

谢谢， 亚伦

Answer 1

我会使用在第一个向量上排序的步进函数。这将避免循环，并且在R中非常快。

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

现在 myfun（1）将为您提供 sorted.x 的最大元素的索引，其值小于 1 。就我而言，

> 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）log（n1）