Technische Samenvatting: Benchmarking van Algoritmen voor Partities van Verzamelingen

Probleemstelling

Het artikel behandelt de computationele uitdaging van het enumereren van alle mogelijke partities van een verzameling van $n$ verschillende objecten. Een partitie van een verzameling wordt gedefinieerd als een collectie van niet-overlappende deelverzamelingen (blokken) waarvan de unie de oorspronkelijke verzameling vormt. Dit probleem is fundamenteel voor taken binnen de combinatorische optimalisatie waarbij men een optimale distributie van objecten in groepen moet identificeren op basis van specifieke criteria (bijv. het verpakken van artikelen in pakketten, het plannen van taken of het toewijzen van gerechten aan borden).

Hoewel volledige enumeratie haalbaar is voor kleine $n$, groeit het aantal partities snel (Bell-getallen, $B_n$). Bijvoorbeeld bij $n=17$ zijn er ongeveer $8 \times 10^{10}$ partities, wat een exhaustieve zoektocht zonder aanzienlijke computationele middelen onhaalbaar maakt voor grotere $n$. Het artikel beoogt een gat in de literatuur te dichten door een praktische vergelijking te bieden van bestaande algoritmen voor het genereren van deze partities, aangezien eerdere studies een directe prestatie-benchmarking van moderne voorstellen tegenover klassieke methoden misten.

Methodologie

De auteurs hanteerden een empirische benchmarking-benadering in plaats van een theoretische complexiteitsanalyse, waarbij zij wezen op het gebrek aan een duidelijke theoretische runtime-analyse voor deze specifieke algoritmen. De methodologie omvatte:

1. Algoritme-selectie: Vier niet-recursieve (iteratieve) algoritmen werden geselecteerd voor testen:

   • Hutchinson [7]: Een klassiek algoritme.
   • Semba [12]: Een modern snel algoritme.
   • Er [4]: Een modern algoritme dat gebruikmaakt van Gray-code concepten zonder expliciete constructie.
   • Djokic et al. [3]: Een modern snel algoritme.
   • Opmerking: Recursieve algoritmen werden uitgesloten van benchmarking vanwege de overhead van herhaalde functie-aanroepen, wat hen over het algemeen minder efficiënt maakt dan iteratieve benaderingen. Gray-code constructies werden erkend maar niet getest.

2. Experimentele Opstelling:

   • Hardware: Tests werden uitgevoerd op laptops, lokale pc's en gevirtualiseerde cloud-machines.
   • Softwareomgeving: Algoritmen werden geïmplementeerd in C om lichtgewicht binaries te garanderen. Tests draaiden op zowel Linux als Windows besturingssystemen.
   • Compilers: De GNU C Compiler (GCC), Intel C Compiler (ICC) en Microsoft Visual C (MSVC) werden gebruikt met diverse optimalisatieniveaus.

3. Analytisch Component: Het artikel evalueerde ook de wiskundige eigenschappen van Bell-getallen ($B_n$). Het evalueerde diverse asymptotische en benaderende formules om de meest praktische expressies te bepalen voor het schatten van $B_n$ over kleine en grote verzetgroottes.

Belangrijkste Bijdragen

1. Benaderingsformules voor Bell-getallen

De auteurs evalueerden bestaande asymptotische expressies voor het berekenen van het aantal partities van verzamelingen. Zij identificeerden een specifieke benadering afgeleid door Moser en Wyman [10] met behulp van de Lambert $W$-functie als de meest nauwkeurige voor praktisch gebruik:
$$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)$$
De auteurs merken op dat deze formule een relatieve fout heeft die kleiner is dan $3 \times 10^{-3}$ voor $2 \le n \le 50$ en de exacte gehele waarde oplevert voor $1 \le n \le 7$. Ze hebben ook een bovengrens door Berend en Tassa [1] beoordeeld, waarbij zij opmerkten dat deze nuttig is voor kleine $n$, ondanks dat deze voor grotere $n$ overschat.

2. Empirische Benchmarking Resultaten

De kernbijdrage is de vergelijkende prestatieanalyse van de vier algoritmen. De belangrijkste bevindingen zijn:

• Afhankelijkheid van Compiler en OS: De runtime-prestaties zijn zeer gevoelig voor de compiler en het besturingssysteem. Linux-gebaseerde code (GCC/ICC) presteerde over het algemeen beter dan Windows-gebaseerde code (MSVC) met een factor tot 2. De keuze van de compiler had een significante impact op de prestaties; bijvoorbeeld draaide Hutchinson's algoritme sneller op GCC dan op ICC, terwijl Djokic's algoritme aanzienlijk sneller draaide op ICC dan op GCC.
• Prestaties van Algoritmen:
  • Hutchinson [7]: Consistent het traagste algoritme, waarbij de prestaties aanzienlijk verslechteren naarmate $n$ toeneemt.
  • Semba [12] en Er [4]: Presteerden sneller dan Hutchinson, maar waren langzamer dan het algoritme van Djokic.
  • Djokic et al. [3]: Toonde de snelste executietijden over het geteste bereik ($n=8$ tot $n=15$). Bijvoorbeeld, bij $n=15$ vereiste het algoritme van Djokic 3.746 ms, vergeleken met 5.285 ms voor Semba en 30.512 ms voor Hutchinson (op een Linux/GCC setup).

Resultaten en Aanbevelingen

Op basis van de empirische gegevens concluderen de auteurs dat het algoritme van Djokic et al. [3] de aanbevolen keuze is voor praktisch gebruik. De auteurs benadrukken dat dit algoritme niet alleen het snelst is, maar ook relatief kort en eenvoudig te implementeren.

Specifieke implementatie-aanbevelingen zijn:

• Gebruik compiler-optimalisatieniveau 2 of hoger.
• Maak gebruik van de Intel Compiler (ICC) op Linux-systemen voor het Djokic-algoritme, aangezien dit in hun tests snellere code opleverde dan GCC.
• Zorg voor de implementatie van het Djokic-algoritme in de aanvullende code.

Betekenis en Omvang

Het artikel claimt bescheiden een praktische kloof in de literatuur te vullen door een directe, empirische vergelijking te bieden van algoritmen voor het genereren van partities van verzamelingen, wat voorheen ontbrak. Het stelt een baseline vast voor prestaties op moderne hardware en compilers.

De auteurs beperken de reikwijdte van hun studie expliciet:

• Zij behandelen geen hardware-gebaseerde enumeratie (verwijzend naar [2] voor dat onderwerp).
• Zij onderzoeken geen beperkte partities van verzamelingen (partities met een maximale blokgrootte), hoewel zij opmerken dat dit een gerelateerd probleem is dat apart onderzoek vereist.
• Zij benchmarken geen Gray-code gebaseerde algoritmen, wat zij voorstellen als een potentieel gebied voor toekomstig werk.
• Zij bieden geen diepgaande theoretische analyse van de interactie tussen compiler-optimalisatie en hardware, aangezien dit buiten de scope van het werk valt.

Het artikel dient als een praktische gids voor onderzoekers en ingenieurs die partities van verzamelingen moeten enumereren, waarbij zowel wiskundige instrumenten voor schatting als een geverifieerde aanbeveling voor het meest efficiënte beschikbare generatie-algoritme worden geboden.