🔢 mathematics

Benchmarking of algorithms for set partitions

Cet article passe en revue les algorithmes d'énumération des partitions d'ensembles, fournit des formules approximatives pour leurs décomptes et recommande l'algorithme de Djokic et al. sur la base de tests de performance.

Auteurs originaux : Arnav Khinvasara, Alexander Pikovski

Publié 2026-02-03

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Arnav Khinvasara, Alexander Pikovski

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez une boîte de briques Lego distinctes. Votre tâche est de trouver toutes les manières possibles de regrouper ces briques ensemble. Vous pourriez mettre chaque brique dans son propre petit tas, vous pourriez les empiler toutes dans une seule tour géante, ou vous pourriez les mélanger et les assortir en divers groupes. Dans le monde des mathématiques, cela s'appelle une partition d'ensemble.

Ce document est essentiellement un « rapport de course » pour des programmes informatiques qui tentent de lister chacun de ces regroupements possibles. Voici la décomposition de ce que les auteurs ont trouvé, en utilisant des analogies simples :

1. Le Problème : Un puzzle à l'explosion rapide

Les auteurs expliquent que, bien que lister des regroupements semble facile pour quelques éléments, le nombre de possibilités explose incroyablement vite.

L'Analogie : Pensez à un jeu de chaises musicales, mais au lieu de personnes, vous avez des nombres. Avec seulement 3 éléments, il y a 5 façons de les grouper. Mais quand on arrive à 17 éléments, il y a environ 82 milliards de façons différentes de les grouper.
La Réalité : Si vous avez plus de 17 ou 18 éléments, il devient impossible pour un ordinateur de lister chaque regroupement en un temps raisonnable. Cependant, pour de plus petits nombres, il est très utile qu'un ordinateur fasse cela, notamment pour des tâches d'optimisation comme le remplissage de boîtes ou la planification de quarts de travail.

2. Compter les Possibilités (Les « Nombres de Bell »)

Avant de pouvoir faire la course entre les algorithmes, les auteurs avaient besoin d'un moyen de savoir exactement combien de regroupements attendre. Ces nombres sont appelés Nombres de Bell.

Le Défi : Calculer le nombre exact est difficile, donc les mathématiciens utilisent des formules pour l'estimer.
La Découverte : Les auteurs ont testé plusieurs formules mathématiques complexes. Ils ont trouvé qu'une formule spécifique (impliquant une fonction mathématique spéciale appelée « fonction W de Lambert ») est incroyablement précise. C'est comme avoir des prévisions météorologiques qui sont justes à la minute près, même pour de petits nombres d'éléments. Ils ont également trouvé une formule plus simple qui fonctionne bien pour les petits groupes, mais qui devient un peu imprécise lorsque les nombres deviennent énormes.

3. La Course : Quatre Algorithmes en Compétition

La partie principale du document est un « benchmark », ce qui est simplement un mot élégant pour une course chronométrée. Les auteurs ont pris quatre programmes informatiques (algorithmes) conçus pour lister ces regroupements et les ont testés sur divers ordinateurs (ordinateurs portables, ordinateurs de bureau, serveurs cloud) en utilisant différents outils logiciels (compilateurs) et systèmes d'exploitation (Windows et Linux).

Les quatre coureurs étaient :

L'Algorithme de Hutchinson : « Le Vieux de la Vieille ». C'est la méthode classique datant de plusieurs décennies.
L'Algorithme de Semba : Un concurrent moderne et rapide.
L'Algorithme d'Er : Un autre concurrent moderne et rapide.
L'Algorithme de Djokic et al. : Le nouveau challenger.

Les Résultats :

Le Vieux de la Vieille (Hutchinson) : Ce programme était nettement plus lent que les autres. C'est comme essayer de courir un marathon avec des bottes lourdes. Les auteurs disent explicitement : Ne l'utilisez pas.
Les Coureurs Modernes (Semba, Er, Djokic) : Ils étaient beaucoup plus rapides.
Le Vainqueur : L'algorithme de Djokic a remporté la médaille d'or. C'était le plus rapide de tous.

4. L'« Moteur » Compte Aussi

Les auteurs ont également découvert que l'« moteur » qui fait tourner le code compte tout autant que la voiture elle-même.

