每日一博 | 解析内存中的高性能图结构
在进行各种图处理、图计算、图查询的时候,内存或是硬盘中如何存储图结构是一个影响性能的关键因素。本文主要分析了几种常见的内存图结构,及其时间、空间复杂度,希望对你有所启发。 通常来说,对于图结构的几种常见的基础操作: 插入一个点 插入一个边 删除一个边 删除一个点的全部邻边 找到一个点的全部邻边 找到一个点的另一个邻点 全图扫描 获取一个点的入度或者出度 这些图相关的操作,除了要关心时间复杂度之外,需要考虑空间占用的问题。 对于大多数实时读写型的系统,增删改查的性能问题会比较重要,它们比较关注上面 1-6 的操作;对于部分密集计算的系统,对批量读取的性能会比较重视,侧重上面 5-8 的操作。 不过遗憾的是,无论是常规的图查询,还是进阶的图计算,根据 RUM 猜想[1],读快、写快、又省空间这样”既要又要也要”的好事是不存在的。 下面,我们介绍几个数据结构并给出少量的定量分析。 我们先从三个典型的方案(邻接矩阵、压缩稀疏矩阵和邻接表)说起,再介绍几种近几年的研究的变种结构 PCSR、VCSR、CSR++。 邻接矩阵 Adjacency Matrix 用矩阵来表示图结构是大学里数据结构课程中...