🔢 mathematics

Benchmarking of algorithms for set partitions

Diese Arbeit überprüft Algorithmen zur Enumeration von Mengenpartitionen, liefert Näherungsformeln für deren Anzahl und empfiehlt den Algorithmus von Djokic et al. auf Basis von Benchmarking-Tests.

Ursprüngliche Autoren: Arnav Khinvasara, Alexander Pikovski

Veröffentlicht 2026-02-03

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Arnav Khinvasara, Alexander Pikovski

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben eine Kiste mit verschiedenen Lego-Steinen. Ihre Aufgabe ist es, jede einzelne Möglichkeit herauszufinden, diese Steine zu Gruppen zusammenzufassen. Sie könnten jeden Stein in seinen eigenen kleinen Haufen legen, Sie könnten sie alle zu einem riesigen Turm stapeln oder Sie könnten sie zu verschiedenen Clustern mischen und kombinieren. In der Welt der Mathematik nennt man das eine Teilmengenpartition (Set Partition).

Dieses Papier ist im Grunde ein „Rassebericht“ für Computerprogramme, die versuchen, jede einzelne dieser möglichen Gruppierungen aufzulisten. Hier ist die Aufschlüsselung dessen, was die Autoren herausgefunden haben, unter Verwendung einfacher Analogien:

1. Das Problem: Ein rasant explodierendes Rätsel

Die Autoren erklären, dass das Auflisten von Gruppierungen für wenige Gegenstände zwar einfach klingt, die Anzahl der Möglichkeiten jedoch unglaublich schnell explodiert.

Die Analogie: Denken Sie an ein Spiel wie Stuhlkreis, aber statt Menschen haben Sie Zahlen. Bei nur 3 Gegenständen gibt es 5 Möglichkeiten, sie zu gruppieren. Aber wenn man bei 17 Gegenständen ankommt, gibt es bereits etwa 82 Milliarden verschiedene Möglichkeiten, sie zu gruppieren.
Die Realität: Wenn Sie mehr als 17 oder 18 Gegenstände haben, wird es für einen Computer unmöglich, jede einzelne Gruppierung in einer angemessenen Zeit aufzulisten. Für kleinere Zahlen ist es jedoch sehr nützlich, einen Computer dies tun zu lassen, insbesondere bei Optimierungsaufgaben wie dem Packen von Kisten oder der Erstellung von Schichtplänen.

2. Das Zählen der Möglichkeiten (Die „Bell-Zahlen“)

Bevor sie die Algorithmen gegeneinander antreten lassen konnten, mussten die Autoren wissen, wie viele Gruppierungen genau zu erwarten sind. Diese Zahlen werden Bell-Zahlen genannt.

Die Herausforderung: Das exakte Berechnen der Zahl ist schwierig, daher verwenden Mathematiker Formeln, um sie abzuschätzen.
Die Entdeckung: Die Autoren testeten mehrere komplexe mathematische Formeln. Sie fanden eine spezifische Formel (die eine spezielle mathematische Funktion namens „Lambert W-Funktion“ beinhaltet), die unglaublich genau ist. Es ist wie eine Wettervorhersage, die selbst für kleine Mengen an Gegenständen auf die Minute genau richtig ist. Sie fanden auch eine einfachere Formel, die für kleinere Gruppen gut funktioniert, aber etwas ungenau wird, wenn die Zahlen riesig werden.

3. Das Rennen: Vier Algorithmen im Wettbewerb

Der Hauptteil des Papiers ist ein „Benchmark“, was einfach ein schickes Wort für ein zeitgesteuertes Rennen ist. Die Autoren nahmen vier verschiedene Computerprogramme (Algorithmen), die darauf ausgelegt sind, diese Gruppierungen aufzulisten, und ließen sie auf verschiedenen Computern (Laptops, Desktops, Cloud-Servern) unter Verwendung verschiedener Software-Tools (Compiler) und Betriebssysteme (Windows und Linux) laufen.

Die vier Rennfahrer waren:

Hutchinsons Algorithmus: Der „Alte“. Dies ist die klassische Methode aus vergangenen Jahrzehnten.
Sembas Algorithmus: Ein moderner, schneller Kontender.
Ers Algorithmus: Ein weiterer moderner, schneller Kontender.
Djokics Algorithmus (et al.): Der neueste Herausforderer.

Die Ergebnisse:

Der Alte (Hutchinson): Dieses Programm war signifikant langsamer als die anderen. Es ist, als würde man versuchen, einen Marathon in schweren Stiefeln zu laufen. Die Autoren sagen ausdrücklich: Benutzen Sie diesen nicht.
Die modernen Rennfahrer (Semba, Er, Djokic): Diese waren viel schneller.
Der Gewinner: Djokics Algorithmus holte die Goldmedaille. Er war der schnellste in allen Bereichen.

4. Der „Motor“ spielt ebenfalls eine Rolle

Die Autoren entdeckten auch, dass der „Motor“, der den Code ausführt, genauso wichtig ist wie das Auto selbst.

