比較基準測試：高吞吐量場景中的 ILP、A* 和分支定界演算法
- Susan Sarandon原創
- 2024-11-06 04:44:02140瀏覽
在這篇文章中，我們將比較最近個人專案中使用的三種不同演算法的表現：ILP（整數線性規劃） 演算法、使用A* 演算法的本地演算法，以及使用Branch and Bound 演算法的最佳化解。所有演算法都使用相同的資料集進行測試，ILP 和分支定界實現共享相同的工作負載，而 A* 實現由於效能限製而受到限制。
免責聲明：雖然我不會深入研究該專案的具體程式碼細節，但我會從中分享一些見解。該程式碼庫不打算公開披露，這是尊重其機密性的免責聲明。
基準測試結果
以下是所有三種演算法的基準測試結果：
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
工作負載配置
所有演算法均使用同一組資料進行測試，但實現之間的工作負載（即處理每個項目的次數）不同。
ILP 和分支定界實施工作量：
plan := []Plan{
{ID: "1", Times: 100},
{ID: "2", Times: 150},
{ID: "3", Times: 200},
{ID: "8", Times: 50},
{ID: "9", Times: 75},
{ID: "10", Times: 80},
{ID: "11", Times: 90},
{ID: "12", Times: 85},
{ID: "13", Times: 60},
{ID: "14", Times: 110},
}
A* 實施工作量：
plan := []Plan{
{ID: "1", Times: 1},
{ID: "2", Times: 1},
{ID: "3", Times: 5},
{ID: "8", Times: 5},
{ID: "9", Times: 5},
{ID: "10", Times: 5},
{ID: "11", Times: 9},
{ID: "12", Times: 5},
{ID: "13", Times: 5},
{ID: "14", Times: 5},
}
工作量分析
為了了解這些工作負載對基準測試結果的影響，我們來計算每個實現的迭代總數（即 Times 值的總和）。
總迭代次數：
- ILP 與分支定界實作：
100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000
- A* 實作：
1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46
工作負載比例：
ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74
這表示與 A* 實作相比，ILP 和分支定界實現處理的迭代次數大約多21.74 倍。
效能比較
讓我們根據工作負載差異來分解基準測試結果。
| Benchmark | Runs | ns/op | B/op | allocs/op | Total Time (ns) |
|---|---|---|---|---|---|
| BenchmarkGenerateReportILP-24 | 724 | 1,694,029 | 30,332 | 181 | ≈ 1,225,836,996 |
| BenchmarkGenerateReportILPParallel-24 | 6,512 | 187,871 | 34,545 | 184 | ≈ 1,223,607,552 |
| BenchmarkBranchGenerateReportLocal-24 | 101,449 | 12,106 | 29,932 | 165 | ≈ 1,224,505,394 |
| BenchmarkGenerateReportLocal-24 | 2 | 851,314,106 | 559,466,456 | 7,379,756 | ≈ 1,702,628,212 |
| BenchmarkGenerateReportLocalParallel-24 | 3 | 349,605,952 | 559,422,440 | 7,379,837 | ≈ 1,048,817,856 |
| BenchmarkBranchGenerateReportLocalParallel-24 | 120,543 | 10,755 | 29,933 | 165 | ≈ 1,295,219,065 |
觀察結果
-
每個操作的執行時間：
-
BenchmarkGenerateReportILP-24 與 BenchmarkBranchGenerateReportLocal-24：
- 分支與綁定 比ILP 快99.29%，將執行時間從1,694,029 ns/op 減少到1,694,029 ns/op 減少到 12/ op
-
BenchmarkGenerateReportILP-24 與 BenchmarkBranchGenerateReportLocal-24：
-
BenchmarkGenerateReportILP-24 與 BenchmarkGenerateReportLocal-24：- ILP 比本地 快99.80%，執行時間從851,314,106 ns/op 減少到 16943,097 >.
-
BenchmarkGenerateReportILPParallel-24 與 BenchmarkBranchGenerateReportLocalParallel-24：
- 分支和綁定並行比ILP並行快94.28%，執行時間從187,871 ns/op減少到187,871 ns/op 減少到
. -
- BenchmarkGenerateReportILPParallel-24 與 BenchmarkGenerateReportLocalParallel-24：
- ILP 並行 比本地並行 快99.95%，將執行時間從349,605,952 ns/op 減少到🎜> 減少到
-
記憶體分配：- ILP 實作：
- 並行運行時記憶體使用和分配略有增加。 分支和綁定實作：
- 與 A* 實作相比，記憶體使用量和分配更低。 A* 實作：
-
吞吐量：- ILP 並行 和 分支定界並行 由於工作負載較高，可以處理 大約 21.74 倍的迭代
- 。 A* 實現
不同工作負載對效能的影響 鑑於 ILP 和 Branch 演算法每次測試迭代處理
21.74 倍- 的吞吐量，這種工作負載差異會影響每個演算法的效能和效率：
-
ILP 和分支演算法：由於這些演算法可處理更大的吞吐量，因此它們針對更高的工作負載進行了最佳化。儘管處理更多操作，但它們仍保持更快的執行時間。這表明它們不僅計算效率高，而且非常適合高吞吐量場景。 本地演算法：吞吐量較小，執行時間較長，演算法在處理增加的工作負載時效率較低。如果擴展到與 ILP 或 Branch 相同的吞吐量，其執行時間將顯著增加，這表明它對於高吞吐量情況並不理想。
在工作負載增加的情況下，ILP 和 Branch 將優於 Local，因為它們能夠有效管理更高的吞吐量。相反，如果工作量減少，Local 演算法的效能可能更接近 ILP 和 Branch，但由於演算法效率的根本差異，仍然可能落後。
演算法概述
為了更清楚地了解每種演算法如何解決問題，這裡對其機制和方法進行了總體概述。
整數線性規劃 (ILP)
目的：
ILP 是一種最佳化技術，用於在數學模型中找到最佳結果（例如最大利潤或最低成本），其要求由線性關係表示。它對於可以用線性約束和線性目標函數表示的問題特別有效。
一般工作流程：
定義變數：
確定代表要做出的選擇的決策變數。目標函數：
制定需要最大化或最小化的線性方程式。約束：
建立解必須滿足的線性不等式或等式。解決：
利用 ILP 求解器找到決策變數的最佳值，在滿足所有限制的同時最大化或最小化目標函數。
偽代碼：
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
A*演算法（本地實作）
目的：
A* 是一種尋路和圖遍歷演算法，以其效能和準確性而聞名。它透過結合統一成本搜尋和純啟發式搜尋的特徵，有效地找到節點之間的最短路徑。
一般工作流程：
初始化：
從初始節點開始並將其新增至優先權佇列。-
循環：
- 從優先權佇列中刪除成本估計最低的節點。
- 如果是目標節點，則終止。
- 否則，透過探索其鄰居來擴展節點。
- 對於每個鄰居，計算新的成本並相應地更新優先權隊列。
終止：
當到達目標節點或優先權佇列為空（表示不存在路徑）時，演算法結束。
偽代碼：
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
分支定界演算法
目的：
分支定界是一種有系統地探索解空間的最佳化演算法。它將問題劃分為更小的子問題（分支），並使用邊界來消除無法產生比當前最佳解決方案更好的解決方案（邊界）的子問題。
一般工作流程：
初始化：
從初始解決方案開始，然後設定最知名的解決方案。分支：
在每個節點，將問題分成更小的子問題。邊界：
計算每個分支中最佳可能解決方案的樂觀估計值（上限）。修剪：
丟棄上限比已知解決方案更差的分支。搜尋：
使用深度優先或最佳優先搜尋遞歸地探索剩餘分支。終止：
當所有分支都被修剪或探索後，最知名的解決方案就是最優的。
偽代碼：
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
比較分析
| Feature | ILP Implementation | Local (A*) Implementation | Branch and Bound Implementation |
|---|---|---|---|
| Optimization Approach | Formulates the problem as a set of linear equations and inequalities to find the optimal solution. | Searches through possible states using heuristics to find the most promising path to the goal. | Systematically explores and prunes the solution space to find optimal solutions efficiently. |
| Scalability | Handles large-scale problems efficiently by leveraging optimized solvers. | Performance can degrade with increasing problem size due to the exhaustive nature of state exploration. | Efficient for combinatorial problems, with pruning reducing the search space significantly. |
| Development Time | Faster implementation as it relies on existing ILP solvers and libraries. | Requires more time to implement, especially when dealing with complex state management and heuristics. | Moderate development time, balancing complexity and optimization benefits. |
| Flexibility | Highly adaptable to various linear optimization problems with clear constraints and objectives. | Best suited for problems where pathfinding to a goal is essential, with heuristic guidance. | Effective for a wide range of optimization problems, especially combinatorial ones. |
| Performance | Demonstrates superior performance in handling a higher number of iterations with optimized memory usage. | While effective for certain scenarios, struggles with high memory allocations and longer execution times under heavy workloads. | Shows significant performance improvements over ILP and A* with optimized memory usage and faster execution times. |
| Developer Experience | Improves developer experience by reducing the need for extensive coding and optimization efforts. | May require significant debugging and optimization to achieve comparable performance levels. | Balances performance with manageable development effort, leveraging existing strategies for optimization. |
| Integration | Currently integrates a C ILP module with Golang, facilitating efficient computation despite cross-language usage. | Fully implemented within Golang, but may face limitations in performance and scalability without optimizations. | Implemented in Golang, avoiding cross-language integration complexities and enhancing performance. |
對伺服器效能的影響
-
可擴充性：
- 分支和綁定實現展示了出色的可擴展性，可以有效處理大量並發請求並減少延遲。
- ILP Parallel 實作也表現出優異的可擴展性，能夠有效處理大量並發請求並減少延遲。
- 由於效能限制，A* 實作不適合高負載環境。
-
資源利用率：
- 分支和限界實現高效利用資源，記憶體消耗低，執行時間快。
- ILP Parallel 有效利用多核心 CPU，提供高吞吐量和可管理的記憶體消耗。
- A* 實作 消耗過多內存，可能導致資源耗盡。
工作負載對效能的影響
工作負載差異影響演算法的效能：
分支限界實現可以有效地處理與 ILP 實現相同的工作負載，提供快速的執行時間和較低的記憶體使用量，使其適合擴展。
ILP 實作 由於最佳化的求解器，可以有效地處理更大的工作負載。
A* 實作 由於高執行時間和記憶體使用而導致效能不佳。
結論
使用最佳化解決方案與分支定界演算法進行了額外的比較，這表明它在性能和資源利用率方面比 ILP 和 A* 演算法有顯著改進。分支定界演算法使用的工作負載與 ILP 演算法相同。
基於分支和界限的BenchmarkBranchGenerateReportLocalParallel功能展示了卓越的效能改進，使其非常適合需要高並發和高效資源管理的伺服器環境。
透過專注於利用分支定界方法的優勢並針對特定問題進行最佳化，我們可以確保專案保持高效能和可擴展性，能夠輕鬆處理不斷增長的需求。
最後的想法
平衡效能、可擴展性和開發人員體驗對於建立強大的應用程式至關重要。 分支定界 方法已被證明是目前設定中最有效的方法，透過合理的開發工作可帶來顯著的效能提升。
透過不斷分析、最佳化和利用每種演算法方法的優勢，我們可以維護一個高效能、可擴展且對開發人員友善的系統。
以上是比較基準測試：高吞吐量場景中的 ILP、A* 和分支定界演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！