比較ベンチマーク: 高スループットシナリオにおける ILP、A*、および分岐および制限されたアルゴリズム-Golang-php.cn

Comparative Benchmarking: ILP, A*, and Branch and Bound Algorithms in High-Throughput Scenarios

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

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

ベンチマーク結果

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

ログイン後にコピー

ワークロード構成

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

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

ログイン後にコピー

これは、ILP および分岐および境界の実装が、A* 実装と比較して約 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

観察

オペレーションあたりの実行時間:
- 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 に短縮します。 .

メモリ割り当て:
- ILP 実装: 並列実行時のメモリ使用量と割り当てがわずかに増加します。
- ブランチ実装とバインド実装: A* 実装と比較してメモリ使用量とメモリ割り当てが少なくなります。
- A* 実装: メモリ割り当てが非常に多く、リソースの使用効率が非効率になります。
スループット:
- ILP Parallel と Branch and Bound Parallel は、ワークロードが高いため、約 21.74 倍の反復を処理できます。
- A* 実装 は、反復回数が大幅に少ないためではなく、メモリ使用量と実装が非効率であるため、スループットに苦労しています。

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

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

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

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

アルゴリズムの概要

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

整数線形計画法 (ILP)

目的:

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

一般的なワークフロー:

変数の定義:

行うべき選択を表す決定変数を特定します。
目的関数:

最大化または最小化する必要がある一次方程式を定式化します。
制約:

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

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

一般的なワークフロー:

初期化:

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

アルゴリズムは、ゴールノードに到達するか、優先キューが空になる (パスが存在しないことを示す) と終了します。

疑似コード:

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 は、解決空間を系統的に探索する最適化アルゴリズムです。問題を小さなサブ問題に分割し (分岐)、境界を使用して、現在の最良の解決策 (境界) よりも優れた解決策を生成できないサブ問題を排除します。

一般的なワークフロー:

初期化:

初期ソリューションから始めて、最もよく知られているソリューションを設定します。
分岐:

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

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

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

深さ優先または最良優先の検索を使用して、残りのブランチを再帰的に探索します。
終了:

すべてのブランチが枝刈りまたは調査されると、最もよく知られているソリューションが最適になります。

疑似コード:

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 関数は、並外れたパフォーマンスの向上を示し、高い同時実行性と効率的なリソース管理を要求するサーバー環境に非常に適しています。

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