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

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) log (n1)