¿Puedo verificar en C (++) si una matriz es 0 (o falsa) sin iterar/iterar sobre cada valor y sin asignar una nueva matriz del mismo tamaño (para usar memcmp)?¿Puedo verificar C (++) si una matriz es 0 (o falsa)?
que estoy abusando de una serie de Bools tener grandes bitsets arbitrarios en tiempo de ejecución y hacer algo de bitflipping en él
Puede utilizar la siguiente condición:
(myvector.end() == std::find(myvector.begin(), myvector.end(), true))
Obviamente, a nivel interno, este bucle recorre 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 a su vector.
ACTUALIZACIÓN
Lie comentarios de Ryan siguientes se describe un método más robusto de hacer esto, basado en el mismo principio.
tenga en cuenta que, mientras que la bandera puede decir confiablemente que la matriz contiene todo falso si la bandera es falsa; si la bandera es verdadera, no puede decir con certeza si la matriz contiene una verdadera. Si la bandera es verdadera, igual deberás verificar si hay alguna verdadera. –
Una forma más sofisticada es realizar un seguimiento de cuántos 'verdaderos' están en la matriz. Si está cambiando un valor de verdadero a falso, disminuye este contador, y si está cambiando un valor de falso a verdadero, entonces incrementa el contador. De lo contrario, si cambia de verdadero a verdadero o de falso a falso, no hace nada. Puedes decir si la matriz es falsa si el contador es cero. –
Una cosa a tener en cuenta, sin embargo es que, si se modifica la matriz mucho y rara vez se hace el "todo es 0" y comprobar si la matriz no es demasiado grande, está perdiendo más tiempo modificando el mostrador de lo que sería ser si fueras a verificar la matriz. – EboMike
Si no está ordenado, no. ¿Cómo planearías lograr eso? ¡Debería inspeccionar cada elemento para ver si es 0 o no! memcmp, por supuesto, también verificaría cada elemento. Sería mucho más costoso ya que también lee otra matriz.
Por supuesto, puede salir pronto tan pronto como llegue a un elemento que no sea 0.
Su única opción sería usar SIMD (que técnicamente sigue verificando cada elemento, pero usando menos instrucciones), pero generalmente no lo hace en una matriz genérica.
(Por cierto, mi respuesta se supone que tiene un/C++ simple matriz C estática. Si se puede especificar qué tipo de matriz que tiene, podríamos ser más específico.)
+1. Creo que su única opción siempre que tenga una matriz contigua de tipos integrales sería usar instrucciones SIMD como se menciona para verificar múltiples elementos a la vez. –
No, usted puede comparar matrices con memcmp, pero no puede comparar un valor con un bloque de memoria.
Lo que puedes hacer es usar algoritmos en C++ pero eso aún implica un ciclo interno.
No tiene que iterar sobre todo, simplemente deje de repetir el primer valor distinto de cero.
No puedo pensar en 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 (__int64 dicen), pero la alineación es entonces un problema .
EDIT: Puede mantener un recuento de bits por separado y verificar que no sea cero. Tendría que tener cuidado con el mantenimiento de esto, por lo que establecer un bit establecido no lo hizo ++, etc.
Si sabe que esto va a ser un requisito, podría compilar una estructura de datos que consista en una matriz (posiblemente dinámica) y una cuenta o celdas actualmente distintas de cero. Obviamente, la configuración de las celdas debe abstraerse, pero eso es natural en C++ con sobrecarga, y puede usar un tipo opaco en c.
Considere el uso de boost::dynamic_bitset en su lugar. Tiene un miembro none y varias otras operaciones similares a std::bitset, pero su longitud se puede establecer en tiempo de ejecución.
no puedo usar bibliotecas externas (y no quieren tampoco) – knittl
@knittl: entonces se puede copiar y pegar el código de 'impulso :: dynamic_bitset'. –
Esta es una biblioteca de solo encabezado. Puede copiar el directorio 'dynamic_bitset' en su proyecto e incluir el encabezado principal en su archivo fuente. –
Suponga que tiene un conjunto de elemento de N, se puede hacer una verificación de bit frente a un conjunto de vectores base.
Por ejemplo, usted tiene una matriz de 15 elementos que desea probar.
Puede probarlo en contra de un 8-elemento de la matriz cero, un 4-elemento de la matriz cero, un 2-elemento de la matriz cero y un 1-elemento de la matriz cero.
es suficiente con asignar estos elementos una vez, dado que se conoce el tamaño máximo de las matrices que desea probar. Además, la prueba se puede realizar en paralelo (y con el ensamblaje intrínseco 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.
knittl,
supongo que no tiene acceso a algún hardware DMA de lujo en el equipo de destino? A veces, el hardware DMA admite exactamente la operación que necesita, es decir, "¿Esta región de memoria es cero?" Este tipo de comparación acelerada por hardware es una solución común cuando se trata de grandes búfers de bits. Por ejemplo, algunos controladores RAID usan este mecanismo para verificar la paridad.
Si está utilizando 'std :: bitset', puede utilizar el' ninguno) método ('. http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00263.html#ac224d7f896a9922057d9e14f307b30fd – Arun
¿Hay alguna razón por la cual esto es un problema porque es más o menos lo que el código de la máquina necesitará hacer de todos modos – doron
@ arunsaha: tengo que establecer el tamaño para un bitset en tiempo de compilación, pero necesito para asignar dinámicamente memoria en tiempo de ejecución – knittl