在矢量搜索是太耗费计算

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)？

我需要反复这样做。 r1和r2都可能包含多达数千个唯一值（图表上的节点数量约为10 ），并且它们的长度是数十万（边缘的数量约为10 ）。

我的配置文件告诉我，我已经注释到的两行代码占用了99％的运行时间，而且我的程序需要相当长的时间才能运行，所以我想知道：还有多少可以优化？最短计算时间的基本限制是什么，以及我有多接近？

另外，将这个特定的代码外包给另一种语言会很容易。这可能会导致显着的性能提升吗？

Answer 1

我没有测试过这个建议，太多的精力来建立一些真实的测试数据，但是......

您是否尝试过你的图形创建邻接矩阵，并使用您的查询？虽然创建矩阵（一次）将是一个相对昂贵的操作，但检查边缘的存在将比阅读两个邻接列表（我认为）便宜得多。

如果您坚持使用您当前的算法（或者更重要的是，使用您当前的数据结构），只要简单地将工作卸载到另一种语言的实现中，您就会感到惊讶。使用其他语言不会改变您正在阅读查找值的长数据向量的事实。

Answer 2

如果您的第一张支票（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