Systèmes d'Exploitation : Le code tournant sur Linux était généralement plus rapide que sur Windows.
Compilateurs : L'outil utilisé pour traduire le code en langage machine faisait une énorme différence. Par exemple, sur un algorithme spécifique, le compilateur Intel était beaucoup plus rapide que le compilateur GNU standard, mais pour un autre algorithme, le compilateur GNU était plus rapide.
La Conclusion : Pour obtenir la meilleure vitesse, vous avez besoin du bon algorithme et des bons réglages logiciels.

5. La Recommandation Finale

Après avoir effectué des milliers de tests, les auteurs ont un verdict clair pour quiconque doit effectuer ce travail :

Utilisez l'algorithme de Djokic et al. Il est le plus rapide, il est relativement court (facile à écrire) et il est facile à implémenter.
Conseil : Assurez-vous que votre ordinateur est réglé sur le mode « hautes performances » (niveau d'optimisation du compilateur 2 ou supérieur) et, si vous êtes sous Linux, utilisez le compilateur Intel pour obtenir les meilleurs résultats.

Ce qu'ils n'ont pas couvert

Les auteurs ont pris soin de s'en tenir aux bases. Ils n'ont pas testé d'algorithmes qui cherchent des regroupements avec des limites spécifiques (comme « les groupes ne peuvent contenir que 3 éléments maximum »), et ils n'ont pas non plus examiné un autre type de système d'ordonnancement appelé « codes de Gray ». Ceux-ci sont laissés pour des recherches futures.

En résumé : Si vous avez besoin qu'un ordinateur liste toutes les façons de grouper un petit ensemble d'éléments, n'utilisez pas les anciennes méthodes. Utilisez l'algorithme de Djokic, lancez-le sur Linux avec le compilateur Intel, et vous accomplirez la tâche en un clin d'œil.

Résumé technique : Évaluation comparative des algorithmes de partitions d'ensembles

Énoncé du problème

L'article traite du défi computationnel que représente l'énumération de toutes les partitions possibles d'un ensemble de $n$ objets distincts. Une partition d'ensemble est définie comme une collection de sous-ensembles (blocs) non chevauchants dont l'union constitue l'ensemble original. Ce problème est fondamental dans les tâches d'optimisation combinatoire où l'on doit identifier la distribution optimale d'objets dans des groupes selon des critères spécifiques (par exemple, l'emballage d'articles dans des colis, l'ordonnancement ou l'assignation de plats à des assiettes).

Bien que l'énumération complète soit réalisable pour de petites valeurs de $n$ , le nombre de partitions croît rapidement (nombres de Bell, $B_n$ ). Par exemple, à $n=17$ , il existe environ $8 \times 10^{10}$ partitions, ce qui rend la recherche exhaustive infaisable pour des $n$ plus grands sans ressources de calcul significatives. L'article vise à combler une lacune dans la littérature en fournissant une comparaison pratique des algorithmes existants pour générer ces partitions, car les études précédentes manquaient d'une évaluation directe des performances des propositions modernes par rapport aux méthodes classiques.

Méthodologie

Les auteurs ont employé une approche d'évaluation empirique plutôt qu'une analyse de complexité théorique, citant l'absence d'analyse de temps d'exécution théorique claire pour ces algorithmes spécifiques. La méthodologie comprenait :

Sélection des algorithmes : Quatre algorithmes non récursifs (itératifs) ont été sélectionnés pour les tests :
- Hutchinson [7] : Un algorithme classique.
- Semba [12] : Un algorithme moderne rapide.
- Er [4] : Un algorithme moderne utilisant des concepts de code de Gray sans construction explicite.
- Djokic et al. [3] : Un algorithme moderne rapide.
- Note : Les algorithmes récursifs ont été exclus de l'évaluation en raison de la surcharge des appels de fonctions répétés, ce qui les rend généralement moins efficaces que les approches itératives. Les constructions basées sur le code de Gray ont été reconnues mais non testées.
Configuration expérimentale :
- Matériel : Les tests ont été effectués sur des ordinateurs portables, des PC locaux et des machines virtuelles dans le cloud.
- Environnement logiciel : Les algorithmes ont été implémentés en C pour garantir des binaires légers. Les tests ont été exécutés sur les systèmes d'exploitation Linux et Windows.
- Compilateurs : Le GNU C Compiler (GCC), l'Intel C Compiler (ICC) et le Microsoft Visual C (MSVC) ont été utilisés avec différents niveaux d'optimisation.
Composante analytique : L'article a également examiné les propriétés mathématiques des nombres de Bell ( $B_n$ ). Il a évalué diverses expressions asymptotiques et approximatives pour déterminer les expressions les plus pratiques pour estimer $B_n$ pour des tailles d'ensembles petites et grandes.

Contributions clés

1. Formules d'approximation pour les nombres de Bell

Les auteurs ont évalué les expressions asymptotiques existantes pour calculer le nombre de partitions d'ensembles. Ils ont identifié une approximation spécifique dérivée de Moser et Wyman [10] utilisant la fonction $W$ de Lambert comme étant la plus précise pour une utilisation pratique :
$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)$
Les auteurs notent que cette formule fournit une erreur relative inférieure à $3 \times 10^{-3}$ pour $2 \le n \le 50$ et donne la valeur entière exacte pour $1 \le n \le 7$ . Ils ont également examiné une borne supérieure par Berend et Tassa [1], notant son utilité pour les petits $n$ malgré une surestimation pour les $n$ plus grands.

