本文分享自天翼云開發者社區《利用排列組合法實現TOPN路徑計算》.作者：羅****斌

        在進行TOPN選路性能摸底時，發現其在100*100節點級別以上的兩兩互相探測情況下的選路性能不太理想，整體壓測后分析發現，選路算法部分是整個處理流程的瓶頸點。對此，我分析了下目前計算TOPN路徑所使用的深度優先遍歷算法，為了收斂計算量，我們添加了路徑深度來控制計算量，效果是顯著的，這是一期的優化方案。但是在此過程中為了控制路徑的深度也產生大量的回溯邏輯，計算量會比理論值多出不少，所以一定程度上產生了性能上的損耗。如果我們繼續在深度優先遍歷算法上進行優化，其效果不會太明顯（深度優先遍歷是使用窮舉法深入相鄰可達點，直到不可達時再回溯上一個訪問點）

        從以上分析得知，在深度優先遍歷方向繼續優化空間有限，我們需要探尋另一種可用于求解TOPN路徑的算法。從路徑結構上分析可知，其首尾固定，變動的只是在中間節點上，我們可以通過選取中間節點個數來控制路徑深度。因為經過中間節點的順序不同，產生的路徑也不一樣，那么我們在選取中間節點的同時也要對其進行全排序。那么這個求解TOPN路徑問題就轉化為組合排列問題，只要實現排列組合算法就能滿足我們的需求，其不存在空跑的回溯計算量，理論計算量與實際一致，損耗更小

        此次優化將更換路徑計算算法，我們將從以下兩方面進行優化：

  一 性能優化點

      1）TOPN路徑計算由之前的深度優先遍歷改為通過 組合排列 方式求解

      2）路徑中各點構成的有向圖使用 二維數組 表示可達性（之前是哈希map），提高讀寫速度

      3）組合排列算法優化，清理冗余邏輯，減少遍歷次數，減少拷貝次數，并預先分配內存防止自動擴容等（提升2倍以上）

      4）迪杰斯特拉和深度遍歷底層改造為使用二維數組獲取兩點之間的權重值（之前是哈希map）

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

  二 內存優化點

      1）減少不必要的數據冗余拷貝，減少數據的使用空間

      2）減少map使用，大量map在gc時情況不太理想