operaciones de conjuntos de tiempo constante

Question

¿Hay algoritmos en tiempo constante de intersección de conjuntos binaria y la unión?

I imaginar el uso de mapas de bits con punteros a los elementos de la memoria y la utilización o para la unión y Y para intersección.

¿alguien ahora de una solución?

Answer 1

Es constante de tiempo de hasta 32 elementos con la clase BitArray. Se puede escribir una medida para obtener un máximo de 64 elementos, utilizando un subyacente ulong []. código no administrado hace 128 elementos posibles con el _mm_or_si128 y _mm_and_si128 intrínsecos. Difícil de usar debido a sus requisitos de alineación de memoria, no puede conseguir que desde el montón de basura recogida.

No se trata de cantidades prácticas en la mayoría de cualquier caso en el que te gustaría para optimizar este tipo de código. Se trata fundamentalmente de un algoritmo O (n) con un muy pequeño Oh. Bien podría utilizar BitArray.