比較基準測試：高吞吐量場景中的 ILP、A* 和分支定界演算法

在這篇文章中，我們將比較最近個人專案中使用的三種不同演算法的表現：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

觀察結果

1. 每個操作的執行時間：
   • BenchmarkGenerateReportILP-24 與 BenchmarkBranchGenerateReportLocal-24：
     • 分支與綁定 比ILP 快99.29%，將執行時間從1,694,029 ns/op 減少到1,694,029 ns/op 減少到
     12/ op
     .

• 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
  減少到
  ns /op
.

• BenchmarkGenerateReportILPParallel-24 與 BenchmarkGenerateReportLocalParallel-24：
  • ILP 並行 比本地並行 快99.95%，將執行時間從349,605,952 ns/op
  減少到🎜> 減少到
  .

1. 記憶體分配：
   ILP 實作：
   • 並行運行時記憶體使用和分配略有增加。
   分支和綁定實作：
   • 與 A* 實作相比，記憶體使用量和分配更低。
   A* 實作：
   極高的記憶體分配，導致資源利用率低。

2. 吞吐量：
   • ILP 並行 和 分支定界並行 由於工作負載較高，可以處理
   大約 21.74 倍的迭代
   • 。
   A* 實現
   吞吐量困難不是因為迭代次數顯著減少，而是因為記憶體使用和實現效率低下。

不同工作負載對效能的影響 鑑於 ILP 和 Branch 演算法每次測試迭代處理

21.74 倍

的吞吐量，這種工作負載差異會影響每個演算法的效能和效率：

• ILP 和分支演算法：由於這些演算法可處理更大的吞吐量，因此它們針對更高的工作負載進行了最佳化。儘管處理更多操作，但它們仍保持更快的執行時間。這表明它們不僅計算效率高，而且非常適合高吞吐量場景。

• 本地演算法：吞吐量較小，執行時間較長，演算法在處理增加的工作負載時效率較低。如果擴展到與 ILP 或 Branch 相同的吞吐量，其執行時間將顯著增加，這表明它對於高吞吐量情況並不理想。

在工作負載增加的情況下，ILP 和 Branch 將優於 Local，因為它們能夠有效管理更高的吞吐量。相反，如果工作量減少，Local 演算法的效能可能更接近 ILP 和 Branch，但由於演算法效率的根本差異，仍然可能落後。

演算法概述

為了更清楚地了解每種演算法如何解決問題，這裡對其機制和方法進行了總體概述。

整數線性規劃 (ILP)

目的：

ILP 是一種最佳化技術，用於在數學模型中找到最佳結果（例如最大利潤或最低成本），其要求由線性關係表示。它對於可以用線性約束和線性目標函數表示的問題特別有效。

一般工作流程：

1. 定義變數：
   
   確定代表要做出的選擇的決策變數。

2. 目標函數：
   
   制定需要最大化或最小化的線性方程式。

3. 約束：
   
   建立解必須滿足的線性不等式或等式。

4. 解決：
   
   利用 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* 是一種尋路和圖遍歷演算法，以其效能和準確性而聞名。它透過結合統一成本搜尋和純啟發式搜尋的特徵，有效地找到節點之間的最短路徑。

一般工作流程：

1. 初始化：
   
   從初始節點開始並將其新增至優先權佇列。

2. 循環：

   • 從優先權佇列中刪除成本估計最低的節點。
   • 如果是目標節點，則終止。
   • 否則，透過探索其鄰居來擴展節點。
   • 對於每個鄰居，計算新的成本並相應地更新優先權隊列。

3. 終止：
   
   當到達目標節點或優先權佇列為空（表示不存在路徑）時，演算法結束。

偽代碼：

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

分支定界演算法

目的：

分支定界是一種有系統地探索解空間的最佳化演算法。它將問題劃分為更小的子問題（分支），並使用邊界來消除無法產生比當前最佳解決方案更好的解決方案（邊界）的子問題。

一般工作流程：

1. 初始化：
   
   從初始解決方案開始，然後設定最知名的解決方案。

2. 分支：
   
   在每個節點，將問題分成更小的子問題。

3. 邊界：
   
   計算每個分支中最佳可能解決方案的樂觀估計值（上限）。

4. 修剪：
   
   丟棄上限比已知解決方案更差的分支。

5. 搜尋：
   
   使用深度優先或最佳優先搜尋遞歸地探索剩餘分支。

6. 終止：
   
   當所有分支都被修剪或探索後，最知名的解決方案就是最優的。

偽代碼：

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中文網其他相關文章！