вычислить максимальное расстояние с большими векторами

Question

ok, поэтому у меня есть 2 вектора (A и B) с разной длиной (в этом примере можно сказать 100000 и 300000), и я хочу получить индексы, имеющие наибольшую разницу. Что-то вроде этого

distAB=bsxfun(@(v1,v2) abs(v1-v2),A,B)); 
[~,lin_indx]=max(distAB(:)); 
[x_indx,y_indx]=ind2sub(size(A),lin_indx) 

Проблема здесь в том, что мои векторы А и В являются слишком большими, и производя матрица «distAB» слишком дорого. Я хотел бы получить мин непосредственно с bsxfun.

Answer 1

Если вы хотите разворачивания расстояния, поиск может быть сведена к только две пары кандидатов : max(A), min(B)) или min(A), max(B)).

Так просто попробовать эти две пары:

[ma_val, ma_ind] = min(A); 
[Ma_val, Ma_ind] = max(A); 
[mb_val, mb_ind] = min(B); 
[Mb_val, Mb_ind] = max(B); 
diff1 = abs(Mb_val-ma_val); 
diff2 = abs(Ma_val-mb_val); 
if diff1 > diff2 
    result_ind_A = ma_ind; 
    result_ind_B = Mb_ind; 
    result_value = diff1; 
else 
    result_ind_A = Ma_ind; 
    result_ind_B = mb_ind; 
    result_value = diff2; 
end 

---

Если вы хотите минимизировать расстояние: сортировка конкатенации A и B, отслеживание какого элемент из A и который из B :

C = sortrows([A(:) zeros(numel(A),1); B(:) ones(numel(B),1)] ,1); 
%// C(k,2)==0 indicates element k comes from A; 1 indicates from B 

Теперь, используйте петлю for для перемещения всех элементов в C(:,1), которые исходят от B. Для каждого такого элемента найдите два элемента из A, которые расположены ближе всего выше и ниже слева в C. Это единственные кандидаты от A, чтобы быть ближе к этому элементу от A.

Для каждого элемента от B у вас есть два кандидата от A, что значительно снижает сложность проблемы.

Answer 2

Вы можете рассчитать distAB этот путь с помощью встроенного в @minus, которые могли бы быть более эффективным -

distAB = abs(bsxfun(@minus,A(:).',B(:))) 

Answer 3

Luis «Подход к сортировке, вероятно, будет самым быстрым. Но если у вас установлен набор инструментов статистики, вы можете использовать функцию knnsearch, которая обеспечивает простое, но эффективное решение. (Есть также некоторые подобные бесплатные версии этого файла на Файловом обмене. Ищите: kd tree nearest neighbor)

Одним из дополнительных преимуществ этого решения является то, что он также работает для данных 2D, 3D, ..., nD.

[Is, D] = knnsearch(A,B,'K',1); 
[~,j] = min(D); i = Is(j); 
[A(i), B(j)]