Нахождение минимальной разницы между каждым элементом одного вектора и другим вектором

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

затем вы можете выполнить двоичный поиск в obj1 для каждого элемента obj2.зная, где будет находиться элемент, вы можете сравнить расстояние до двух соседних элементов obj1, что даст вам минимальное расстояние.

среда выполнения (где n1 = |obj1| и n2 = |obj2|):(n1 + n2) логарифм (n1)