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

免責(zé)聲明：雖然我不會(huì)深入研究該項(xiàng)目的具體代碼細(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ù)載配置

所有算法均使用同一組數(shù)據(jù)進(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í)現(xiàn)：

  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í)現(xiàn)相比，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 減少到 12,106 ns/op .

• BenchmarkGenerateReportILP-24 與 BenchmarkGenerateReportLocal-24：

  • ILP 比 本地 快 99.80%，將執(zhí)行時(shí)間從 851,314,106 ns/op 減少到 1,694,029 ns/op.

• BenchmarkGenerateReportILPParallel-24 與 BenchmarkBranchGenerateReportLocalParallel-24：

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

• BenchmarkGenerateReportILPParallel-24 與 BenchmarkGenerateReportLocalParallel-24：

  • ILP 并行 比 本地并行 快 99.95%，將執(zhí)行時(shí)間從 349,605,952 ns/op 減少到 187,871 ns/op .

1. 內(nèi)存分配：

   • ILP 實(shí)現(xiàn)： 并行運(yùn)行時(shí)內(nèi)存使用和分配略有增加。
   • 分支和綁定實(shí)現(xiàn)：與 A* 實(shí)現(xiàn)相比，內(nèi)存使用量和分配更低。
   • A* 實(shí)現(xiàn)： 極高的內(nèi)存分配，導(dǎo)致資源利用率低下。

2. 吞吐量：

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

不同工作負(fù)載對(duì)性能的影響

鑒于 ILP 和 Branch 算法每次測(cè)試迭代處理 21.74 倍 的吞吐量，這種工作負(fù)載差異會(huì)影響每個(gè)算法的性能和效率：

• ILP 和分支算法：由于這些算法可處理更大的吞吐量，因此它們針對(duì)更高的工作負(fù)載進(jìn)行了優(yōu)化。盡管處理更多操作，但它們?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 是一種優(yōu)化技術(shù)，用于在數(shù)學(xué)模型中找到最佳結(jié)果（例如最大利潤(rùn)或最低成本），其要求由線性關(guān)系表示。它對(duì)于可以用線性約束和線性目標(biāo)函數(shù)表示的問(wèn)題特別有效。

一般工作流程：

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

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

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

4. 解決：
   
   利用 ILP 求解器找到?jīng)Q策變量的最優(yōu)值，在滿足所有約束的同時(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í)現(xiàn)）

目的：

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

一般工作流程：

1. 初始化：
   
   從初始節(jié)點(diǎn)開(kāi)始并將其添加到優(yōu)先級(jí)隊(duì)列中。

2. 循環(huán)：

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

3. 終止：
   
   當(dāng)?shù)竭_(dá)目標(biāo)節(jié)點(diǎn)或優(yōu)先級(jí)隊(duì)列為空（表示不存在路徑）時(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)地探索解空間的優(yōu)化算法。它將問(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ì)比分析

對(duì)服務(wù)器性能的影響

• 可擴(kuò)展性：

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

• 資源利用率：

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

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

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

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

• ILP 實(shí)施 由于優(yōu)化的求解器，可以有效地處理更大的工作負(fù)載。

• A* 實(shí)現(xiàn) 由于高執(zhí)行時(shí)間和內(nèi)存使用而導(dǎo)致性能不佳。

結(jié)論

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

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

通過(guò)專注于利用分支定界方法的優(yōu)勢(shì)并針對(duì)特定問(wèn)題對(duì)其進(jìn)行優(yōu)化，我們可以確保項(xiàng)目保持高性能和可擴(kuò)展性，能夠輕松處理不斷增長(zhǎng)的需求。

最后的想法

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

通過(guò)不斷分析、優(yōu)化和利用每種算法方法的優(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)文章！