Existe-t-il des algorithmes à temps constant pour l'intersection d'ensembles binaires et l'union? J'imagine l'utilisation de bitmaps avec des pointeurs vers des éléments de la mémoire et en utilisant OU pour union et ET pour intersection.opérations d'ensemble à temps constant
Quelqu'un at-il maintenant une solution?
Il est temps constant jusqu'à 32 éléments avec la classe BitArray. Vous pouvez en écrire un personnalisé pour obtenir jusqu'à 64 éléments, en utilisant un ulong [] sous-jacent. Le code non géré rend 128 éléments possibles avec les intrinsèques _mm_or_si128 et _mm_and_si128. Difficile à utiliser en raison de leurs exigences d'alignement de la mémoire, ne peut pas obtenir cela à partir du tas de déchets collectés.
Ce ne sont pas des quantités pratiques dans la plupart des cas où vous souhaitez optimiser ce type de code. Il s'agit fondamentalement d'un algorithme O (n) avec un très petit Oh. Pourrait aussi bien utiliser BitArray.
Ce sera au moins O (n), car le nombre d'opérations OR/AND que vous devez effectuer augmente proportionnellement à la taille définie. –
Ensembles de quoi? Des entiers arbitraires de 32 bits? –
Quand j'ai dû faire cela, j'ai presque utilisé l'approche que vous décrivez. La principale différence étant que j'ai généralement travaillé avec de petits ensembles, donc j'ai simplement utilisé des entiers ou des tableaux d'entiers. Au lieu de les utiliser directement comme pointeurs, je les traite comme des indices. Les bitmaps peuvent permettre de petites économies en termes de vérification de la portée, mais IIRC le compilateur C# optimise la vérification de la gamme pour les tableaux dans certaines situations. Comme le souligne Gabe, il s'agit en fait de O (n/p), où p est le parallélisme implicite du vecteur binaire. – TechNeilogy