한 벡터와 다른 벡터의 각 요소 간의 최소 차이 찾기

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) 가장 큰 요소의 색인을 줄 것입니다. 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을 정렬하여 시작하십시오

그런 다음 OBJ2의 각 요소에 대해 OBJ1에서 이진 검색을 수행 할 수 있습니다. 요소가 어디에 있는지 알면 OBJ1의 근처의 두 요소와의 거리를 비교하여 최소 거리를 제공 할 수 있습니다.

런타임 (여기서 n1 = | obj1 | 및 n2 = | obj2 |) : (n1 + n2) log (n1)