寻找两个向量中每个元素之间的最小差异

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。

谢谢，Aaron

- Aaron Statham

---

我们需要更多信息。是obj1，obj2还是两者都在变化？有多少个唯一的元素？ - hadley

现在，obj1和obj2都需要扩展到数万个，将来可能会扩展到数百万个 - 并且两者都不包含重复项。 - Aaron Statham

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]))

- Jonathan Chang

Answer 2

首先按照 obj1 进行排序。

然后可以在 obj1 中进行二分搜索，查找 obj2 的每个元素。通过知道元素所在位置，可以比较其与 obj1 附近两个元素的距离，从而得到最小距离。

运行时间（其中 n1 = |obj1|，n2 = |obj2|）为： (n1 + n2) log (n1)

- Jayen

Answer 3

回复J. Chang： 感谢您提供强大而快速的解决方案。

对于我使用您的4行代码，我需要找到最小差异（以检查是否可接受）：

min_diff.val = min(mindist)

这里有一个“愚蠢”的错误，我在多年后才注意到。我想要选择差异最小的值...我敢打赌你已经看出来了。

min_diff.idx = which.min(mindist)
sorted.x[indices[min_diff.idx]]

由于mindist同时检查sorted.x [indices]和sorted.x [indices + 1]，所以它们对于idx可能会产生混淆，因为这两个比较具有相同的索引

---

示例： 如果indices是55,56
mindist将检查55,56（索引）和56,57（indices + 1）
如果mindist发现最小值是56，但在indices + 1（56），57中
有没有办法保存正确的索引？

- S.Br