Domanda Bit di conteggio impostati in una classe .Net BitArray


Sto implementando una libreria in cui sto usando estensivamente la classe BitNet .Net e ho bisogno di un equivalente al metodo Java BitSet.Cardinality (), cioè un metodo che restituisce il numero di bit impostati. Stavo pensando di implementarlo come metodo di estensione per la classe BitArray. L'implementazione banale è quella di iterare e contare i bit impostati (come di seguito), ma volevo un'implementazione più veloce poiché avrei eseguito migliaia di operazioni e contato la risposta. C'è un modo più veloce rispetto all'esempio qui sotto?

count = 0;

for (int i = 0; i < mybitarray.Length; i++)
{

  if (mybitarray [i])
    count++;
}

17
2018-02-21 06:59


origine


risposte:


Questa è la mia soluzione basata sul "miglior metodo di conteggio dei bit" di 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;

}

Secondo i miei test, questo è circa 60 volte più veloce del semplice ciclo foreach e ancora 30 volte più veloce dell'approccio di Kernighan con circa il 50% di bit impostato su true in un BitArray con 1000 bit. Ho anche una versione VB di questo se necessario.


27
2018-01-16 08:46



puoi farlo abbastanza facilmente con Linq

BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
           where m
           select m).Count();

2
2018-02-21 07:08



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;

Preso da "I pezzi di conteggio sono impostati, secondo Brian Kernighan"e adattato per byte. Lo sto usando per bit array di 1 000 000+ bit ed è superbo.
Se i tuoi bit non sono n * 8, puoi contare manualmente il byte mod.


2
2017-12-15 14:14



Potresti usare Linq, ma sarebbe inutile e più lento:

var sum = mybitarray.OfType<bool>().Count(p => p);

1
2018-02-21 07:08



Non c'è modo più veloce con l'utilizzo BitArray - A questo punto dovrai contare su di loro - puoi usare LINQ per farlo o fare il tuo loop, ma non esiste un metodo offerto da BitArray e la struttura dati sottostante è un int[] array (come visto con Reflector) - quindi questo sarà sempre O (n), n è il numero di bit nell'array.

L'unico modo per pensare di renderlo più veloce è usare la riflessione per afferrare il sottostante m_array campo, quindi è possibile aggirare il confine controlla che Get() utilizza su ogni chiamata (vedi sotto) - ma questo è un po 'sporco, e potrebbe valere la pena solo su array molto grandi poiché la riflessione è 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);
}

Se questa ottimizzazione è davvero importante per te, dovresti creare la tua classe per la manipolazione dei bit, che potrebbe essere utilizzata internamente BitArray, ma tiene traccia del numero di bit impostati e offre i metodi appropriati (in gran parte delegati a BitArray  ma aggiungi metodi per ottenere il numero di bit attualmente impostato) - ovviamente questo sarebbe O (1).


1
2018-02-21 07:14



Se si desidera massimizzare la velocità, è possibile calcolare una tabella di ricerca in cui viene fornito un valore di byte con la cardinalità, ma BitArray non è la struttura ideale per questo, poiché è necessario utilizzare il reflection per trascinare di memoria sottostante e operare sui tipi integrali - vedi questa domanda per una migliore spiegazione di questa tecnica.

Un'altra tecnica, forse più utile, è quella di usare qualcosa di simile il trucco di Kernighan, che è O (m) per un valore n bit della cardinalità 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;
}

Anche questo è un po 'più ingombrante di quanto sarebbe in C, perché non ci sono operazioni definite tra tipi interi e BitArray, (tmp &= tmp - 1, ad esempio, per cancellare il bit del set meno significativo, è stato tradotto tmp &= (tmp & ~0x1).

Non ho idea se questo finisca per essere più veloce di ingenuamente iterando per il caso del BCL BitArray, ma algoritmicamente parlando dovrebbe essere superiore.


EDIT: citato dove ho scoperto il trucco Kernighan, con una spiegazione più approfondita


1
2018-02-21 07:37



