在這篇文章中，我們將比較最近個(gè)人專案中使用的三種不同演算法的表現(xiàn)：ILP（整數(shù)線性規(guī)劃） 演算法、使用A* 演算法的本地演算法，以及使用Branch and Bound 演算法的最佳化解。所有演算法都使用相同的資料集進(jìn)行測(cè)試，ILP 和分支定界實(shí)現(xiàn)共享相同的工作負(fù)載，而 A* 實(shí)現(xiàn)由於效能限製而受到限制。

免責(zé)聲明：雖然我不會(huì)深入研究該專案的具體程式碼細(xì)節(jié)，但我會(huì)從中分享一些見(jiàn)解。該程式碼庫(kù)不打算公開(kāi)披露，這是尊重其機(jī)密性的免責(zé)聲明。

基準(zhǔn)測(cè)試結(jié)果

以下是所有三種演算法的基準(zhǔn)測(cè)試結(jié)果：

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

工作負(fù)載配置

所有演算法均使用同一組資料進(jìn)行測(cè)試，但實(shí)現(xiàn)之間的工作負(fù)載（即處理每個(gè)項(xiàng)目的次數(shù)）不同。

ILP 和分支定界實(shí)施工作量：

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* 實(shí)施工作量：

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},
}

工作量分析

為了了解這些工作負(fù)載對(duì)基準(zhǔn)測(cè)試結(jié)果的影響，我們來(lái)計(jì)算每個(gè)實(shí)現(xiàn)的迭代總數(shù)（即 Times 值的總和）。

總迭代次數(shù)：

• ILP 與分支定界實(shí)作：

  100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000

• A* 實(shí)作：

  1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46

工作負(fù)載比例：

ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74

這表示與 A* 實(shí)作相比，ILP 和分支定界實(shí)現(xiàn)處理的迭代次數(shù)大約多21.74 倍。

效能比較

讓我們根據(jù)工作負(fù)載差異來(lái)分解基準(zhǔn)測(cè)試結(jié)果。

觀察結(jié)果

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

• BenchmarkGenerateReportILP-24 與 BenchmarkGenerateReportLocal-24：
  • ILP 比本地 快99.80%，執(zhí)行時(shí)間從851,314,106 ns/op 減少到
  16943,097 >.

• BenchmarkGenerateReportILPParallel-24 與 BenchmarkBranchGenerateReportLocalParallel-24：

  • 分支和綁定並行比ILP並行快94.28%，執(zhí)行時(shí)間從187,871 ns/op減少到187,871 ns/op
  減少到
  ns /op
.

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

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

2. 吞吐量：
   • ILP 並行 和 分支定界並行 由於工作負(fù)載較高，可以處理
   大約 21.74 倍的迭代
   • 。
   A* 實(shí)現(xiàn)
   吞吐量困難不是因?yàn)榈螖?shù)顯著減少，而是因?yàn)橛洃涹w使用和實(shí)現(xiàn)效率低下。

不同工作負(fù)載對(duì)效能的影響 鑑於 ILP 和 Branch 演算法每次測(cè)試迭代處理

21.74 倍

的吞吐量，這種工作負(fù)載差異會(huì)影響每個(gè)演算法的效能和效率：

• ILP 和分支演算法：由於這些演算法可處理更大的吞吐量，因此它們針對(duì)更高的工作負(fù)載進(jìn)行了最佳化。儘管處理更多操作，但它們?nèi)员３指斓膱?zhí)行時(shí)間。這表明它們不僅計(jì)算效率高，而且非常適合高吞吐量場(chǎng)景。

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

在工作負(fù)載增加的情況下，ILP 和 Branch 將優(yōu)於 Local，因?yàn)樗鼈兡軌蛴行Ч芾砀叩耐掏铝?。相反，如果工作量減少，Local 演算法的效能可能更接近 ILP 和 Branch，但由於演算法效率的根本差異，仍然可能落後。

演算法概述

為了更清楚地了解每種演算法如何解決問(wèn)題，這裡對(duì)其機(jī)制和方法進(jìn)行了總體概述。

整數(shù)線性規(guī)劃 (ILP)

目的：

ILP 是一種最佳化技術(shù)，用於在數(shù)學(xué)模型中找到最佳結(jié)果（例如最大利潤(rùn)或最低成本），其要求由線性關(guān)係表示。它對(duì)於可以用線性約束和線性目標(biāo)函數(shù)表示的問(wèn)題特別有效。

一般工作流程：

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

2. 目標(biāo)函數(shù)：
   
   制定需要最大化或最小化的線性方程式。

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

4. 解決：
   
   利用 ILP 求解器找到?jīng)Q策變數(shù)的最佳值，在滿足所有限制的同時(shí)最大化或最小化目標(biāo)函數(shù)。

偽代碼：

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*演算法（本地實(shí)作）

目的：

