Поиск в векторе слишком дорог для вычислений

Question

Мне нужно выполнить блок кода, подобный следующему:

x = some_number;
y = some_other_number;

u = a_vector_of_numbers;
v = another_vector_of_numbers;
% u and v are of equal size

r1 = ((x == u) | (x == v));   % Expensive!
r2 = ((y == u) | (y == v));   % Expensive!

q = any(r1 & r2);

Вы можете думать об этом как: x и y - два узла на графике, и если я не ошибаюсь,это проверяет, связаны ли x и y, используя список смежности [r1, r2].Другими словами, я пытаюсь ответить на вопрос: «Существует ли такой индекс i, что x и y могут быть найдены в r1(i) или r2(i)?»

Iнужно делать это неоднократно.И r1, и r2 могут содержать до тысячи уникальных значений (количество узлов на графике порядка 10 ⁴ ), а их длина составляет сотни тысяч (количество ребер напорядка 10 ⁶ ).

Мой профилировщик говорит мне, что две строки, которые я указал в комментариях, занимают 99% времени выполнения, и моей программе требуется много времени для запуска, поэтому яЯ задаюсь вопросом: сколько еще это может быть оптимизировано?Каков фундаментальный предел минимального времени вычислений и насколько я близок?

Кроме того, было бы довольно легко передать этот конкретный код на другой язык.Может ли это когда-нибудь привести к значительному увеличению производительности?

Answer 1

Если ваша первая проверка (r1), вероятно, удалит большинство результатов, ваша вторая проверка может быть предварительно отфильтрована, чтобы проверить только возможные совпадения. Код для этого будет выглядеть так:

mask_r1 = ((x == u) | (x == v));   % Expensive!
r2 = ((y == u(mask_r1)) | (y == v(mask_r1)));   % Less expensive!
q = any(r2);

Я даже видел случаи (обычно в старых версиях Matlab), где добавление find к первой строке улучшало производительность. Но я больше не думаю, что это правда (они включили эту оптимизацию в анализатор). Ниже приведены некоторые временные результаты трех методов (оригинальный, с использованием логической маски, с использованием явного списка индексов):

x = 2;
y = 3;
v = randi(200,1e5,1);
u = randi(200,1e5,1);

tic;
for ix = 1:1000
    r1 = ((x == u) | (x == v));   % Expensive!
    r2 = ((y == u) | (y == v));   % Expensive!
    q = any(r1 & r2);
end
toc;  %1.175234


tic;
for ix = 1:1000
    mask_r1 = ((x == u) | (x == v));   % Expensive!
    r2 = ((y == u(mask_r1)) | (y == v(mask_r1)));   % Less expensive!
    q = any(r2);
end
toc;  %0.878857

tic;
for ix = 1:1000
    ixs_r1 = find(((x == u) | (x == v)));   % Expensive!
    r2 = ((y == u(r1)) | (y == v(r1)));   % Less expensive!
    q = any(r2);
end
toc;  %1.118103

Answer 2

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

Вы пытались создать матрицу смежности для своего графика и использовать ее для своих запросов?Хотя создание матрицы (один раз) было бы относительно дорогой операцией, проверка на наличие ребра была бы намного дешевле, чем чтение обоих списков смежности (я думаю).

Если придерживаться текущего алгоритма (или, если говорить точнее, с вашей текущей структурой данных) я был бы удивлен, если бы вы получили значительное ускорение, просто перенеся работу на реализацию на другом языке.Использование другого языка не меняет того факта, что вы просматриваете длинные векторы данных в поисках значений.