如何评价一线大厂资深 APP 性能优化系列之异步优化与拓扑排序？ 第1页

异步优化不谈，只讨论拓扑排序。拓扑排序是一个非常有意思的东西。拓扑排序有如下几个基本问题。

1、存在回路的有向图，如何进行拓扑排序

答案是缩点，即把回路当成一个要素（结点）来处理。

什么叫缩点？

上面有缩点的示意图。

缩点的算法就是求强连通子集。也就是三大算法。

上面是有计算1000*1000的矩阵，并比较三个算法的速度。

2、拓扑排序最终结果数目

DAG中的拓扑排序的个数等价于统计一个偏序集上线性组合的个数。求这个线性组合已经有人证明了是NP完全问题。NP问题就不解释了。

3、对抗解释结构模型与对抗哈斯图方法

对抗解释结构模型英文简写是AISM，最终是以一对拓扑层级图的方式展示结果。是2020年才提出的方法。这个方法是ISM基础上的拓展，很好发文章。

对抗解释结构模型方法就是对抗哈斯图方法，取的名字不同而已。

运用这个方法，很好理解拓扑排序。先来看AISM的算法。

上面是计算方式一的流程图。

上面是计算方式二的流程图。

具体计算过程不再详细解释。

4、拓扑层级图与拓扑排序

假设最终求出的对抗层级拓扑图如下：

上面就是哈斯图，又叫对抗哈斯图，也叫对抗层级拓扑图。

上面的图称之为可拓变系统，是一个活动网络。即有活动要素。

这个拓扑排序的结果是，任意一边从上往下数形成的一个线性队列就是一个拓扑排序的解。

其中F5可以放到F6的那层，这种也是一个层级拓扑图的解。

这种算拓扑排序的个数是一个NP完全问题的。

。

上面这种没有活动要素的。也就是两边是一样的。称之为刚性系统

那好办，直接算组合就出来了。

无非是E6 ,E8换一下顺序。