geeksforgeeks - flip c++
¿Manera eficiente de iterar sobre bits verdaderos en std:: bitset? (6)
¿Hay alguna manera de iterar sobre un (posiblemente enorme) std::bitset que sea lineal en el número de bits que se configuran en verdadero ? Quiero evitar tener que comprobar cada posición en el conjunto de bits. La iteración debe devolver sucesivamente los índices de cada bit que se establece en verdadero.
A veces las personas usan codificación de longitud de ejecución para cosas como esa. Si codifica el conjunto de bits entrante en una matriz de longitudes de ejecución, el número de ejecuciones que terminará no superará el número de transiciones entre los bits de ajuste y de borrado, que es como máximo 2*k . Además, en muchas aplicaciones, el número de transiciones es mucho menor que k , por lo que obtendría un excelente rendimiento de tiempo promedio además del lineal en el peor de los casos.
Además, es sencillo agregar una estructura de datos que le permita buscar de manera eficiente cosas como "el próximo bit de conjunto que comienza con la posición n en la matriz": simplemente realice un scan de las longitudes de ejecución.
Para que eso sea lineal, necesitaría una lista enlazada / matriz / conjunto de los índices establecidos como verdaderos. Mantener dicho índice secundario no es parte de los compromisos de rendimiento / almacenamiento requeridos por std :: bitset, y dado que sería una desventaja para todos sin su requisito específico, no hay forma de que una implementación lo proporcione. Podría considerar complementar su conjunto de bits con un contenedor de este tipo, o usar la biblioteca de contenedores multi-index de boost.
Puede verificar hasta 32 bits a la vez con un acumulador u64 y una tabla de 32 entradas como
u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};
Solo lea en 32 bits en un acumulador u64 y bájelo hacia abajo dependiendo del desplazamiento y verifique sus bits contra la tabla. Puede hacer esto de forma binaria para hacer el número de comparaciones en un máximo de 5. Esto será más lento para los datos que no son "lineales" en la moda. Esto entonces se convierte en tiempo de registro.
Recorriendo todo el conjunto de bits y simplemente comprobando el valor y almacenando el índice si es verdadero, es lineal. Puede acelerar eso sin embargo con una tabla de búsqueda. Ver este codigo
Solo hay dos opciones que funcionan mucho mejor que O (N) en los bits totales:
- Uso de instrucciones especiales de escaneo de bits disponibles en ciertas arquitecturas como BSF en x86 .
- Hay algoritmos O (log2 (N)) para encontrar el bit más bajo establecido en una palabra. Esto, por supuesto, no se escala bien cuando el conjunto de bits es denso, en lugar de escaso. Resucitando algunos de mis recuerdos de niebla, encontré la fuente en la biblioteca de FXT. Los detalles se pueden encontrar en el libro de FXT (pdf) , en la sección 1.3.2.
Un bitvector estándar no admite una iteración eficiente sobre bits verdaderos: el tiempo de ejecución es siempre O (n), donde n es el número de bits totales, que no depende de k. Sin embargo, una estructura especial llamada van Emde Boas Tree admite la iteración sobre los bits en el tiempo O (k lg lg n), donde n es el número de bits y k es el número de bits verdaderos.
Como parte de Shameless Self-Promotion, tengo una implementación de un vEB-tree en mi sitio web personal . Si es inapropiado para mí anunciar esto aquí, hágamelo saber y lo eliminaré.