Almacenar un vector de bits en memoria no inicializada y espacio mínimo

8

Un truco bien conocido para almacenar vectores de bits utilizando memoria no inicializada puede asignar un vector de bits de tamaño en el que todos los bits se ponen a asignando bits de memoria e inicializando solo de ellos. Esta representación admite la configuración y el desarmado de cualquier bit en tiempo constante.n0(2n+1)lgnlgn

Esto se remonta a "Alfred Aho, John Hopcroft y el libro de 1974 de Jeffrey Ullman El diseño y análisis de algoritmos informáticos ... Capítulo 2, ejercicio 2.12", "Libro de 1986 de Jon Bentley Programming Pearls... Columna 1, ejercicio 8; ejercicio 9 en la segunda edición ", y " el documento de 1993 de Preston Briggs y Linda Torczon, 'Una representación eficiente para conjuntos dispersos' " .

El "Cambio de base sin perder espacio" de Dodis et al. ligeramente el requisito de espacio a bits, aunque este algoritmo requiere la precomputación de constantes con bits cada una.(2n+1)lgn+1Θ(lgn)Θ(lgn)

¿Cuánto espacio se puede ahorrar? ¿Hay una representación de vectores de bits en los que

  • Los bits se pueden activar o desactivar en tiempoO(1)
  • La inicialización de un nuevo vector de bits de s utiliza bits de memoria no inicializada y memoria inicializada0o(nlgn)O(lgn)
jbapple
fuente

Respuestas:

2

Sí, esto se puede hacer a través de bucketing . La representación en Briggs y Torczon se puede usar para almacenar no solo bits, sino también valores asociados con cualquier conjunto de bits, almacenándolos junto a los valores en la matriz densa. Para valores de bits, esto lleva a un costo total de almacenamiento de .k(2n+1)lgn+kn

Ahora elija . Cada valor de bits representará un conjunto de bits contiguos en la matriz de bits. Por lo tanto, solo necesitamos rastrear de ellos con las matrices densas y dispersas. Esto lleva a un costo total de bits de almacenamiento, con bits inicializados.k=lgnklgnn/lgnΘ(n)Θ(lgn)

Al igual que la solución básica, esto requiere operaciones en palabras de longitud para establecer un solo bit.O(1)Θ(lgn)

jbapple
fuente