Vecteurs de bits

Un vecteur de bits est simplement une séquence d'éléments de un bit. Chaque élément est référencé par son indice, souvent entre $0$ pour le premier objet et $n-1$ pour le dernier (où $n$ est la taille du vecteur). Un tel vecteur peut être utilisé pour représenter un ensemble dont les éléments appartiennent à un domaine totalement ordonné et relativement dense. Les ensembles du langage de programmation Pascal étaient conçus d'après cette représentation.

L'idée est de faire correspondre chaque indice du vecteur à un élément du domaine, puis de représenter un ensemble sous la forme d'un vecteur dans lequel le bit d'indice $i$ est $1$ si et seulement si l'élément du domaine correspondant à $i$ se trouve dans l'ensemble.

Il faut d'abord une fonction $f$ pour implémenter la correspondance entre un élément du domaine et l'indice du vecteur. Souvent, cette fonction est l'identité $f(x) = x$. C'est le cas, par exemple si l'on souhaite un ensemble dont le domaine est :

• les jours de la semaine (1-7)
• les semaines de l'année (1-52)
• les jours de l'année (1-366)
• les mois de l'année (1-12)
• les heures du jour (0-23)
• les années d'un siècle (0-99)
• les départements de la France (ou presque)
• etc

Parfois, le domaine est dense, mais l'application n'a besoin que d'une petite partie de ce domaine. Si par exemple on souhaite représenter un ensemble de numéros de téléphones, mais que la taille de l'ensemble est seulement de quelques dizaines d'éléments, ce n'est pas une bonne idée de créer un vecteur de taille $10^{10}$ (nécessaire pour représenter tous le numéros de téléphone possibles en France). Ceci est aussi souvent vrai pour les numéros de sécurité sociale.

Une méthode classique pour obtenir un domaine totalement ordonné et dense est de faire correspondre, artificiellement, à chaque élément du domaine un petit entier positif. Si le domaine est par exemple les personnes membres d'une organisation ou les employés d'une société, il est relativement facile de donner à chaque personne un numéro de membre ou un numéro d'employé unique, de façon à ce que le domaine soit dense. Ce numéro peut être stocké sur disque avec les données permanentes de la personne concernée. Dans ce cas, on peut représenter un ensemble de membres du domaine par un vecteur de bits, dont les indices correspondent à ce numéro unique.

Si le domaine n'est pas totalement ordonné ou n'est pas dense, mais relativement petit et connu à la compilation, il est parfois possible d'utiliser le hachage parfait.

Les vecteurs de bits sont très performants du point de vue de la complexité des opérations proposées. Ajouter ou supprimer un élément à l'ensemble se fait en temps constant ($O(1))$. Il en est de même pour tester si un objet appartient à l'ensemble.

Calculer l'union ou l'intersection de deux ensembles, ou le complémentaire d'un ensemble se fait en temps linéaire ($O(n)$) où $n$ est la taille du domaine. Mais nous avons supposé que les instances utilisent une bonne fraction des éléments du domaine. On peut donc supposer que ces opérations sont proportionnelles aux tailles des opérandes. De plus, il est souvent possible d'implémenter ces opérations avec des instructions-machine traitant $32$ ou $64$ bits simultanément. Ces opérations n'ont donc pas seulement une complexité raisonnable, mais elle sont aussi très rapides en pratique.

Pour déterminer la taille de l'ensemble, il faut compter le nombre de bits à $1$. En principe, c'est une opération dont le coût est $O(n)$. Mais si c'est une opération essentielle, il est plus simple de maintenir un compteur associé à l'ensemble et de l'incrémenter ou le décrémenter chaque fois qu'un élément est ajouté ou supprimé. Pour l'union et l'intersection, il faut aussi compter le nombre d'éléments de l'ensemble résultant. Ce comptage ne change pas la complexité des deux opérations, mais les ralentissent considérablement (facteur 2 minimum).

On peut se poser la question de la densité du domaine requise pour qu'un vecteur de bits soit un bon choix. Si l'on compare avec une liste simplement chaînée par exemple (qui nécessite un surcoût d'au moins 2, probablement 3 ou 4, mots, soit entre 64 et 256 bits par élément), il est clair que le domaine n'a pas à être forcément très dense pour que le vecteur de bits soit un choix raisonnable. En moyenne, il suffit qu'un élément sur 50 (environ) du domaine soit élément de l'ensemble, pour que l'espace occupé par le vecteur de bits soit inférieur à celui d'une solution avec une liste simplement chaînée.

En Common Lisp, il y a deux façons de représenter des vecteurs de bits : sous forme d'entiers (voir section 6.2.8) ou sous forme de vecteurs dont les éléments sont des bits (voir section 9.1.3). Ces deux façons permettent de réaliser l'ensemble des opérations requises pour implémenter les ensembles.