このブログ投稿では、最近の個人プロジェクトで使用された 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
すべてのアルゴリズムは同じデータセットを使用してテストされましたが、ワークロード (つまり、各項目が処理される回数) は実装間で異なりました。
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},
}
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 値の合計) を計算してみましょう。
100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000
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 と BenchmarkGenerateReportLocal-24:
BenchmarkGenerateReportILPParallel-24 と BenchmarkBranchGenerateReportLocalParallel-24:
BenchmarkGenerateReportILPParallel-24 と BenchmarkGenerateReportLocalParallel-24:
メモリ割り当て:
スループット:
ILP アルゴリズムとブランチ アルゴリズムがテスト反復ごとに 21.74 倍 多くのスループットを処理することを考えると、このワークロードの違いは各アルゴリズムのパフォーマンスと効率に影響します。
ILP および分岐アルゴリズム: これらはより大きなスループットを処理するため、より高いワークロード向けに最適化されています。より多くの操作を処理するにもかかわらず、より速い実行時間を維持します。これは、計算効率が高いだけでなく、高スループットのシナリオにも適していることを示唆しています。
ローカル アルゴリズム: このアルゴリズムはスループットが小さく、実行時間が長いため、増加したワークロードを処理する効率が低くなります。 ILP または Branch と同じスループットにスケールすると、実行時間が大幅に増加するため、高スループットの場合には理想的ではないことがわかります。
ワークロードが増加するシナリオでは、ILP と Branch はより高いスループットを効率的に管理できるため、ローカル よりも優れたパフォーマンスを発揮します。逆に、ワークロードが削減された場合、ローカル アルゴリズムは 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* は、そのパフォーマンスと精度で知られるパス探索およびグラフ走査アルゴリズムです。均一コスト検索と純粋なヒューリスティック検索の機能を組み合わせて、ノード間の最短パスを効率的に見つけます。
一般的なワークフロー:
初期化:
最初のノードから始めて、それを優先キューに追加します。
ループ:
終了:
アルゴリズムは、ゴール ノードに到達するか、優先キューが空になる (パスが存在しないことを示す) と終了します。
疑似コード:
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 実装と同じワークロードを効率的に処理し、高速な実行時間と低いメモリ使用量を実現し、スケーリングに適しています。
ILP 実装 は、最適化されたソルバーにより、より大きなワークロードを効率的に処理します。
A* 実装 は、実行時間とメモリ使用量が多いため、パフォーマンスに問題があります。
分岐および境界アルゴリズム を使用した最適化されたソリューションを使用した追加の比較が追加されました。これは、パフォーマンスとリソース使用率の点で ILP および A* アルゴリズムよりも大幅に改善されたことを示しています。ブランチおよびバウンド アルゴリズムで使用されるワークロードは、ILP アルゴリズムと同じです。
ブランチおよびバインドベースの BenchmarkBranchGenerateReportLocalParallel 関数は、並外れたパフォーマンスの向上を示し、高い同時実行性と効率的なリソース管理を要求するサーバー環境に非常に適しています。
分岐結合アプローチの長所を活用し、特定の問題に合わせて最適化することに重点を置くことで、プロジェクトのパフォーマンスとスケーラビリティを維持し、増大する要求に簡単に対応できるようにすることができます。
堅牢なアプリケーションを構築するには、パフォーマンス、スケーラビリティ、開発者エクスペリエンスのバランスをとることが重要です。 ブランチとバインド アプローチは、現在のセットアップで最も効率的であることが証明されており、合理的な開発労力で大幅なパフォーマンスの向上を実現します。
各アルゴリズムのアプローチの長所を継続的にプロファイリング、最適化し、活用することで、高性能でスケーラブルで開発者に優しいシステムを維持できます。
以上が比較ベンチマーク: 高スループット シナリオにおける ILP、A*、および分岐および制限されたアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
