Mehdi
Good Job! I already implemented a bitarray as a bitset class, based on a old work done by someone here or there (don't remember)
This bitset has been used extensively by me, so I am used to it, and I've implemented several performance improvements, let me tell you some of them:
You should implement GetHashCode(), Equals() to allow this class to be used as index in Dictionary or Hashtable
Also ToString() should be overriden (useful for debugging)
Here is my code for this
public override int GetHashCode()
{
int h = 0;
if (_compressed != null)
{
foreach (uint u in _compressed) h ^= (int)u;
}
if (_uncompressed != null)
{
foreach (uint u in _uncompressed) h ^= (int)u;
}
return h;
}
Here is a not-so-lightweight comparison, with a little more work you may compare int-by int if both arrays are compressed or uncompressed, but for a hurry this should work as fine, (and actually does)!
public override bool Equals(object obj)
{
if (obj != null && obj is WAHBitArray)
{
WAHBitArray w = obj as WAHBitArray;
w.CheckBitArray();
CheckBitArray();
return w._uncompressed.Equals(_uncompressed);
}
else return false;
}
Its many times needed to see if the bitarray is empty (ie. after a And() operation), this yields a property needed, called 'Zero' which is good to implement as an extremely fast routine, like this one:
public bool Zero
{
get
{
CheckBitArray();
foreach (uint ui in _uncompressed)
{
if (ui != 0)
return false;
}
return true;
}
}
Even as I did not sniff inside the compression schema, the same may not need to decompress the array and work on the compressed one as well, even faster!
Another useful is the "cardinality" or OnesCount()
You can setup a simple array of 256 bytes, putting inside the number of ones of this byte (counted)
then simply add up all bytes (making at least 4 integer additions for each integer in the _uncompressed array).
The actual method makes Bit-Length additions (loops trough)
Here is the code:
public int BitCount()
{
CheckBitArray();
int c = 0;
int count = _uncompressed.Count << 2;
for (int i = 0; i < count; i++)
{
c += BYTE_COUNTS[(_uncompressed[i >> 2] >> ((i & 0x3)<<3)) & 0xFF];
}
return c;
}
For example the bitcount, is also slow, the string concatenation generates 'Length' strings in memory, with all the allocations overhead.
public string Bits
{
get
{
char[] c = new char[Length];
for (int i = 0; i < Length; i++)
c[i] = internalGet(i) ? '1' : '0';
return new string(c);
}
}
Also a simpler concatenation is not good but even faster than StringBuilder() for short stings
string s = "";
for (int i = 0; i < Length; i++)
s = (internalGet(i) ? "1" : "0") + s;
return s;
Parity is also needed, this is a fast way to calculate it!
public bool Parity
{
get
{
CheckBitArray();
int p = 0;
foreach (int i in _uncompressed)
p ^= i;
p ^= p >> 16;
p ^= p >> 8;
p ^= p >> 4;
p ^= p >> 2;
p ^= p >> 1;
return (p & 0x01) == 0;
}
}
and for the byte ones count, here is the block
#region private static byte[] BYTE_COUNTS
private static byte[] BYTE_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
#endregion
Hope this helps you all, and if you want to include this routines, mention me "Andres Hohendahl" with a co-Author/Contributor legend!
|