我有一个N节点和L链接的无向图，其结构通常由其具有N行和N列的邻接矩阵A描述。在该邻接矩阵中，值‘1’表示两个节点之间的链路，反之，‘0’表示没有链路。
我在MatLab中工作，希望避免内置graph()函数提供的所有复杂功能，例如N = neighbors(G, NODEID)，其中G是G = graph(adjm);，adjm是邻接矩阵。
在此图中，我需要确定哪些唯一节点(邻居)连接到一个或多个初始节点，标记为idx。我目前使用的是以下代码行：

fidx = unique(ceil(find(adjm(idx,:)) / numel(idx)));

其中fidx包含一组idx起始节点的邻居(连接的节点)。这个操作对不同的节点重复了很多次，经过一些分析后，我发现指令find(adjm(idx,:))确实阻碍了整个运行时。我的第一个尝试是试图避免find()。例如，使用：

A = adjm(idx,:);
A = A(:) == 1;
V = 1:size(A,1);
idx = unique(ceil(V(A) / numel(idx)));

然而，对于我的应用程序来说，这仍然太慢了。
对于减少与此特定代码段相关的运行时间，您有什么建议？
下面是一个最小的例子：

%Minimal example:
f = @() get_neighb();
timeit(f)

function get_neighb()
%generate a graph with a large number of nodes N, in order to have
%computations times large enough:
N = 2e4; %number of nodes
G = round( rand(N) / 1.5 );
G = triu(G) + triu(G,1)';
adjm = G - diag(diag(G));

%for visualisation purposes:
%plot(graph(adjm));

s = size(adjm,1);

%list of some nodes to search for (randomly chosen):
n_nodes_test = 2000; %number of couples to test
%In this minimal example, we focus on searching for the neighbors of each couple (2-tuple) of
%nodes only. But 'snodes' can be single nodes or n-tuples, i.e. containing more
%than 2 nodes
snodes = [ round(linspace(1, s/2, n_nodes_test)); round(linspace(s/2, s, n_nodes_test))]';

%This section is the critical one:
for i=1:n_nodes_test
    
    idx = snodes(i,:); %assign current couple of starting nodes to 'idx'.
    
    %fidx = unique(ceil(find(adjm(idx,:)) / numel(idx)));
    %can be replaced by the following:
    A = adjm(idx,:);
    A = A(:) == 1;
    V = 1:size(A,1);
    idxf = unique(ceil(V(A) / numel(idx)));
    
    %which is similar to (using Matlab built-in 'graph' functions):
    % G = graph(adjm);
    % T = unique([neighbors(G, snodes(1,1)); neighbors(G, snodes(1,2))]);
    % here idxf' == T
end

end

基准测试

以下是提出的解决方案的简短基准。关于如何使用timeit()或profiler准确测量运行时，有几个建议。在这个基准测试中，我们坚持使用分析器来测量每个函数find_neighb_v()的运行时间。在上面发布的最小示例中，大约80%的运行时专门用于构建图形adjm。然而，我们的目标是测量检索节点邻居的最快方法，而不是测量创建图的时间。

关于图(G)的一个注记

MatLab内置套件graph()提供了实用而高效的函数来返回节点的邻居。然而，对于邻接矩阵adjm的每次直接修改，都需要通过调用graph(G)来更新graph()结构，这可能非常耗时，尤其是对于大型网络。可以直接修改graph()结构的底层Node和Edge列表，但对于使用邻接矩阵属性直接处理图形拓扑的人-例如使用频谱分析-这是不可能的。这里还提供了graph()函数的运行时，以便于比较。

代码

%Benchmarck using profiler:

%generate a graph with a large number of nodes N, in order to have
%computations times large enough:
N = 1.5e4; %number of nodes
G = round( rand(N) / 1.5 );
G = triu(G) + triu(G,1)';
adjm = G - diag(diag(G));

%for visualisation purposes:
%plot(graph(adjm));

s = size(adjm,1);

%list of some nodes to search for (randomly chosen):
n_nodes_test = 2000; %number of couples to test
%In this minimal example, we focus on searching for the neighbors of each couple (2-tuple) of
%nodes only. But 'snodes' can be single nodes or n-tuples, i.e. containing more
%than 2 nodes
snodes = [ round(linspace(1, s/2, n_nodes_test)); round(linspace(s/2, s, n_nodes_test))]';

G_test = graph(adjm);

profile on
%1st version, using find()
find_neighb_v1(adjm, snodes, n_nodes_test);
%2nd version, without find()
find_neighb_v2(adjm, snodes, n_nodes_test);
%3rd version, using any() and find()
find_neighb_v3(adjm, snodes, n_nodes_test);
%base version, using built-in graph() and neighbors-) functions
find_neighb_base(G_test, snodes, n_nodes_test);
profile viewer

function find_neighb_v1(adjm, snodes, n_nodes_test)
    for i=1:n_nodes_test
        idx = snodes(i,:); %assign current couple of starting nodes to 'idx'.
        
        idxf = unique(ceil(find(adjm(idx,:)) / numel(idx)));
    end
end

function find_neighb_v2(adjm, snodes, n_nodes_test)

    for i=1:n_nodes_test
        idx = snodes(i,:); %assign current couple of starting nodes to 'idx'.
    
        A = adjm(idx,:);
        A = A(:) == 1;
        V = 1:size(A,1);
        idxf = unique(ceil(V(A) / numel(idx)));
    end

end

function find_neighb_v3(adjm, snodes, n_nodes_test)

    for i=1:n_nodes_test
        idx = snodes(i,:); %assign current couple of starting nodes to 'idx'.
    
        idxf = find(any(adjm(idx, :)));
    end

end

function find_neighb_base(G, snodes, n_nodes_test)

    for i=1:n_nodes_test
        idx = snodes(i,:); %assign current couple of starting nodes to 'idx'.
        
        idxf = unique([neighbors(G, idx(1)); neighbors(G, idx(2))]);
    end

end

结果和结论

结果是在一台简单的办公计算机上获得的：

find_neighb_v1 : 1.437s
find_neighb_v2 : 1.314s
find_neighb_v3 : 0.995s
find_neighb_base : 0.666s

并证明了所提出的解决方案(V3)更有效，但受到find()的阻碍。