Se non ti dispiace copiare il codice di System.Collections.BitArray nel tuo progetto e modificarlo, puoi scrivere come utente: (Penso che sia il più veloce e ho provato a usare BitVector32 [] per implementare il mio BitArray, ma è ancora così 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);
        }
    }

1
2017-11-04 03:10



Ho scritto la mia versione di dopo averne trovato uno che utilizza una tabella di ricerca:

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;
}

1
2017-09-16 13:41



Il problema è naturalmente O (n), quindi la soluzione è probabilmente la più efficiente.

Dato che stai cercando di contare un sottoinsieme arbitrario di bit, non puoi contare i bit quando sono impostati (fornirebbe un aumento di velocità se non si impostano i bit troppo spesso).

È possibile verificare se il processore in uso ha un comando che restituirà il numero di bit impostati. Ad esempio un processore con SSE4 potrebbe utilizzare POPCNT secondo questo post. Questo probabilmente non funzionerebbe per te dal momento che .Net non consente l'assembly (perché è indipendente dalla piattaforma). Inoltre, i processori ARM probabilmente non hanno un equivalente.

Probabilmente la soluzione migliore sarebbe una tabella di ricerca (o switch se si potesse garantire che lo switch fosse compilato con un singolo salto su currentLocation + byteValue). Questo ti darebbe il conteggio per l'intero byte. Ovviamente BitArray non consente l'accesso al tipo di dati sottostante, quindi è necessario creare il proprio BitArray. Dovresti anche garantire che tutti i bit nel byte saranno sempre parte dell'intersezione che non sembra probabile.

Un'altra opzione sarebbe quella di utilizzare una matrice di booleani anziché un BitArray. Questo ha il vantaggio di non aver bisogno di estrarre il bit dagli altri nel byte. Lo svantaggio è che l'array occuperà 8 volte lo spazio in memoria, il che significa non solo lo spreco di spazio, ma anche più dati in push mentre si scorre l'array per eseguire il conteggio.

La differenza tra una ricerca di array standard e una ricerca di BitArray è la seguente:
Array:

  1. offset = index * indexSize
  2. Ottieni memoria in posizione + offset e salva in valore

BitArray:

  1. index = index / indexSize
  2. offset = index * indexSize
  3. Ottieni memoria in posizione + offset e salva in valore
  4. position = index% indexSize
  5. Spostare i bit di posizione del valore
  6. valore = valore e 1

Ad eccezione di # 2 per gli array e # 3 la maggior parte di questi comandi richiede 1 ciclo del processore da completare. Alcuni comandi possono essere combinati in 1 comando usando processori x86 / x64, anche se probabilmente non con ARM poiché utilizza una serie ridotta di istruzioni.
Quale tra i due (array o BitArray) migliori saranno specifici della piattaforma (velocità del processore, istruzioni del processore, dimensioni della cache del processore, velocità della cache del processore, quantità di memoria di sistema (RAM), velocità della memoria di sistema (CAS), velocità di connessione tra processore e RAM) e la diffusione degli indici che si desidera contare (le intersezioni sono spesso raggruppate in cluster o distribuite casualmente).

Riassumere: probabilmente potresti trovare un modo per renderlo più veloce, ma la tua soluzione è la più veloce che otterrai per il tuo set di dati usando un bit per modello booleano in .NET.

Modificare: assicurati di accedere agli indici che vuoi contare in ordine. Se si accede agli indici 200, 5, 150, 151, 311, 6 in tale ordine, si aumenterà la quantità di errori di cache, con conseguente maggiore tempo trascorso in attesa del recupero dei valori dalla RAM.


0
2018-04-11 22:22



Ho avuto lo stesso problema, ma avevo più di un solo metodo di cardinalità da convertire. Quindi, ho optato per il porting dell'intera classe BitSet. Fortunatamente era autonomo.

Qui è il Gist della porta C #.

Sarei grato se le persone segnalassero eventuali bug rilevati - Non sono uno sviluppatore Java e ho un'esperienza limitata con la logica dei bit, quindi potrei averne tradotto in modo errato.


0
2017-12-03 05:07