Betriebssysteme: Code, der auf Linux läuft, war im Allgemeinen schneller als auf Windows.
Compiler: Das Werkzeug, das den Code in Maschinensprache übersetzt, machte einen riesigen Unterschied. Zum Beispiel war auf einem spezifischen Algorithmus der Intel-Compiler viel schneller als der Standard-GNU-Compiler, aber bei einem anderen Algorithmus war der GNU-Compiler schneller.
Das Fazit: Um die beste Geschwindigkeit zu erreichen, benötigen Sie sowohl den richtigen Algorithmus als auch die richtigen Software-Einstellungen.

5. Die endgültige Empfehlung

Nachdem sie tausende von Tests durchgeführt hatten, haben die Autoren ein klares Urteil für jeden, der diese Arbeit leisten muss:

Verwenden Sie den Algorithmus von Djokic et al. Er ist der schnellste, er ist relativ kurz (leicht zu schreiben) und er ist einfach zu implementieren.
Tipp: Stellen Sie sicher, dass Ihr Computer auf den Modus „Hohe Leistung“ eingestellt ist (Compiler-Optimierungsstufe 2 oder höher), und wenn Sie auf Linux sind, verwenden Sie den Intel-Compiler, um die besten Ergebnisse zu erzielen.

Was sie nicht abgedeckt haben

Die Autoren waren sorgfältig darauf bedacht, sich an die Grundlagen zu halten. Sie haben keine Algorithmen getestet, die versuchen, Gruppierungen mit spezifischen Grenzen zu finden (wie z. B. „Gruppen dürfen maximal 3 Elemente enthalten“), noch haben sie sich mit einem anderen Typ von Ordnungssystem namens „Gray-Codes“ beschäftigt. Diese Themen wurden für die zukünftige Forschung zurückgelassen.

Zusammenfassend: Wenn Sie einen Computer benötigen, um jede Möglichkeit aufzulisten, eine kleine Menge von Gegenständen zu gruppieren, verwenden Sie nicht die alten Methoden. Verwenden Sie den Djokic-Algorithmus, lassen Sie ihn auf Linux mit dem Intel-Compiler laufen, und Sie werden die Aufgabe im Handumdrehen erledigt haben.

Technisches Resümee: Benchmarking von Algorithmen für Mengenpartitionen

Problemstellung

Die Arbeit befasst sich mit der rechnerischen Herausforderung, alle möglichen Mengenpartitionen einer Menge von $n$ distinkten Objekten zu enumerieren. Eine Mengenpartition ist definiert als eine Sammlung von disjunkten Teilmengen (Blöcken), deren Vereinigung die ursprüngliche Menge bildet. Dieses Problem ist grundlegend für kombinatorische Optimierungsaufgaben, bei denen man eine optimale Verteilung von Objekten auf Gruppen basierend auf spezifischen Kriterien identifizieren muss (z. B. das Verpacken von Artikeln in Pakete, Zeitplanung oder das Zuweisen von Speisen zu Tellern).

Während eine vollständige Enumeration für kleine $n$ machbar ist, wächst die Anzahl der Partitionen (Bell-Zahlen, $B_n$ ) rasant an. Beispielsweise gibt es bei $n=17$ etwa $8 \times 10^{10}$ Partitionen, was eine erschöpfende Suche ohne signifikante Rechenressourcen unmöglich macht. Die Arbeit zielt darauf ab, eine Lücke in der Literatur zu schließen, indem sie einen praktischen Vergleich bestehender Algorithmen zur Generierung dieser Partitionen bietet, da frühere Studien ein direktes Leistungs-Benchmarking moderner Vorschläge gegenüber klassischen Methoden vermissen ließen.

Methodik

Die Autoren verwendeten einen empirischen Benchmarking-Ansatz anstelle einer theoretischen Komplexitätsanalyse, da sie den Mangel an einer klaren theoretischen Laufzeitanalyse für diese spezifischen Algorithmen anführten. Die Methodik umfasste:

Algorithmenauswahl: Vier nicht-rekursive (iterative) Algorithmen wurden für Tests ausgewählt:
- Hutchinson [7]: Ein klassischer Algorithmus.
- Semba [12]: Ein moderner, schneller Algorithmus.
- Er [4]: Ein moderner Algorithmus, der Gray-Code-Konzepte ohne explizite Konstruktion nutzt.
- Djokic et al. [3]: Ein moderner, schneller Algorithmus.
- Hinweis: Rekursive Algorithmen wurden aufgrund des Overheads durch wiederholte Funktionsaufrufe, was sie im Allgemeinen weniger effizient als iterative Ansätze macht, vom Benchmarking ausgeschlossen. Gray-Code-Konstruktionen wurden anerkannt, jedoch nicht getestet.
Experimenteller Aufbau:
- Hardware: Die Tests wurden auf Laptops, lokalen PCs und virtualisierten Cloud-Maschinen durchgeführt.
- Softwareumgebung: Die Algorithmen wurden in C implementiert, um leichtgewichtige Binärdateien zu gewährleisten. Die Tests liefen sowohl unter Linux als auch unter Windows.
- Compiler: Der GNU C Compiler (GCC), der Intel C Compiler (ICC) und Microsoft Visual C (MSVC) wurden mit verschiedenen Optimierungsstufen eingesetzt.
Analytische Komponente: Die Arbeit untersuchte zudem die mathematischen Eigenschaften der Bell-Zahlen ( $B_n$ ). Sie evaluierte verschiedene asymptotische und approximative Formeln, um die praktischsten Ausdrücke zur Schätzung von $B_n$ für kleine und große Mengen zu bestimmen.

