利用排列组合法实现 TOPN 路径计算

本文分享自天翼云开发者社区《利用排列组合法实现TOPN路径计算》.作者：罗****斌

1 背景

在进行 TOPN 选路性能摸底时，发现其在 100*100 节点级别以上的两两互相探测情况下的选路性能不太理想，整体压测后分析发现，选路算法部分是整个处理流程的瓶颈点。对此，我分析了下目前计算 TOPN 路径所使用的深度优先遍历算法，为了收敛计算量，我们添加了路径深度来控制计算量，效果是显著的，这是一期的优化方案。但是在此过程中为了控制路径的深度也产生大量的回溯逻辑，计算量会比理论值多出不少，所以一定程度上产生了性能上的损耗。如果我们继续在深度优先遍历算法上进行优化，其效果不会太明显（深度优先遍历是使用穷举法深入相邻可达点，直到不可达时再回溯上一个访问点）

2 方案

从以上分析得知，在深度优先遍历方向继续优化空间有限，我们需要探寻另一种可用于求解 TOPN 路径的算法。从路径结构上分析可知，其首尾固定，变动的只是在中间节点上，我们可以通过选取中间节点个数来控制路径深度。因为经过中间节点的顺序不同，产生的路径也不一样，那么我们在选取中间节点的同时也要对其进行全排序。那么这个求解 TOPN 路径问题就转化为组合排列问题，只要实现排列组合算法就能满足我们的需求，其不存在空跑的回溯计算量，理论计算量与实际一致，损耗更小

此次优化将更换路径计算算法，我们将从以下两方面进行优化：

一 性能优化点

1）TOPN 路径计算由之前的深度优先遍历改为通过 组合排列 方式求解

2）路径中各点构成的有向图使用 二维数组 表示可达性（之前是哈希 map），提高读写速度

3）组合排列算法优化，清理冗余逻辑，减少遍历次数，减少拷贝次数，并预先分配内存防止自动扩容等（提升 2 倍以上）

4）迪杰斯特拉和深度遍历底层改造为使用二维数组获取两点之间的权重值（之前是哈希 map）

5）使用高性能 json 库提升速度

二 内存优化点

1）减少不必要的数据冗余拷贝，减少数据的使用空间

2）减少 map 使用，大量 map 在 gc 时情况不太理想