首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》存储问题

关灯直达底部

当使用二维矩阵来表示元素集合中n个元素的潜在关系时,需要注意一些事项。首先,矩阵需要n2个元素的存储空间,即使有时候元素之间的关系集合非常小。在这些情况下,也就是所谓的稀疏图,由于计算机内存的限制,不可能存储超过数千个顶点的图。例如,Java虚拟机堆使用默认值256MB,创建一个二维的int[4096][4096]矩阵就已经超出可用内存。即使程序员能够在一台有着更多内存的计算机上执行程序,事实上创建的矩阵规模存在一个固定的上界。另外,在大规模矩阵中存储稀疏图,遍历矩阵来寻找边的操作的开销会很大,并且这种存储方法也限制了更多的改进。第二,当顶点之间有多种关系时,不适合使用矩阵。为了能够在矩阵中存储这种关系,矩阵中每一个元素将会当作一个表。

每一种邻接表示法都存储了相同的信息。假设,你写了一个程序,需要计算出世界上任意两个城市之间的最便宜航班。每条边的权重和两个城市之间最便宜直航的价格有关(假设航线不会中转)。根据2005年国际机场协会(ACI)发布的一份报告,世界上有总共1659个机场,这样也就需要一个有2 752 281个条目的二维矩阵。那么就有一个问题:“多少条目是有值的”,它的答案取决于直航航线的数目,ACI的报告也显示,2005年有71 600 000次“航空活动”,简单地说每天有大概196 164次航班。即使所有的航班都是在两个不同机场之间的直航(显然直航的数目要比这个小很多),这个矩阵也有93%是空值——一个非常好的稀疏矩阵的例子!

当使用一个邻接表表示无向图时,我们可以使用一些方法来减少需要的存储空间。假设一个顶点u的邻接顶点为:2、8、1、5、3、10、11和4。首先,这些邻接顶点会以升序来存储,这样做能够快速地定位是否存在一条边(u,v)。在这种结构下,虽然有8个邻接顶点,但是确定是否边(u,6)是否存在只需要6次比较。当然,添加一条边就不再是常数时间,这里我们需要权衡一下利弊。其次,为了能够更加高效地检查是否边(u,v)存在,邻接表可以存储邻接顶点的范围,例子中的邻接表中八个顶点可以减少到三个:1~5、8、10~11。这种方法也能够减少是否存在一条边的计算次数,不过这会降低添加或者删除边的效率。