Analyse comparative : algorithmes ILP, A* et Branch and Bound dans des scénarios à haut débit

Dans cet article de blog, nous comparerons les performances de trois algorithmes différents utilisés dans un projet personnel récent : l'algorithme ILP (Integer Linear Programming), le Algorithme local utilisant l'algorithme A* et une solution optimisée utilisant l'algorithme Branch and Bound. Tous les algorithmes ont été testés en utilisant le même ensemble de données, les implémentations ILP et Branch and Bound partageant la même charge de travail, tandis que l'implémentation A* était limitée en raison de contraintes de performances.

Avertissement : Même si je n'entrerai pas dans les détails spécifiques du code du projet, j'en partagerai quelques idées. La base de code n'est pas destinée à être divulguée au public, et cela sert d'avertissement quant au respect de sa confidentialité.

Résultats de référence

Voici les résultats de référence pour les trois algorithmes :

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
</my-package></my-project></my-package></my-project>

Configuration de la charge de travail

Tous les algorithmes ont été testés en utilisant le même ensemble de données, mais la charge de travail (c'est-à-dire le nombre de fois que chaque élément est traité) différait entre les implémentations.

Charge de travail de mise en œuvre ILP et Branch and Bound :

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* Charge de travail de mise en œuvre :

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

Analyse de la charge de travail

Pour comprendre l'impact de ces charges de travail sur les résultats du benchmark, calculons le nombre total d'itérations (c'est-à-dire la somme des valeurs Times) pour chaque implémentation.

Itérations totales :

• Implémentations ILP et Branch and Bound :

  100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000

• A* Implémentation :

  1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46

Ratio de charge de travail :

ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74

Cela signifie que les implémentations ILP et Branch and Bound gèrent environ 21,74 fois plus d'itérations par rapport à l'implémentation A*.

Comparaison des performances

Décomposons les résultats du benchmark par rapport aux différences de charge de travail.

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

Observations

1. Durée d'exécution par opération :
   • BenchmarkGenerateReportILP-24 contre BenchmarkBranchGenerateReportLocal-24 :
     • Branch and Bound est 99,29 % plus rapide que ILP, réduisant le temps d'exécution de 1 694 029 ns/op à 12 106 ns/op .

• BenchmarkGenerateReportILP-24 vs BenchmarkGenerateReportLocal-24 :

  • ILP est 99,80 % plus rapide que Local, réduisant le temps d'exécution de 851 314 106 ns/op à 1 694 029 ns/op.

• BenchmarkGenerateReportILPParallel-24 vs BenchmarkBranchGenerateReportLocalParallel-24 :

  • Branch and Bound Parallel est 94,28 % plus rapide que ILP Parallel, réduisant le temps d'exécution de 187 871 ns/op à 10 755 ns /op.

• BenchmarkGenerateReportILPParallel-24 vs BenchmarkGenerateReportLocalParallel-24 :

  • ILP Parallel est 99,95 % plus rapide que Local Parallel, réduisant le temps d'exécution de 349 605 952 ns/op à 187 871 ns/op .

1. Allocations de mémoire :

   • Implémentations ILP : Légère augmentation de l'utilisation et des allocations de mémoire lors de l'exécution en parallèle.
   • Implémentations Branch and Bound : Utilisation et allocations de mémoire réduites par rapport aux implémentations A*.
   • A* Implémentations : Allocations de mémoire extrêmement élevées, conduisant à une utilisation inefficace des ressources.

2. Débit :

   • ILP Parallel et Branch and Bound Parallel peuvent gérer environ 21,74 fois plus d'itérations en raison de la charge de travail plus élevée.
   • Les Les implémentations A* ont du mal à gérer le débit, non pas en raison du nombre d'itérations nettement inférieur, mais en raison d'une utilisation et d'une implémentation inefficaces de la mémoire.

Impact de la charge de travail variable sur les performances

Étant donné que les algorithmes ILP et Branch gèrent 21,74 fois plus de débit par itération de test, cette différence de charge de travail a un impact sur les performances et l'efficacité de chaque algorithme :

• Algorithmes ILP et de branche : comme ceux-ci gèrent un débit plus élevé, ils sont optimisés pour des charges de travail plus élevées. Bien qu’ils gèrent davantage d’opérations, ils maintiennent des temps d’exécution plus rapides. Cela suggère qu'ils sont non seulement efficaces sur le plan informatique, mais également bien adaptés aux scénarios à haut débit.

• Algorithme local : avec un débit plus faible et un temps d'exécution plus élevé, cet algorithme est moins efficace pour gérer des charges de travail accrues. S'il était adapté au même débit qu'ILP ou Branch, son temps d'exécution augmenterait considérablement, ce qui indique qu'il n'est pas idéal pour les cas à haut débit.

Dans les scénarios où la charge de travail est augmentée, ILP et Branch surpasseraient Local en raison de leur capacité à gérer efficacement un débit plus élevé. À l'inverse, si la charge de travail était réduite, l'algorithme local pourrait fonctionner plus près de l'ILP et de la branche, mais serait toujours à la traîne en raison de différences fondamentales dans l'efficacité algorithmique.

Présentation de l'algorithme

Pour mieux comprendre la façon dont chaque algorithme aborde la résolution de problèmes, voici un aperçu général de leurs mécanismes et méthodologies.

Programmation linéaire entière (ILP)

Objectif :

ILP est une technique d'optimisation utilisée pour trouver le meilleur résultat (comme le profit maximum ou le coût le plus bas) dans un modèle mathématique dont les exigences sont représentées par des relations linéaires. Il est particulièrement efficace pour les problèmes qui peuvent être exprimés en termes de contraintes linéaires et de fonction objectif linéaire.

Flux de travail général :

1. Définir les variables :
   
   Identifiez les variables de décision qui représentent les choix à faire.

2. Fonction objectif :
   
   Formulez une équation linéaire qui doit être maximisée ou minimisée.

3. Contraintes :
   
   Établir des inégalités ou des égalités linéaires que la solution doit satisfaire.

4. Résoudre :
   
   Utilisez un solveur ILP pour trouver les valeurs optimales des variables de décision qui maximisent ou minimisent la fonction objectif tout en satisfaisant toutes les contraintes.

Pseudocode :

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
</my-package></my-project></my-package></my-project>

Algorithme A* (implémentation locale)

Objectif :

A* est un algorithme de recherche de chemin et de parcours de graphiques connu pour ses performances et sa précision. Il trouve efficacement le chemin le plus court entre les nœuds en combinant les fonctionnalités de recherche à coût uniforme et de recherche heuristique pure.

Flux de travail général :

1. Initialisation :
   
   Commencez par un nœud initial et ajoutez-le à la file d'attente prioritaire.

2. Boucle :

   • Supprimez le nœud avec l'estimation de coût la plus basse de la file d'attente prioritaire.
   • S'il s'agit du nœud d'objectif, terminez.
   • Sinon, développez le nœud en explorant ses voisins.
   • Pour chaque voisin, calculez le nouveau coût et mettez à jour la file d'attente prioritaire en conséquence.

3. Résiliation :
   
   L'algorithme se termine lorsque le nœud objectif est atteint ou que la file d'attente prioritaire est vide (indiquant qu'aucun chemin n'existe).

Pseudocode :

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
</my-package></my-project></my-package></my-project>

Algorithme de branchement et de liaison

Objectif :

Branch and Bound est un algorithme d'optimisation qui explore systématiquement l'espace des solutions. Il divise le problème en sous-problèmes plus petits (branchement) et utilise des limites pour éliminer les sous-problèmes qui ne peuvent pas produire de meilleures solutions que la meilleure actuelle (limite).

Flux de travail général :

1. Initialisation :
   
   Commencez par une solution initiale et définissez la solution la plus connue.

2. Branchement :
   
   À chaque nœud, divisez le problème en sous-problèmes plus petits.

3. Limite :
   
   Calculez une estimation optimiste (borne supérieure) de la meilleure solution possible dans chaque branche.

4. Taille :
   
   Jetez les branches dont la limite supérieure est pire que la solution la plus connue.

5. Recherche :
   
   Explorez de manière récursive les branches restantes en utilisant la recherche en profondeur ou en premier.

6. Résiliation :
   
   Lorsque toutes les branches ont été taillées ou explorées, la solution la plus connue est optimale.

Pseudocode :

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
</my-package></my-project></my-package></my-project>

Analyse comparative

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.

Implications pour les performances du serveur

• Évolutivité :

  • L'implémentation Branch and Bound démontre une excellente évolutivité, gérant efficacement un grand nombre de requêtes simultanées avec une latence réduite.
  • L'implémentation ILP Parallel montre également une excellente évolutivité, gérant efficacement un grand nombre de requêtes simultanées avec une latence réduite.
  • L'implémentation A* n'est pas adaptée aux environnements à charge élevée en raison de limitations de performances.

• Utilisation des ressources :

  • Les implémentations Branch and Bound utilisent les ressources de manière efficace, avec une faible consommation de mémoire et des temps d'exécution rapides.
  • ILP Parallel utilise efficacement les processeurs multicœurs, offrant un débit élevé avec une consommation de mémoire gérable.
  • Les Les implémentations A* consomment trop de mémoire, ce qui peut conduire à un épuisement des ressources.

Impact de la charge de travail sur les performances

Les différences de charge de travail influencent les performances des algorithmes :

• Branch and Bound Implementation gère efficacement la même charge de travail que l'implémentation ILP, offrant des temps d'exécution rapides et une faible utilisation de la mémoire, ce qui la rend adaptée à la mise à l'échelle.

• La mise en œuvre ILP gère efficacement une charge de travail plus importante grâce à des solveurs optimisés.

• L'implémentation A* peine en termes de performances en raison des temps d'exécution et de l'utilisation de la mémoire élevés.

Conclusion

Une comparaison supplémentaire a été ajoutée en utilisant une solution optimisée avec l'algorithme Branch and Bound, qui montre comment il s'est considérablement amélioré par rapport aux algorithmes ILP et A* en termes de performances et d'utilisation des ressources. La charge de travail utilisée sur l'algorithme Branch and Bound est la même que celle de l'algorithme ILP.

La fonction BenchmarkBranchGenerateReportLocalParallel basée sur les branches et les limites présente des améliorations de performances exceptionnelles, ce qui la rend parfaitement adaptée aux environnements de serveur exigeant une simultanéité élevée et une gestion efficace des ressources.

En nous concentrant sur l'exploitation des atouts de l'approche Branch and Bound et en l'optimisant pour un problème spécifique, nous pouvons garantir que le projet reste à la fois performant et évolutif, capable de gérer facilement des demandes croissantes.

Pensées finales

Équilibrer les performances, l'évolutivité et l'expérience des développeurs est crucial pour créer des applications robustes. L'approche Branch and Bound s'est avérée la plus efficace dans la configuration actuelle, offrant des gains de performances substantiels avec un effort de développement raisonnable.

En profilant, optimisant et tirant continuellement parti des atouts de chaque approche algorithmique, nous pouvons maintenir un système hautes performances, évolutif et convivial pour les développeurs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!