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

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.

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

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

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

Analyse comparative

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 grace à 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!