C'è un modo di iterare su un (possibilmente enorme) std::bitset ovvero lineare nel numero di bit impostato su true? Voglio evitare di dover controllare ogni singola posizione nel bitset. L'iterazione dovrebbe successivamente restituire gli indici di ciascun bit impostato su true.Modo efficiente di iterare su bit true in std :: bitset?
Affinché ciò sia lineare, è necessario un elenco/matrice/set di indici impostati true. Mantenere un tale indice secondario non fa parte dei compromessi prestazionali/di archiviazione richiesti da std :: bitset, e dato che svantaggerebbe tutti senza il tuo specifico requisito, non c'è modo che un'implementazione fornisca questo. Potresti considerare di integrare il tuo set di bit con un contenitore di questo tipo, oppure utilizzare la libreria di contenitori multiindice di boost.
In loop su tutto il set di bit e semplicemente controllando il valore e memorizzando l'indice se vero, IS linear. Puoi accelerarlo con una tabella di ricerca. Vedere questo codice:
Il punto della domanda era che la scansione dell'intero set di bit non è necessariamente lineare rispetto al numero di bit impostati. Ad esempio, se il numero di set di bit fosse noto come ~ ln N dove N era la dimensione del set, allora una scansione prenderà comunque O (N) e non O (ln N). –
Eddie, non è lineare nel numero di bit reali. Ti preghiamo di considerare di modificare la tua risposta o di rimuoverla. – einpoklum
È possibile controllare fino a 32-bit alla volta con un accumulatore U64 e un tavolo da 32-entry come
u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};
Basta leggere a 32 bit in un U64 accumulatore e spostarlo verso il basso a seconda dell'offset e controllare i bit contro il tavolo. È possibile farlo in modo binario per ottenere il numero di confronti a un massimo di 5. Ciò sarà più lento per i dati che non sono "lineari" nella moda. Questo diventa quindi il tempo di registrazione.
Un bitvector standard non supporta un'iterazione efficiente su bit reali - il runtime è sempre O (n), dove n è il numero di bit totali, che non dipende da k. Tuttavia, una struttura speciale chiamata van Emde Boas Tree supporta l'iterazione sui bit nel tempo O (k lg lg n), dove n è il numero di bit e k è il numero di bit reali.
Come un po 'di spudorato auto-promozione, ho an implementation of a vEB-tree on my personal website. Se è inappropriato per me pubblicizzarlo qui, per favore fammelo sapere e lo prenderò in considerazione.
ci sono solo due opzioni che fare molto meglio di O (N) sui bit totale:
A volte le persone usano run-length encoding per cose del genere. Se si codifica il bitset in entrata in una serie di lunghezze di esecuzione, il numero di esecuzioni che si finisce non supera il numero di transizioni tra bit impostato e chiaro, che è al massimo 2*k. Inoltre, in molte applicazioni il numero di transizioni è molto inferiore a k, quindi si otterrà un'eccellente prestazione media in aggiunta a quella lineare peggiore.
Inoltre, è semplice aggiungere una struttura dati che consenta di cercare in modo efficiente cose come "il prossimo bit impostato a partire da n th posizione nell'array": basta creare un scan di lunghezze di esecuzione.
È inoltre possibile trovare il codice per bitset sparse sul Web. – etarion
Capisco. Sfortunatamente, mantenere una memoria separata degli indici non è un'opzione. Grazie per i tuoi approfondimenti. – Astyanax