我有一个静态图(拓扑不会随时间变化,并且在编译时已知),其中图中的每个节点都可以具有三种状态之一。然后我模拟一个动态,其中一个节点有可能随时间改变其状态,而这个概率取决于其邻居的状态。随着图表变大,模拟开始变得非常慢,但经过一些分析后,我发现大部分计算时间都花在了遍历邻居列表上。
我能够通过更改用于访问图中邻居的数据结构来提高模拟速度,但想知道是否有更好(更快)的方法来做到这一点。我目前的实现是这样的:
对于一个N
节点标记为从0
到N-1
且平均邻居数为 的图K
,我将每个状态作为整数存储在 an 中std::vector<int> states
,并将每个节点的邻居数存储在 中std::vector<int> number_of_neighbors
。
为了存储邻居信息,我创建了另外两个向量:std::vector<int> neighbor_lists
它按顺序存储与 node 0
、 node 1
、 ... 、 node相邻的节点N
,以及一个索引向量std::vector<int> index
,它为每个节点存储其第一个邻居的索引neighbor_lists
.
所以我总共有四个向量:
printf( states.size() ); // N
printf( number_of_neighbors.size() ); // N
printf( neighbor_lists.size() ); // N * k
printf( index.size() ); // N
更新节点时i
,我像这样访问它的邻居:
// access neighbors of node i:
for ( int s=0; s<number_of_neighbors[i]; s++ ) {
int neighbor_node = neighbor_lists[index[i] + s];
int state_of_neighbor = states[neighbor_node];
// use neighbor state for stuff...
}
总结一下我的问题:是否有更快的实现来访问固定图结构中的相邻节点?
目前,我已经在相当长的模拟时间内达到了 N = 5000,但如果可能的话,我的目标是 N ~ 15.000。