Puedo comprobar en C (++) si una matriz es todo 0 (o falso)?

Question

puedo comprobar en C (++) si una matriz es todo 0 (o falso) sin iterar / bucle sobre cada valor individual y sin la asignación de una nueva matriz del mismo tamaño (para uso memcmp)?

estoy abusando de una serie de Bools tener grandes bitsets arbitrarios en tiempo de ejecución y hacer algo de bitflipping en él

Answer 1

Se puede utilizar la siguiente condición:

(myvector.end() == std::find(myvector.begin(), myvector.end(), true))

Obviamente, a nivel interno, este bucles más de todos los valores.

La alternativa (que en realidad debería evitar bucles) es reemplazar todas las funciones de escritura de acceso, y un seguimiento de si true jamás se ha escrito en su vector.

Actualizar

Los comentarios de Lie Ryan a continuación describen un método más robusto de hacer esto, basado en el mismo principio.

Answer 2

Si no se ordena, no. ¿Cómo te planear en el cumplimiento de ese? Usted tendría que inspeccionar cada elemento para ver si es 0 o no! memcmp, por supuesto, también sería comprobar cada elemento. Sólo sería mucho más caro, ya que lee otra matriz también.

Por supuesto, se puede temprana de salida tan pronto como se golpeó un elemento-0 no.

Su única opción sería utilizar SIMD (que técnicamente aún comprueba todos los elementos, pero utilizando un menor número de instrucciones), pero generalmente no lo hace en una matriz genérica.

(Por cierto, mi respuesta se supone que tiene un / C ++ simple matriz estática C. Si se puede especificar qué tipo de matriz que tiene, podríamos ser más específico.)

Answer 3

Si usted sabe que esto va a ser un requisito, se podría construir una estructura de datos que consiste en una matriz (posiblemente dinámico) y un recuento de células o actualmente no cero. Obviamente, la configuración de las células debe ser abstraído a través, pero eso es natural en C ++ con la sobrecarga, y se puede utilizar un tipo opaco en c.

Answer 4

Suponga que tiene un conjunto de elemento de N, se puede hacer una verificación de bit frente a un conjunto de vectores de base.

Por ejemplo, usted tiene una matriz de 15 elementos que desee prueba.

Puede probarlo en contra de un 8-elemento de la matriz cero, una matriz de 4 elementos cero, un 2-elemento de la matriz cero y un 1-elemento de la matriz cero.

Sólo tiene que asignar estos elementos una vez dado que se conoce el tamaño máximo de las matrices desea probar. Además, la prueba se puede realizar en paralelo (y con el montaje intrínseca si es necesario).

mejora adicional en términos de asignación de memoria se puede hacer con el uso de solamente una matriz de 8 elementos desde un 4-elemento de la matriz cero es simplemente la primera mitad de la 8-elemento de la matriz cero.

Answer 5

Considere el uso de boost::dynamic_bitset lugar. Tiene un miembro de none y varios otros std::bitset-operaciones similares, pero su longitud se puede ajustar en tiempo de ejecución.

Answer 6

No, usted puede comparar matrices con memcmp, pero no se puede comparar un valor con un bloque de memoria.

Lo que puede hacer es utilizar algoritmos en C ++, pero que todavía implica un bucle interno.

Answer 7

Usted no tiene que iterar sobre toda la cosa, sólo se detienen en lazo con el primer valor que no sea cero.

No se me ocurre ninguna manera de comprobar un conjunto de valores distintos de control de dichos aparatos cada uno de ellos - se puede jugar a juegos con la comprobación de la memoria subyacente como algo más grande que bool (digamos __int64), pero la alineación es entonces un problema.

EDIT: Se podría mantener una cuenta separada de bits puestos, y comprobar que no es cero. Habría que tener cuidado con el mantenimiento de este, por lo que el establecimiento de un conjunto de bits no ++ y así sucesivamente.

Answer 8

knittl,

supongo que no tiene acceso a algún hardware DMA de lujo en el equipo de destino? A veces soportes de hardware DMA exactamente la operación que necesita, es decir, "¿Es esta región de la memoria de todo ceros?" Este tipo de comparación con aceleración por hardware es una solución común cuando se trata de grandes bit-buffers. Por ejemplo, algunos controladores RAID utilizan este mecanismo para la comprobación de la paridad.