les opérations de réglage à temps constant

Question

Y at-il des algorithmes à temps constant pour intersection ensemble binaire et de l'union?

J'imagine à l'aide bitmaps avec des pointeurs vers des éléments dans la mémoire et l'utilisation ou pour l'union et AND pour intersection.

Est-ce que quelqu'un maintenant d'une solution?

Answer 1

Il est temps constant jusqu'à 32 éléments avec la classe BitArray. Vous pouvez écrire un personnalisé pour obtenir jusqu'à 64 éléments, en utilisant un ulong sous-jacente []. code non managé fait 128 éléments possibles avec le _mm_or_si128 et _mm_and_si128 intrinsics. Difficile à utiliser en raison de leurs exigences d'alignement de mémoire, ne peut pas obtenir ce à partir du tas d'ordures collectées.

Ce ne sont pas des quantités pratiques dans la plupart tous les cas où vous voudriez optimiser ce type de code. Il est fondamentalement un algorithme O (n) avec très Oh petit. Autant utiliser BitArray.