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

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 | п2 = | obj2 |): (n1 + n2) журнал (n1)