Cuenta de bits establecidos en una clase.Net BitArray
algorithm (10)
Estoy implementando una biblioteca en la que estoy utilizando ampliamente la clase .Net BitArray y necesito un equivalente al método Java BitSet.Cardinality (), es decir, un método que devuelve el número de bits establecido. Estaba pensando en implementarlo como un método de extensión para la clase BitArray. La implementación trivial es iterar y contar los bits establecidos (como a continuación), pero quería una implementación más rápida ya que estaría realizando miles de operaciones de conjuntos y contando la respuesta. ¿Hay una manera más rápida que el siguiente ejemplo?
count = 0;
for (int i = 0; i < mybitarray.Length; i++)
{
if (mybitarray [i])
count++;
}
El problema es naturalmente O (n), como resultado, su solución es probablemente la más eficiente.
Dado que está tratando de contar un subconjunto arbitrario de bits, no puede contar los bits cuando están establecidos (proporcionaría un aumento de velocidad si no está configurando los bits con demasiada frecuencia).
Puede verificar si el procesador que está utilizando tiene un comando que devolverá el número de bits establecidos. Por ejemplo, un procesador con SSE4 podría usar el POPCNT de acuerdo con esta publicación . Es probable que esto no funcione para usted ya que .Net no permite el ensamblaje (porque es independiente de la plataforma). Además, los procesadores ARM probablemente no tienen un equivalente.
Probablemente, la mejor solución sería una tabla de consulta (o cambio si pudiera garantizar que el cambio se compilará en un solo salto a currentLocation + byteValue). Esto le daría la cuenta para el byte entero. Por supuesto, BitArray no da acceso al tipo de datos subyacente, por lo que tendría que crear su propio BitArray. También tendría que garantizar que todos los bits en el byte siempre formarán parte de la intersección que no suena probable.
Otra opción sería usar una matriz de valores booleanos en lugar de un BitArray. Esto tiene la ventaja de que no es necesario extraer el bit de los otros en el byte. La desventaja es que la matriz ocupará 8 veces más espacio en la memoria, lo que significa que no solo se desperdicia espacio, sino también más datos a medida que recorre la matriz para realizar su conteo.
La diferencia entre una búsqueda de matriz estándar y una búsqueda de BitArray es la siguiente:
Formación:
- offset = index * indexSize
- Obtener memoria en la ubicación + desplazamiento y guardar en valor
BitArray:
- index = index / indexSize
- offset = index * indexSize
- Obtener memoria en la ubicación + desplazamiento y guardar en valor
- position = index% indexSize
- Desplazar los bits de posición de valor
- valor = valor y 1
Con la excepción de # 2 para Arrays y # 3, la mayoría de estos comandos toman 1 ciclo de procesador para completarse. Algunos de los comandos se pueden combinar en 1 comando usando procesadores x86 / x64, aunque probablemente no con ARM, ya que usa un conjunto reducido de instrucciones.
Cuál de los dos (array o BitArray) se desempeñará mejor será específico para su plataforma (velocidad del procesador, instrucciones del procesador, tamaños de caché del procesador, velocidad de la caché del procesador, cantidad de memoria del sistema (Ram), velocidad de la memoria del sistema (CAS), velocidad de conexión entre el procesador y la RAM), así como la dispersión de los índices que desea contar (son las intersecciones más a menudo agrupadas o se distribuyen al azar).
Para resumir: probablemente podría encontrar una manera de hacerlo más rápido, pero su solución es la más rápida que obtendrá para su conjunto de datos utilizando un poco por modelo booleano en .NET.
Editar: asegúrese de que está accediendo a los índices que desea contar en orden. Si accede a los índices 200, 5, 150, 151, 311, 6 en ese orden, aumentará la cantidad de fallos de caché, lo que resultará en un mayor tiempo de espera para recuperar los valores de la RAM.
Escribí mi versión de después de no encontrar una que use una tabla de consulta:
private int[] _bitCountLookup;
private void InitLookupTable()
{
_bitCountLookup = new int[256];
for (var byteValue = 0; byteValue < 256; byteValue++)
{
var count = 0;
for (var bitIndex = 0; bitIndex < 8; bitIndex++)
{
count += (byteValue >> bitIndex) & 1;
}
_bitCountLookup[byteValue] = count;
}
}
private int CountSetBits(BitArray bitArray)
{
var result = 0;
var numberOfFullBytes = bitArray.Length / 8;
var numberOfTailBits = bitArray.Length % 8;
var tailByte = numberOfTailBits > 0 ? 1 : 0;
var bitArrayInBytes = new byte[numberOfFullBytes + tailByte];
bitArray.CopyTo(bitArrayInBytes, 0);
for (var i = 0; i < numberOfFullBytes; i++)
{
result += _bitCountLookup[bitArrayInBytes[i]];
}
for (var i = (numberOfFullBytes * 8); i < bitArray.Length; i++)
{
if (bitArray[i])
{
result++;
}
}
return result;
}
Esta es mi solución basada en el "mejor método de conteo de bits" de http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
public static Int32 GetCardinality(BitArray bitArray)
{
Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];
bitArray.CopyTo(ints, 0);
Int32 count = 0;
// fix for not truncated bits in last integer that may have been set to true with SetAll()
ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));
for (Int32 i = 0; i < ints.Length; i++)
{
Int32 c = ints[i];
// magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
unchecked
{
c = c - ((c >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
count += c;
}
return count;
}
Según mis pruebas, esto es aproximadamente 60 veces más rápido que el simple bucle foreach y aún así es 30 veces más rápido que el enfoque de Kernighan con alrededor del 50% de bits establecido en verdadero en un BitArray con 1000 bits. También tengo una versión VB de esto si es necesario.
No hay una manera más rápida de usar BitArray . Lo importante es que tendrá que contarlos. Puede usar LINQ para hacer eso o hacer su propio bucle, pero BitArray no ofrece ningún método y la estructura de datos subyacente es una int[] array (como se ve con Reflector) - por lo que siempre será O (n), siendo n el número de bits en el array.
La única forma en que podría pensar en hacerlo más rápido es usar la reflexión para obtener una retención del campo m_array subyacente, luego puede sortear los controles de límites que Get() usa en cada llamada (ver a continuación), pero esto es un poco sucio. y puede que solo valga la pena en arreglos muy grandes ya que la reflexión es costosa.
public bool Get(int index)
{
if ((index < 0) || (index >= this.Length))
{
throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
return ((this.m_array[index / 0x20] & (((int) 1) << (index % 0x20))) != 0);
}
Si esta optimización es realmente importante para usted, debe crear su propia clase para la manipulación de bits, que internamente podría usar BitArray , pero mantiene un registro del número de bits establecido y ofrece los métodos apropiados (en su mayoría, delegar a BitArray pero agregue métodos para obtener el número). de bits actualmente establecidos) - entonces, por supuesto, esto sería O (1).
Podrías usar Linq, pero sería inútil y más lento:
var sum = mybitarray.OfType<bool>().Count(p => p);
Puedes lograr esto fácilmente con Linq
BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
where m
select m).Count();
Si no te importa copiar el código de System.Collections.BitArray a tu proyecto y editarlo, puedes escribir como tú: (Creo que es el más rápido. Y he intentado usar BitVector32 [] para implementar mi BitArray, pero sigue siendo tan lento.)
public void Set(int index, bool value)
{
if ((index < 0) || (index >= this.m_length))
{
throw new ArgumentOutOfRangeException("index", "Index Out Of Range");
}
SetWithOutAuth(index,value);
}
//When in batch setting values,we need one method that won''t auth the index range
private void SetWithOutAuth(int index, bool value)
{
int v = ((int)1) << (index % 0x20);
index = index / 0x20;
bool NotSet = (this.m_array[index] & v) == 0;
if (value && NotSet)
{
CountOfTrue++;//Count the True values
this.m_array[index] |= v;
}
else if (!value && !NotSet)
{
CountOfTrue--;//Count the True values
this.m_array[index] &= ~v;
}
else
return;
this._version++;
}
public int CountOfTrue { get; internal set; }
public void BatchSet(int start, int length, bool value)
{
if (start < 0 || start >= this.m_length || length <= 0)
return;
for (int i = start; i < length && i < this.m_length; i++)
{
SetWithOutAuth(i,value);
}
}
Si realmente desea maximizar la velocidad, puede pre-calcular una tabla de búsqueda donde dado un valor de byte tiene la cardinalidad, pero BitArray no es la estructura ideal para esto, ya que tendría que usar la reflexión para tirar del almacenamiento subyacente fuera de él y opere en los tipos integrales - vea esta pregunta para una mejor explicación de esa técnica.
Otra técnica, quizás más útil, es usar algo como el truco de Kernighan , que es O (m) para un valor de n de bit de cardinalidad m.
static readonly ZERO = new BitArray (0);
static readonly NOT_ONE = new BitArray (1).Not ();
public static int GetCardinality (this BitArray bits)
{
int c = 0;
var tmp = new BitArray (myBitArray);
for (c; tmp != ZERO; c++)
tmp = tmp.And (tmp.And (NOT_ONE));
return c;
}
Esto también es un poco más engorroso de lo que sería en C, porque no hay operaciones definidas entre tipos de enteros y BitArrays, ( tmp &= tmp - 1 , por ejemplo, para borrar el bit de conjunto menos significativo, se ha traducido a tmp &= (tmp & ~0x1) .
No tengo idea de si esto termina siendo más rápido que una iteración ingenua para el caso de BCL BitArray, pero hablando algorítmicamente debería ser superior.
EDITAR: citado donde descubrí el truco de Kernighan, con una explicación más profunda
Tuve el mismo problema, pero tenía más que solo el método de Cardinalidad para convertir. Entonces, opté por portar toda la clase BitSet. Afortunadamente era autocontenido.
Aquí está la esencia del puerto C # .
Apreciaría si la gente informara sobre cualquier error que se encuentre, no soy un desarrollador de Java y tengo experiencia limitada con la lógica de bits, por lo que podría haber traducido algunos de ellos incorrectamente.
BitArray myBitArray = new BitArray(...
int
bits = myBitArray.Count,
size = ((bits - 1) >> 3) + 1,
counter = 0,
x,
c;
byte[] buffer = new byte[size];
myBitArray.CopyTo(buffer, 0);
for (x = 0; x < size; x++)
for (c = 0; buffer[x] > 0; buffer[x] >>= 1)
counter += buffer[x] & 1;
Tomado de " Contando los bits establecidos, la forma de Brian Kernighan " y adaptado para bytes. Lo estoy usando para arreglos de bits de más de 1 000 000 bits y es excelente.
Si sus bits no son n * 8, entonces puede contar el byte mod manualmente.