2. Résultats de l'évaluation comparative empirique

La contribution centrale est l'analyse comparative des performances des quatre algorithmes. Les principales conclusions sont les suivantes :

Dépendance au compilateur et au système d'exploitation : La performance du temps d'exécution est très sensible au compilateur et au système d'exploitation. Le code basé sur Linux (GCC/ICC) a généralement surpassé le code basé sur Windows (MSVC) jusqu'à un facteur de 2. Le choix du compilateur a considérablement impacté la performance ; par exemple, l'algorithme de Hutchinson s'est exécuté plus rapidement sur GCC que sur ICC, tandis que l'algorithme de Djokic s'est exécuté nettement plus rapidement sur ICC que sur GCC.
Performance des algorithmes :
- Hutchinson [7] : Constamment l'algorithme le plus lent, avec une performance qui se dégrade considérablement à mesure que $n$ augmente.
- Semba [12] et Er [4] : Ont été plus rapides que Hutchinson mais plus lents que l'algorithme de Djokic.
- Djokic et al. [3] : A démontré les temps d'exécution les plus rapides sur la plage testée ( $n=8$ à $n=15$ ). Par exemple, à $n=15$ , l'algorithme de Djokic a nécessité 3 746 ms, contre 5 285 ms pour Semba et 30 512 ms pour Hutchinson (sur une configuration Linux/GCC).

Résultats et recommandations

Sur la base des données empiriques, les auteurs concluent que l'algorithme de Djokic et al. [3] est le choix recommandé pour une utilisation pratique. Les auteurs soulignent que cet algorithme est non seulement le plus rapide, mais aussi relativement court et facile à implémenter.

Des recommandations d'implémentation spécifiques incluent :

Utiliser un niveau d'optimisation de compilateur 2 ou supérieur.
Utiliser l'Intel Compiler (ICC) sur des systèmes Linux pour l'algorithme de Djokic, car il a produit un code plus rapide que GCC dans leurs tests.
Fournir l'implémentation de l'algorithme de Djokic dans le code supplémentaire.

Signification et portée

L'article revendique modestement avoir comblé une lacune pratique dans la littérature en fournissant une comparaison empirique directe des algorithmes de génération de partitions d'ensembles, ce qui faisait auparavant défaut. Il établit une référence de performance sur le matériel et les compilateurs modernes.

Les auteurs limitent explicitement la portée de leur étude :

Ils ne couvrent pas l'énumération basée sur le matériel (référence à [2] pour ce sujet).
Ils n'étudient pas les partitions d'ensembles restreintes (partitions avec une taille de bloc maximale), bien qu'ils notent que cela constitue un problème connexe nécessitant une investigation séparée.
Ils ne testent pas les algorithmes basés sur le code de Gray, suggérant cela comme un domaine potentiel pour des travaux futurs.
Ils ne fournissent pas d'analyse théorique approfondie de l'interaction entre l'optimisation du compilateur et le matériel, notant que cela est hors du champ de l'étude.

L'article sert de guide pratique pour les chercheurs et les ingénieurs ayant besoin d'énumérer des partitions d'ensembles, offrant à la fois des outils mathématiques pour l'estimation et une recommandation vérifiée pour l'algorithme de génération le plus efficace actuellement disponible.