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

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

ベンチマーク結(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)成

すべてのアルゴリズムは同じデータセットを使用してテストされましたが、ワークロード (つまり、各項目が処理される回數(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ù)の合計數(shù) (つまり、Times 値の合計) を計算してみましょう。

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

• BenchmarkGenerateReportILP-24 と BenchmarkGenerateReportLocal-24:

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

• BenchmarkGenerateReportILPParallel-24 と BenchmarkBranchGenerateReportLocalParallel-24:

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

• BenchmarkGenerateReportILPParallel-24 と BenchmarkGenerateReportLocalParallel-24:

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

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

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

2. スループット:

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

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

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

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

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

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

アルゴリズムの概要

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

整數(shù)線形計畫法 (ILP)

目的:

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

一般的なワークフロー:

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

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

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

4. 解決:
   
   ILP ソルバーを利用して、すべての制約を満たしながら目的関數(shù)を最大化または最小化する決定変數(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* アルゴリズム (ローカル実裝)

目的:

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

一般的なワークフロー:

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

2. ループ:

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

3. 終了:
   
   アルゴリズムは、ゴール ノードに到達するか、優(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)的に探索する最適化アルゴリズムです。問題を小さなサブ問題に分割し (分岐)、境界を使用して、現(xiàn)在の最良の解決策 (境界) よりも優(yōu)れた解決策を生成できないサブ問題を排除します。

一般的なワークフロー:

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

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

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

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

• リソース使用率:

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

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

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

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

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

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

結(jié)論

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

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

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

最終的な考え

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

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

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