In diesem Blogbeitrag vergleichen wir die Leistung von drei verschiedenen Algorithmen, die in einem aktuellen persönlichen Projekt verwendet wurden: dem ILP (Integer Linear Programming)-Algorithmus, dem Lokaler Algorithmus unter Verwendung des A*-Algorithmus und eine optimierte Lösung unter Verwendung des Branch and Bound-Algorithmus. Alle Algorithmen wurden mit demselben Datensatz getestet, wobei die ILP- und Branch-and-Bound-Implementierungen die gleiche Arbeitslast teilten, während die A*-Implementierung aufgrund von Leistungseinschränkungen eingeschränkt war.
Haftungsausschluss: Obwohl ich nicht auf die spezifischen Codedetails des Projekts eingehen werde, werde ich einige Erkenntnisse daraus teilen. Die Codebasis ist nicht zur öffentlichen Offenlegung bestimmt und dient als Haftungsausschluss zur Wahrung ihrer Vertraulichkeit.
Hier sind die Benchmark-Ergebnisse für alle drei Algorithmen:
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
Alle Algorithmen wurden mit demselben Datensatz getestet, aber der Arbeitsaufwand (d. h. die Häufigkeit, mit der jedes Element verarbeitet wird) unterschied sich zwischen den Implementierungen.
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},
}
Um die Auswirkungen dieser Arbeitslasten auf die Benchmark-Ergebnisse zu verstehen, berechnen wir die Gesamtzahl der Iterationen (d. h. die Summe der Zeitwerte) für jede Implementierung.
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
Das bedeutet, dass die ILP- und Branch-and-Bound-Implementierungen ungefähr 21,74-mal mehr Iterationen verarbeiten im Vergleich zur A*-Implementierung.
Lassen Sie uns die Benchmark-Ergebnisse in Bezug auf die Arbeitsbelastungsunterschiede aufschlüsseln.
| 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 vs BenchmarkGenerateReportLocal-24:
BenchmarkGenerateReportILPParallel-24 vs BenchmarkBranchGenerateReportLocalParallel-24:
BenchmarkGenerateReportILPParallel-24 vs. BenchmarkGenerateReportLocalParallel-24:
Speicherzuweisungen:
Durchsatz:
Angesichts der Tatsache, dass die ILP- und Branch-Algorithmen 21,74-mal mehr Durchsatz pro Testiteration verarbeiten, wirkt sich dieser Unterschied in der Arbeitslast auf die Leistung und Effizienz jedes Algorithmus aus:
ILP- und Branch-Algorithmen: Da diese einen größeren Durchsatz bewältigen, sind sie für höhere Arbeitslasten optimiert. Obwohl sie mehr Vorgänge abwickeln, sorgen sie für kürzere Ausführungszeiten. Dies legt nahe, dass sie nicht nur recheneffizient sind, sondern auch für Hochdurchsatzszenarien gut geeignet sind.
Lokaler Algorithmus: Mit einem geringeren Durchsatz und einer höheren Ausführungszeit ist dieser Algorithmus bei der Bewältigung erhöhter Arbeitslasten weniger effizient. Bei einer Skalierung auf den gleichen Durchsatz wie ILP oder Branch würde sich die Ausführungszeit erheblich verlängern, was darauf hindeutet, dass es nicht ideal für Fälle mit hohem Durchsatz ist.
In Szenarien mit erhöhter Arbeitslast würden ILP und Branch Local übertreffen aufgrund ihrer Fähigkeit, einen höheren Durchsatz effizient zu verwalten. Wenn umgekehrt die Arbeitslast reduziert würde, könnte die Leistung des lokalen Algorithmus näher an der von ILP und Branch liegen, würde aber aufgrund grundlegender Unterschiede in der Algorithmuseffizienz wahrscheinlich immer noch hinterherhinken.
Um ein klareres Verständnis dafür zu vermitteln, wie die einzelnen Algorithmen an die Problemlösung herangehen, finden Sie hier einen allgemeinen Überblick über ihre Mechanismen und Methoden.
Zweck:
ILP ist eine Optimierungstechnik, mit der das beste Ergebnis (z. B. maximaler Gewinn oder niedrigste Kosten) in einem mathematischen Modell ermittelt wird, dessen Anforderungen durch lineare Beziehungen dargestellt werden. Es ist besonders effektiv für Probleme, die durch lineare Einschränkungen und eine lineare Zielfunktion ausgedrückt werden können.
Allgemeiner Arbeitsablauf:
Variablen definieren:
Identifizieren Sie die Entscheidungsvariablen, die die zu treffenden Entscheidungen darstellen.
Zielfunktion:
Formulieren Sie eine lineare Gleichung, die maximiert oder minimiert werden muss.
Einschränkungen:
Legen Sie lineare Ungleichungen oder Gleichheiten fest, die die Lösung erfüllen muss.
Lösen:
Verwenden Sie einen ILP-Löser, um die optimalen Werte der Entscheidungsvariablen zu finden, die die Zielfunktion maximieren oder minimieren und gleichzeitig alle Einschränkungen erfüllen.
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
Zweck:
A* ist ein Pfadfindungs- und Graph-Traversal-Algorithmus, der für seine Leistung und Genauigkeit bekannt ist. Es findet effizient den kürzesten Weg zwischen Knoten, indem es Funktionen der Suche nach einheitlichen Kosten und der reinen heuristischen Suche kombiniert.
Allgemeiner Arbeitsablauf:
Initialisierung:
Beginnen Sie mit einem Anfangsknoten und fügen Sie ihn der Prioritätswarteschlange hinzu.
Schleife:
Kündigung:
Der Algorithmus schließt ab, wenn der Zielknoten erreicht ist oder die Prioritätswarteschlange leer ist (was anzeigt, dass kein Pfad vorhanden ist).
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
Zweck:
Branch and Bound ist ein Optimierungsalgorithmus, der den Lösungsraum systematisch erkundet. Es unterteilt das Problem in kleinere Teilprobleme (Verzweigung) und verwendet Grenzen, um Teilprobleme zu eliminieren, die keine besseren Lösungen als die derzeit besten liefern können (Begrenzung).
Allgemeiner Arbeitsablauf:
Initialisierung:
Beginnen Sie mit einer ersten Lösung und legen Sie die bekannteste Lösung fest.
Verzweigung:
Teilen Sie das Problem an jedem Knoten in kleinere Teilprobleme auf.
Begrenzung:
Berechnen Sie eine optimistische Schätzung (Obergrenze) der bestmöglichen Lösung in jedem Zweig.
Beschneiden:
Verwerfen Sie Zweige, bei denen die Obergrenze schlechter ist als die bekannteste Lösung.
Suche:
Erkunden Sie verbleibende Zweige rekursiv mithilfe der Tiefensuche oder der Bestensuche.
Kündigung:
Wenn alle Zweige beschnitten oder erkundet wurden, ist die bekannteste Lösung optimal.
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
| 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. |
Skalierbarkeit:
Ressourcennutzung:
Die Workload-Unterschiede beeinflussen die Leistung der Algorithmen:
Branch-and-Bound-Implementierung bewältigt die gleiche Arbeitslast wie die ILP-Implementierung effizient und sorgt für schnelle Ausführungszeiten und geringe Speichernutzung, sodass sie für die Skalierung geeignet ist.
ILP-Implementierung bewältigt aufgrund optimierter Solver eine größere Arbeitslast effizient.
A*-Implementierung hat aufgrund hoher Ausführungszeiten und Speichernutzung Probleme mit der Leistung.
Ein zusätzlicher Vergleich wurde mit einer optimierten Lösung mit dem Branch and Bound-Algorithmus hinzugefügt, der zeigt, wie sich diese im Hinblick auf Leistung und Ressourcennutzung gegenüber dem ILP- und dem A*-Algorithmus deutlich verbessert hat. Die beim Branch-and-Bound-Algorithmus verwendete Arbeitslast ist die gleiche wie beim ILP-Algorithmus.
Die Branch and Bound-basierte BenchmarkBranchGenerateReportLocalParallel-Funktion weist außergewöhnliche Leistungsverbesserungen auf und eignet sich daher hervorragend für Serverumgebungen, die eine hohe Parallelität und effizientes Ressourcenmanagement erfordern.
Indem wir uns darauf konzentrieren, die Stärken des Branch-and-Bound-Ansatzes zu nutzen und ihn für das spezifische Problem zu optimieren, können wir sicherstellen, dass das Projekt sowohl leistungsfähig als auch skalierbar bleibt und in der Lage ist, steigende Anforderungen problemlos zu bewältigen.
Das Gleichgewicht zwischen Leistung, Skalierbarkeit und Entwicklererfahrung ist entscheidend für die Entwicklung robuster Anwendungen. Der Branch and Bound-Ansatz hat sich im aktuellen Setup als der effizienteste erwiesen und bietet erhebliche Leistungssteigerungen bei vertretbarem Entwicklungsaufwand.
Durch die kontinuierliche Profilierung, Optimierung und Nutzung der Stärken jedes algorithmischen Ansatzes können wir ein leistungsstarkes, skalierbares und entwicklerfreundliches System aufrechterhalten.
Das obige ist der detaillierte Inhalt vonVergleichendes Benchmarking: ILP-, A*- und Branch-and-Bound-Algorithmen in Hochdurchsatzszenarien. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Wie viel ist Dimensity 8200 gleich Snapdragon?
Was sind die DDoS-Angriffstools?
So löschen Sie Ihre eigenen Werke auf TikTok
Welche Software ist Adobe
0x00000006 Was tun, wenn der Drucker nicht angeschlossen werden kann?
Verwendung von parseInt in Java
So behalten Sie die Anzahl der Dezimalstellen in C++ bei
Einführung in Festplattenschnittstellentypen
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
