在這篇文章中,我們將比較最近個人專案中使用的三種不同演算法的表現: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
所有演算法均使用同一組資料進行測試,但實現之間的工作負載(即處理每個項目的次數)不同。
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}, }
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 值的總和)。
100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000
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 與 BenchmarkGenerateReportLocal-24:
BenchmarkGenerateReportILPParallel-24 與 BenchmarkBranchGenerateReportLocalParallel-24:
記憶體分配:
吞吐量:
不同工作負載對效能的影響 鑑於 ILP 和 Branch 演算法每次測試迭代處理
21.74 倍ILP 和分支演算法:由於這些演算法可處理更大的吞吐量,因此它們針對更高的工作負載進行了最佳化。儘管處理更多操作,但它們仍保持更快的執行時間。這表明它們不僅計算效率高,而且非常適合高吞吐量場景。
本地演算法:吞吐量較小,執行時間較長,演算法在處理增加的工作負載時效率較低。如果擴展到與 ILP 或 Branch 相同的吞吐量,其執行時間將顯著增加,這表明它對於高吞吐量情況並不理想。
在工作負載增加的情況下,ILP 和 Branch 將優於 Local,因為它們能夠有效管理更高的吞吐量。相反,如果工作量減少,Local 演算法的效能可能更接近 ILP 和 Branch,但由於演算法效率的根本差異,仍然可能落後。
為了更清楚地了解每種演算法如何解決問題,這裡對其機制和方法進行了總體概述。
目的:
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* 是一種尋路和圖遍歷演算法,以其效能和準確性而聞名。它透過結合統一成本搜尋和純啟發式搜尋的特徵,有效地找到節點之間的最短路徑。
一般工作流程:
初始化:
從初始節點開始並將其新增至優先權佇列。
循環:
終止:
當到達目標節點或優先權佇列為空(表示不存在路徑)時,演算法結束。
偽代碼:
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 實現相同的工作負載,提供快速的執行時間和較低的記憶體使用量,使其適合擴展。
ILP 實作 由於最佳化的求解器,可以有效地處理更大的工作負載。
A* 實作 由於高執行時間和記憶體使用而導致效能不佳。
使用最佳化解決方案與分支定界演算法進行了額外的比較,這表明它在性能和資源利用率方面比 ILP 和 A* 演算法有顯著改進。分支定界演算法使用的工作負載與 ILP 演算法相同。
基於分支和界限的BenchmarkBranchGenerateReportLocalParallel功能展示了卓越的效能改進,使其非常適合需要高並發和高效資源管理的伺服器環境。
透過專注於利用分支定界方法的優勢並針對特定問題進行最佳化,我們可以確保專案保持高效能和可擴展性,能夠輕鬆處理不斷增長的需求。
平衡效能、可擴展性和開發人員體驗對於建立強大的應用程式至關重要。 分支定界 方法已被證明是目前設定中最有效的方法,透過合理的開發工作可帶來顯著的效能提升。
透過不斷分析、最佳化和利用每種演算法方法的優勢,我們可以維護一個高效能、可擴展且對開發人員友善的系統。
以上是比較基準測試:高吞吐量場景中的 ILP、A* 和分支定界演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!