このブログ投稿では、最近の個(gè)人プロジェクトで使用された 3 つの異なるアルゴリズムのパフォーマンスを比較します。ILP (整數(shù)線形計(jì)畫(huà)法) アルゴリズム、A* アルゴリズムを使用したローカル アルゴリズム、および Branch and Bound アルゴリズムを使用した最適化されたソリューション。すべてのアルゴリズムは同じデータセットを使用してテストされ、ILP と分岐および境界の実裝は同じワークロードを共有しましたが、A* 実裝はパフォーマンス上の制約により制限されました。

免責(zé)事項(xiàng): プロジェクトの特定のコードの詳細(xì)については掘り下げませんが、そこから得た洞察をいくつか共有します。コードベースは一般公開(kāi)を目的としていないため、これは機(jī)密性を尊重するための免責(zé)事項(xiàng)として機(jī)能します。

ベンチマーク結(jié)果

3 つのアルゴリズムすべてのベンチマーク結(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

ワークロード構(gòu)成

すべてのアルゴリズムは同じデータセットを使用してテストされましたが、ワークロード (つまり、各項(xiàng)目が処理される回?cái)?shù)) は実裝間で異なりました。

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

ワークロード分析

ベンチマーク結(jié)果に対するこれらのワークロードの影響を理解するために、各実裝の反復(fù)の合計(jì)數(shù) (つまり、Times 値の合計(jì)) を計(jì)算してみましょう。

総反復(fù)數(shù):

• 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

これは、ILP および分岐および境界の実裝が、A* 実裝と比較して約 21.74 倍 の反復(fù)を処理していることを意味します。

性能比較

ワークロードの違いに関連してベンチマークの結(jié)果を分析してみましょう。

観察

1. オペレーションあたりの実行時(shí)間:
   • BenchmarkGenerateReportILP-24 と BenchmarkBranchGenerateReportLocal-24:
     • Branch and Bound は ILP よりも 99.29% 高速で、実行時(shí)間を 1,694,029 ns/op から 12,106 ns/op に短縮します。 .

• BenchmarkGenerateReportILP-24 と BenchmarkGenerateReportLocal-24:

  • ILP は ローカル よりも 99.80% 高速で、実行時(shí)間を 851,314,106 ns/op から 1,694,029 ns/op に短縮します。 >.

• BenchmarkGenerateReportILPParallel-24 と BenchmarkBranchGenerateReportLocalParallel-24:

  • 分岐およびバインドされた並列は、ILP 並列よりも 94.28% 高速で、実行時(shí)間を 187,871 ns/op から 10,755 ns に短縮します。 /op.

• BenchmarkGenerateReportILPParallel-24 と BenchmarkGenerateReportLocalParallel-24:

  • ILP Parallel は Local Parallel よりも 99.95% 高速で、実行時(shí)間を 349,605,952 ns/op から 187,871 ns/op に短縮します。 .

1. メモリ割り當(dāng)て:

   • ILP 実裝: 並列実行時(shí)のメモリ使用量と割り當(dāng)てがわずかに増加します。
   • ブランチ実裝とバインド実裝: A* 実裝と比較してメモリ使用量とメモリ割り當(dāng)てが少なくなります。
   • A* 実裝: メモリ割り當(dāng)てが非常に多く、リソースの使用効率が非効率になります。

2. スループット:

   • ILP Parallel と Branch and Bound Parallel は、ワークロードが高いため、約 21.74 倍の反復(fù)を処理できます。
   • A* 実裝 は、反復(fù)回?cái)?shù)が大幅に少ないためではなく、メモリ使用量と実裝が非効率であるため、スループットに苦労しています。

さまざまなワークロードがパフォーマンスに與える影響

ILP アルゴリズムとブランチ アルゴリズムがテスト反復(fù)ごとに 21.74 倍 多くのスループットを処理することを考えると、このワークロードの違いは各アルゴリズムのパフォーマンスと効率に影響します。

• ILP および分岐アルゴリズム: これらはより大きなスループットを処理するため、より高いワークロード向けに最適化されています。より多くの操作を処理するにもかかわらず、より速い実行時(shí)間を維持します。これは、計(jì)算効率が高いだけでなく、高スループットのシナリオにも適していることを示唆しています。

• ローカル アルゴリズム: このアルゴリズムはスループットが小さく、実行時(shí)間が長(zhǎng)いため、増加したワークロードを処理する効率が低くなります。 ILP または Branch と同じスループットにスケールすると、実行時(shí)間が大幅に増加するため、高スループットの場(chǎng)合には理想的ではないことがわかります。

ワークロードが増加するシナリオでは、ILP と Branch はより高いスループットを効率的に管理できるため、ローカル よりも優(yōu)れたパフォーマンスを発揮します。逆に、ワークロードが削減された場(chǎng)合、ローカル アルゴリズムは ILP およびブランチに近いパフォーマンスを発揮する可能性がありますが、アルゴリズム効率の根本的な違いにより、依然として遅れが生じる可能性があります。

アルゴリズムの概要

各アルゴリズムが問(wèn)題解決にどのようにアプローチするかをより明確に理解できるように、ここではそのメカニズムと方法論の概要を示します。

整數(shù)線形計(jì)畫(huà)法 (ILP)

目的:

ILP は、要件が線形関係で表される數(shù)學(xué)的モデルで最良の結(jié)果 (最大利益や最小コストなど) を見(jiàn)つけるために使用される最適化手法です。これは、線形制約と線形目的関數(shù)の観點(diǎn)から表現(xiàn)できる問(wèn)題に特に効果的です。

一般的なワークフロー:

1. 変數(shù)の定義:
   
   行うべき選択を表す決定変數(shù)を特定します。

