Posso controllare C (++) se un array è tutto 0 (o falso) senza iterare/ripetere il ciclo su ogni singolo valore e senza allocare un nuovo array della stessa dimensione (per utilizzare memcmp)?Posso controllare C (++) se un array è tutto 0 (o falso)?
sto abusando un array di Caccio ad avere grandi bitsets arbitrari in fase di esecuzione e fare un po 'su di esso bitflipping
È possibile utilizzare la seguente condizione:
(myvector.end() == std::find(myvector.begin(), myvector.end(), true))
Ovviamente, internamente, questo loop over tutti i valori.
L'alternativa (che dovrebbe davvero evitare il looping) è di ignorare tutte le funzioni di accesso in scrittura e tenere traccia di se true è mai stato scritto sul vettore.
UPDATE
Lie commenti di Ryan seguenti descrivono un metodo più robusto di fare questo, basato sullo stesso principio.
si tenga presente che, mentre il flag può affermare in modo affidabile che l'array contiene tutto falso se il flag è falso; se il flag è true, non può dire in modo affidabile se l'array contiene un true. Se il flag è true, dovrai comunque verificare se esiste un valore vero. –
Un modo più sofisticato è quello di tenere traccia del numero di 'true's nell'array. Se stai modificando un valore da vero a falso, decrementi questo contatore e se cambi un valore da falso a vero, aumenti il contatore. Altrimenti, se stai cambiando da vero a vero o da falso a falso, non fai nulla. Puoi capire se la matrice è falsa se il contatore è zero. –
Una cosa da tenere a mente è che, se modifichi molto la matrice e raramente fai il controllo "è tutto 0" e se la matrice non è troppo grande, stai sprecando più tempo modificando il contatore di quanto non faresti essere se si dovesse controllare la matrice. – EboMike
Se non è ordinato, no. Come penseresti di realizzarlo? Dovresti controllare ogni elemento per vedere se è 0 o no! memcmp, ovviamente, controllerebbe anche ogni elemento. Sarebbe solo molto più costoso visto che legge anche un'altra matrice.
Naturalmente, è possibile uscire presto non appena si preme un elemento diverso da 0.
L'unica opzione sarebbe utilizzare SIMD (che tecnicamente controlla ancora ogni elemento, ma utilizzando meno istruzioni), ma generalmente non lo si fa in un array generico.
(Btw, la mia risposta presuppone che si dispone di un/array semplice statica C C++. Se è possibile specificare che tipo di serie che hai, potremmo essere più specifico.)
+1. Penso che la tua unica opzione, purché tu abbia una serie contigua di tipi integrali, sarebbe quella di utilizzare le istruzioni SIMD come menzionato per verificare più elementi contemporaneamente. –
No, è possibile confrontare le matrici con memcmp, ma non è possibile confrontare un valore con un blocco di memoria.
Ciò che si può fare è utilizzare algoritmi in C++ ma che coinvolgono ancora un ciclo internamente.
Non è necessario ripetere l'intera operazione, basta interrompere il ciclo sul primo valore diverso da zero.
non riesco a pensare a un modo per controllare una serie di valori diversi da loro ogni controllo, a sua volta - si potrebbe giocare con il controllo della memoria di base come qualcosa di più grande di bool (__int64 dicono), ma l'allineamento è poi un problema .
MODIFICA: È possibile mantenere un conteggio separato dei bit di impostazione e controllare che sia diverso da zero. Dovresti stare attento alla manutenzione di questo, in modo che l'impostazione di un bit impostato non sia ++ e così via.
Se si sa che questo sarà un requisito, è possibile creare una struttura di dati costituita da un array (eventualmente dinamico) e un conteggio o celle attualmente non zero. Ovviamente l'impostazione delle celle deve essere sradicata, ma ciò è naturale in C++ con sovraccarico, e puoi usare un tipo opaco in c.
Utilizzare invece boost::dynamic_bitset. Ha un membro none e diverse altre operazioni simili a std::bitset, ma la sua lunghezza può essere impostata in fase di esecuzione.
Non posso usare librerie esterne (e non voglio neanche) – knittl
@knittl: quindi puoi copiare e incollare il codice da 'boost :: dynamic_bitset'. –
Questa è una libreria di sola intestazione. Puoi semplicemente copiare la directory 'dynamic_bitset' nel tuo progetto e includere l'intestazione principale nel tuo file sorgente. –
Assumendo di disporre di un array di elementi N, è possibile eseguire un controllo di bit su un set di vettori di base.
Ad esempio, si dispone di un array di 15 elementi che si desidera testare.
È possibile testarlo su un array zero a 8 elementi, un array zero a 4 elementi, un array zero a 2 elementi e un array zero a 1 elemento.
Devi solo assegnare questi elementi una volta che conosci la dimensione massima degli array che vuoi testare. Inoltre, il test può essere eseguito in parallelo (e con l'assemblaggio intrinseco se necessario).
Un ulteriore miglioramento in termini di allocazione della memoria può essere eseguito utilizzando solo una matrice a 8 elementi poiché un array zero a 4 elementi è semplicemente la prima metà della matrice zero a 8 elementi.
Knittl,
non mi si supponga di avere accesso a alcuni componenti hardware DMA fantasia sul computer di destinazione? A volte l'hardware DMA supporta esattamente l'operazione richiesta, ad esempio "È questa regione di memoria completamente zero?" Questo tipo di confronto con accelerazione hardware è una soluzione comune quando si gestiscono buffer di grandi dimensioni. Ad esempio, alcuni controller RAID utilizzano questo meccanismo per il controllo di parità.
Se si utilizza 'std :: bitset', è possibile utilizzare il metodo' none() '. http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00263.html#ac224d7f896a9922057d9e14f307b30fd – Arun
C'è un motivo per cui questo è un problema perché è più o meno ciò che il codice macchina dovrà fare comunque – doron
@ arunsaha: devo impostare la dimensione per un bitset in fase di compilazione, ma ho bisogno di allocare dinamicamente memoria in fase di esecuzione – knittl