Python Dijkstras 二进制分布

通常，从算法而不是数据 struct 的Angular 来考虑空间局部性会更好.比方说，相同的数据 struct 对于Dijkstra算法可能执行得很好，但对于不同的算法来说就不太好了.

Dijkstra算法的关键是(1)优先级队列，(2)寻找与 node 相邻的边，(3)更新 node 距离.

问题是，(2)在每个 node 上只执行一次，因此改进可能不会产生太大的差异.我们可能应该使用邻接列表，将其存储为数组，以便它占用尽可能少的高速缓存线.如果我们可以将此存储与我们无论如何都要访问的内容重叠，那将是最好的，但我看不到这样做的好方法-将它们与优先级队列重叠可能会使优先级队列操作成本更高.

我想说，(3)最好是将所有 node 距离保存在单独的数组中，这也是为了最大限度地减少内存占用.

因此，我们可能会try 如下所示:

struct Edge { 
   int weight; 
   int neighbor; 
}; 
 
struct AdjacencyList { 
   Edge adjacencyHead[K];  // K is tuned to the structure fits  
                           // in an even number of cache lines, and  
                           // is large enough to cover the  
                           // majority of nodes. 
   Edge *adjacencyTail;    // Any overflow incurs an extra  
                           // pointer lookup 
}; 
 
struct Node { 
   int heapPosition; 
   int distance; 
|; 
 
AdjacencyList adjacency[NumNodes]; 
Node nodes[NumNodes]; 
int heap[NumNodes]; 

可能有一种聪明的方法来重叠距离和优先级队列.我们还需要考虑像二进制堆这样的低内存成本数据 struct 和像斐波那契堆这样更昂贵但渐进更有效的 struct 之间的权衡.

可能值得将距离移到堆中，并使用间接方式在那里更新它们，而不是让堆间接引用Node对象进行比较.

或者，我可能错了，保留这样的指针实际上更好，尽管内存成本更高:

struct Node { 
   Node *parent; 
   Node *left; 
   Node *right; 
   int distance; 
|; 

我怀疑它不是，只是因为它至少大了50%(在64位架构上更大)，但我们可能会获得更好的访问位置.

无论如何，优先级队列可能比这里的图形数据 struct 更重要.在最坏的情况下，每次边操作都会改变 node 在优先级队列中的位置.我们可能不得不try 几种可能性，以找到适合特定体系 struct 的最佳可能性.