2. 目的関數(shù):
   
   最大化または最小化する必要がある一次方程式を定式化します。

3. 制約:
   
   解が満たさなければならない線形不等式または等式を確立します。

4. 解決:
   
   ILP ソルバーを利用して、すべての制約を満たしながら目的関數(shù)を最大化または最小化する決定変數(shù)の最適値を見(jiàn)つけます。

疑似コード:

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* は、そのパフォーマンスと精度で知られるパス探索およびグラフ走査アルゴリズムです。均一コスト検索と純粋なヒューリスティック検索の機(jī)能を組み合わせて、ノード間の最短パスを効率的に見(jiàn)つけます。

一般的なワークフロー:

1. 初期化:
   
   最初のノードから始めて、それを優(yōu)先キューに追加します。

2. ループ:

   • コスト推定値が最も低いノードを優(yōu)先キューから削除します。
   • ゴールノードの場(chǎng)合は終了します。
   • それ以外の場(chǎng)合は、近隣ノードを探索してノードを拡張します。
   • 近隣ごとに、新しいコストを計(jì)算し、それに応じて優(yōu)先キューを更新します。

3. 終了:
   
   アルゴリズムは、ゴール ノードに到達(dá)するか、優(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

分岐および拘束されたアルゴリズム

目的:

Branch and Bound は、解決空間を系統(tǒng)的に探索する最適化アルゴリズムです。問(wèn)題を小さなサブ問(wèn)題に分割し (分岐)、境界を使用して、現(xiàn)在の最良の解決策 (境界) よりも優(yōu)れた解決策を生成できないサブ問(wèn)題を排除します。

一般的なワークフロー:

1. 初期化:
   
   初期ソリューションから始めて、最もよく知られているソリューションを設(shè)定します。

2. 分岐:
   
   各ノードで、問(wèn)題をより小さなサブ問(wèn)題に分割します。

3. 境界:
   
   各ブランチで可能な最良の解決策の楽観的な推定値 (上限) を計(jì)算します。

4. 剪定:
   
   上限が最もよく知られている解決策よりも悪いブランチを破棄します。

5. 検索:
   
   深さ優(yōu)先または最良優(yōu)先の検索を使用して、殘りのブランチを再帰的に探索します。

6. 終了:
   
   すべてのブランチが枝刈りまたは調(diào)査されると、最もよく知られているソリューションが最適になります。

疑似コード:

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

比較分析

サーバーのパフォーマンスへの影響

• スケーラビリティ:

  • ブランチとバインドの実裝は、優(yōu)れたスケーラビリティを示し、待ち?xí)r間を短縮しながら多數(shù)の同時(shí)リクエストを効率的に処理します。
  • ILP Parallel 実裝は優(yōu)れたスケーラビリティも示し、待ち?xí)r間を短縮しながら多數(shù)の同時(shí)リクエストを効率的に処理します。
  • A* 実裝は、パフォーマンス上の制限があるため、高負(fù)荷環(huán)境には適していません。

• リソース使用率:

  • ブランチ実裝とバインド実裝は、メモリ消費(fèi)量が少なく、実行時(shí)間が速いため、リソースを効率的に利用します。
  • ILP Parallel はマルチコア CPU を効果的に利用し、管理可能なメモリ消費(fèi)量で高いスループットを提供します。
  • A* 実裝 は過(guò)剰なメモリを消費(fèi)し、リソースの枯渇につながる可能性があります。

ワークロードがパフォーマンスに與える影響

ワークロードの違いはアルゴリズムのパフォーマンスに影響します:

• ブランチおよびバインドされた実裝は、ILP 実裝と同じワークロードを効率的に処理し、高速な実行時(shí)間と低いメモリ使用量を?qū)g現(xiàn)し、スケーリングに適しています。

• ILP 実裝 は、最適化されたソルバーにより、より大きなワークロードを効率的に処理します。

• A* 実裝 は、実行時(shí)間とメモリ使用量が多いため、パフォーマンスに問(wèn)題があります。

結(jié)論

分岐および境界アルゴリズム を使用した最適化されたソリューションを使用した追加の比較が追加されました。これは、パフォーマンスとリソース使用率の點(diǎn)で ILP および A* アルゴリズムよりも大幅に改善されたことを示しています。ブランチおよびバウンド アルゴリズムで使用されるワークロードは、ILP アルゴリズムと同じです。

ブランチおよびバインドベースの BenchmarkBranchGenerateReportLocalParallel 関數(shù)は、並外れたパフォーマンスの向上を示し、高い同時(shí)実行性と効率的なリソース管理を要求するサーバー環(huán)境に非常に適しています。

分岐結(jié)合アプローチの長(zhǎng)所を活用し、特定の問(wèn)題に合わせて最適化することに重點(diǎn)を置くことで、プロジェクトのパフォーマンスとスケーラビリティを維持し、増大する要求に簡(jiǎn)単に対応できるようにすることができます。

最終的な考え

堅(jiān)牢なアプリケーションを構(gòu)築するには、パフォーマンス、スケーラビリティ、開(kāi)発者エクスペリエンスのバランスをとることが重要です。 ブランチとバインド アプローチは、現(xiàn)在のセットアップで最も効率的であることが証明されており、合理的な開(kāi)発労力で大幅なパフォーマンスの向上を?qū)g現(xiàn)します。

各アルゴリズムのアプローチの長(zhǎng)所を継続的にプロファイリング、最適化し、活用することで、高性能でスケーラブルで開(kāi)発者に優(yōu)しいシステムを維持できます。

以上が比較ベンチマーク: 高スループット シナリオにおける ILP、A*、および分岐および制限されたアルゴリズムの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。