百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   feng-kuang-shen-shi-92 网友的相关建议: 
      

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

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

答案是缩点,即把回路当成一个要素(结点)来处理。

什么叫缩点?

上面有缩点的示意图。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





  

相关话题

  如何显式构造出包含于[0, 1]Q的正测度闭集F? 
  开发人员如何构建自己的学习笔记系统? 
  .NET 下的性能问题如何定位? 
  哪段代码最能代表程序员的暴力美学? 
  机器学习的理论方向 PhD 是否真的会接触那么多现代数学(黎曼几何、代数拓扑之类)? 
  一堆n维空间的由m个点组成的点集,m大于n,我们只知道它们之间的距离,能否判断所在空间的维数? 
  哪些开发会用到微积分、离散数学、线性代数、概率论的知识? 
  如何直接跳出深层递归而不是一层一层跳出? 
  一个程序员的水平能差到什么程度? 
  如何直接跳出深层递归而不是一层一层跳出? 

前一个讨论
孩子话太多怎么办?
下一个讨论
为什么中国女人更容易找到老外当老公,中国男人找外国老婆的就少很多?





© 2025-06-25 - tinynew.org. All Rights Reserved.
© 2025-06-25 - tinynew.org. 保留所有权利