A* 是一種尋路和圖遍歷演算法，以其效能和準(zhǔn)確性而聞名。它透過(guò)結(jié)合統(tǒng)一成本搜尋和純啟發(fā)式搜尋的特徵，有效地找到節(jié)點(diǎn)之間的最短路徑。

一般工作流程：

1. 初始化：
   
   從初始節(jié)點(diǎn)開(kāi)始並將其新增至優(yōu)先權(quán)佇列。

2. 循環(huán)：

   • 從優(yōu)先權(quán)佇列中刪除成本估計(jì)最低的節(jié)點(diǎn)。
   • 如果是目標(biāo)節(jié)點(diǎn)，則終止。
   • 否則，透過(guò)探索其鄰居來(lái)擴(kuò)展節(jié)點(diǎn)。
   • 對(duì)於每個(gè)鄰居，計(jì)算新的成本並相應(yīng)地更新優(yōu)先權(quán)隊(duì)列。

3. 終止：
   
   當(dāng)?shù)竭_(dá)目標(biāo)節(jié)點(diǎn)或優(yōu)先權(quán)佇列為空（表示不存在路徑）時(shí)，演算法結(jié)束。

偽代碼：

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

分支定界演算法

目的：

分支定界是一種有系統(tǒng)地探索解空間的最佳化演算法。它將問(wèn)題劃分為更小的子問(wèn)題（分支），並使用邊界來(lái)消除無(wú)法產(chǎn)生比當(dāng)前最佳解決方案更好的解決方案（邊界）的子問(wèn)題。

一般工作流程：

1. 初始化：
   
   從初始解決方案開(kāi)始，然後設(shè)定最知名的解決方案。

2. 分支：
   
   在每個(gè)節(jié)點(diǎn)，將問(wèn)題分成更小的子問(wèn)題。

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

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

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

6. 終止：
   
   當(dāng)所有分支都被修剪或探索後，最知名的解決方案就是最優(yōu)的。

偽代碼：

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

比較分析

對(duì)伺服器效能的影響

• 可擴(kuò)充性：

  • 分支和綁定實(shí)現(xiàn)展示了出色的可擴(kuò)展性，可以有效處理大量並發(fā)請(qǐng)求並減少延遲。
  • ILP Parallel 實(shí)作也表現(xiàn)出優(yōu)異的可擴(kuò)展性，能夠有效處理大量並發(fā)請(qǐng)求並減少延遲。
  • 由於效能限制，A* 實(shí)作不適合高負(fù)載環(huán)境。

• 資源利用率：

  • 分支和限界實(shí)現(xiàn)高效利用資源，記憶體消耗低，執(zhí)行時(shí)間快。
  • ILP Parallel 有效利用多核心 CPU，提供高吞吐量和可管理的記憶體消耗。
  • A* 實(shí)作 消耗過(guò)多內(nèi)存，可能導(dǎo)致資源耗盡。

工作負(fù)載對(duì)效能的影響

工作負(fù)載差異影響演算法的效能：

• 分支限界實(shí)現(xiàn)可以有效地處理與 ILP 實(shí)現(xiàn)相同的工作負(fù)載，提供快速的執(zhí)行時(shí)間和較低的記憶體使用量，使其適合擴(kuò)展。

• ILP 實(shí)作 由於最佳化的求解器，可以有效地處理更大的工作負(fù)載。

• A* 實(shí)作 由於高執(zhí)行時(shí)間和記憶體使用而導(dǎo)致效能不佳。

結(jié)論

使用最佳化解決方案與分支定界演算法進(jìn)行了額外的比較，這表明它在性能和資源利用率方面比 ILP 和 A* 演算法有顯著改進(jìn)。分支定界演算法使用的工作負(fù)載與 ILP 演算法相同。

基於分支和界限的BenchmarkBranchGenerateReportLocalParallel功能展示了卓越的效能改進(jìn)，使其非常適合需要高並發(fā)和高效資源管理的伺服器環(huán)境。

透過(guò)專注於利用分支定界方法的優(yōu)勢(shì)並針對(duì)特定問(wèn)題進(jìn)行最佳化，我們可以確保專案保持高效能和可擴(kuò)展性，能夠輕鬆處理不斷增長(zhǎng)的需求。

最後的想法

平衡效能、可擴(kuò)展性和開(kāi)發(fā)人員體驗(yàn)對(duì)於建立強(qiáng)大的應(yīng)用程式至關(guān)重要。 分支定界 方法已被證明是目前設(shè)定中最有效的方法，透過(guò)合理的開(kāi)發(fā)工作可帶來(lái)顯著的效能提升。

透過(guò)不斷分析、最佳化和利用每種演算法方法的優(yōu)勢(shì)，我們可以維護(hù)一個(gè)高效能、可擴(kuò)展且對(duì)開(kāi)發(fā)人員友善的系統(tǒng)。

以上是比較基準(zhǔn)測(cè)試：高吞吐量場(chǎng)景中的 ILP、A* 和分支定界演算法的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！