Zentrale Beiträge

1. Approximationsformeln für Bell-Zahlen

Die Autoren evaluierten bestehende asymptotische Ausdrücke zur Berechnung der Anzahl von Mengenpartitionen. Sie identifizierten eine spezifische Approximation, die von Moser und Wyman [10] unter Verwendung der Lambert-W-Funktion abgeleitet wurde, als die genaueste für die praktische Anwendung:
$B_n \approx B^*_n = \frac{e^{n W(n) + n/W(n) - n - 1}}{\sqrt{W(n) + 1}} \left( 1 - \frac{W(n)^2(2W(n)^2 + 7W(n) + 10)}{24n(W(n) + 1)^3} \right)$
Die Autoren stellen fest, dass diese Formel einen relativen Fehler von weniger als $3 \times 10^{-3}$ für $2 \le n \le 50$ aufweist und für $1 \le n \le 7$ den exakten ganzzahligen Wert liefert. Sie untersuchten auch eine obere Schranke durch Berend und Tassa [1] und merkten an, dass diese trotz der Überschätzung für größere $n$ für kleine $n$ nützlich ist.

2. Empirische Benchmarking-Ergebnisse

Der Kernbeitrag ist die vergleichende Leistungsanalyse der vier Algorithmen. Die wichtigsten Erkenntnisse sind:

Abhängigkeit von Compiler und Betriebssystem: Die Laufzeitleistung reagiert hochsensibel auf den Compiler und das Betriebssystem. Linux-basierter Code (GCC/ICC) übertraf Windows-basierten Code (MS-VC) im Allgemeinen um den Faktor 2. Die Wahl des Compilers beeinflusste die Leistung erheblich; zum Beispiel lief Hutchinsons Algorithmus auf GCC schneller als auf ICC, während Djokics Algorithmus auf ICC signifikant schneller lief als auf GCC.
Algorithmenleistung:
- Hutchinson [7]: War konsistent der langsamste Algorithmus, wobei die Leistung mit zunehmendem $n$ signifikant abnahm.
- Semba [12] und Er [4]: Waren schneller als Hutchinson, aber langsamer als der Algorithmus von Djokic.
- Djokic et al. [3]: Demonstrierte die schnellsten Ausführungszeiten über den getesteten Bereich ( $n=8$ bis $n=15$ ). Beispielsweise benötigte der Algorithmus von Djokic bei $n=15$ lediglich 3.746 ms, verglichen mit 5.285 ms für Semba und 30.512 ms für Hutchinson (in einem Linux/GCC-Setup).

Ergebnisse und Empfehlungen

Basierend auf den empirischen Daten kommen die Autoren zu dem Schluss, dass der Algorithmus von Djokic et al. [3] die empfohlene Wahl für die praktische Anwendung ist. Die Autoren heben hervor, dass dieser Algorithmus nicht nur der schnellste, sondern auch relativ kurz und einfach zu implementieren ist.

Spezifische Implementierungsempfehlungen beinhalten:

Verwendung der Compiler-Optimierungsstufe 2 oder höher.
Nutzung des Intel Compilers (ICC) auf Linux-Systemen für den Djokic-Algorithmus, da dies in ihren Tests einen schnelleren Code als GCC lieferte.
Bereitstellung der Implementierung des Djokic-Algorithmus im ergänzenden Code.

Bedeutung und Umfang

Die Arbeit beansprucht bescheiden, eine praktische Lücke in der Literatur zu schließen, indem sie einen direkten, empirischen Vergleich von Algorithmen zur Erzeugung von Mengenpartitionen bietet, der zuvor fehlte. Sie etabliert eine Baseline für die Leistung auf moderner Hardware und Compilern.

Die Autoren begrenzen den Umfang ihrer Studie explizit:

Sie behandeln keine hardwarebasierte Enumeration (sie verweisen hierzu auf [2]).
Sie untersuchen keine eingeschränkten Mengenpartitionen (Partitionen mit einer maximalen Blockgröße), merken jedoch an, dass dies ein verwandtes Problem ist, das eine separate Untersuchung erfordert.
Sie führen kein Benchmarking für Gray-Code-basierte Algorithmen durch und schlagen dies als potenzielles Feld für zukünftige Arbeiten vor.
Sie liefern keine tiefgehende theoretische Analyse des Zusammenspiels zwischen Compiler-Optimierung und Hardware, da dies außerhalb des Rahmens der Arbeit liegt.

Die Arbeit dient als praktischer Leitfaden für Forscher und Ingenieure, die Mengenpartitionen enumerieren müssen, und bietet sowohl mathematische Werkzeuge zur Schätzung als auch eine verifizierte Empfehlung für den effizientesten verfügbaren Generierungsalgorithmus.