¿Hay alguna forma de iterar sobre un (posiblemente enorme) std::bitset que es lineal en el número de bits que se establece en true? Quiero evitar tener que verificar cada posición en el conjunto de bits. La iteración debe devolver sucesivamente los índices de cada bit que se establece en verdadero.¿Manera eficiente de iterar sobre bits verdaderos en std :: bitset?
Para que sea lineal, necesitaría una lista enlazada/conjunto/matriz de los índices establecidos como verdaderos. Mantener dicho índice secundario no es parte de las compensaciones de desempeño/almacenamiento requeridas por std :: bitset, y dado que pondría en desventaja a 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 de múltiples índices de boost.
Looping sobre todo el conjunto de bits y simplemente verificando el valor y almacenando el índice si es verdadero, IS lineal. Puede acelerar eso con una tabla de búsqueda. Ver este código:
El objetivo de la pregunta era que la exploración de todo el conjunto de bits no es necesariamente lineal con respecto al número de bits establecidos. Por ejemplo, si se sabe que el número de conjuntos de bits es ~ ln donde N era el tamaño del conjunto, entonces un escaneo aún tomará O (N) y no O (ln N). –
Eddie, no es lineal en el número de bits verdaderos. Considere editar su respuesta o eliminarla. – einpoklum
Puede comprobar hasta 32-bits a la vez con un acumulador de U64 y una mesa de 32 entrada como
u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};
Basta con leer en 32 bits en un U64 acumulador y desplazarlo hacia abajo dependiendo de la compensación y verificar sus bits contra la mesa. 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 de forma 'lineal'. Esto se convierte en tiempo de registro.
Un bitvector estándar no admite la iteración eficiente sobre bits verdaderos: el tiempo de ejecución siempre es O (n), donde n es el número total de bits, 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 yk es el número de bits verdaderos.
Como un poco de auto promoción de Shameless, tengo an implementation of a vEB-tree on my personal website. Si no es apropiado para mí anunciar esto aquí, házmelo saber y lo quitaré.
sólo hay dos opciones que lo hacen mucho mejor que O (N) en el total de bits:
A veces las personas usan run-length encoding para cosas como esas. Si codifica el conjunto de bits entrantes en una matriz de longitudes de ejecución, el número de ejecuciones con las que finaliza no excederá el número de transiciones entre los bits definidos y claros, 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 peor caso lineal.
Por otra parte, es fácil añadir una estructura de datos que le permiten buscar de manera eficiente para cosas tales como "el siguiente conjunto de bits a partir de n ª posición en la matriz": acaba de construir un scan de las tiradas.
También puede encontrar el código para bitsets dispersos en la web. – etarion
Entiendo. Desafortunadamente, mantener un almacenamiento de índices por separado no es una opción. Gracias por tus ideas. – Astyanax