On Sunday, 29 July 2012 at 14:41:48 UTC, bearophile wrote:
As you guess I have had to use many arrays of bits in my
programs :-)
I'll do what I can :)
4124 - Set/reset all bits ie:
BitArray ba = BitArray(100);
ba[] = true;
Others haven't been done yet.
Among those 4124 suggestions the most important, and very
simple to implement, are:
- set n-th bit (this can be a little more efficient than
bs[n]=1;)
- reset n-th bit (this can be a little more efficient than
bs[n]=1;)
If it has to determine between compact and non-compact, then I
really don't see how any speed improvement can be made, and if
it's optimized it may be inlined which would be about as fast as
you could get.
Another commonly needed operation is a very fast bit count.
There are very refined algorithms to do this.
Likely similar to the hamming weight table mentioned in TDPL.
Combined with the canUseBulk I think I could make it fairly fast.
7487 - Done. When prepending it extends the array to size_t
extra and slowly backtracks until it needs to do it again.
Leaving a bit of "capacity" at the beginning is a good idea.
With how it's made for speed and slices, it had to :P
7488 - Done, union used and is 'compact' version (by default
or resized and can fit)
Good, this makes BitArray usable in many other situations :-)
Yes, currently a debate of it's partial ref/value issue is
coming up. As it is it's usable, and if you want to be sure it's
unique you can always dup it, otherwise as a previous suggestion
I'll either make two array types for either full reference vs
value, or take his separate slices (reference) idea.
Related:
http://d.puremagic.com/issues/show_bug.cgi?id=6697
Not so sure. Could make a multi-dimentional one that returns
slices to various sections, but that's iffy. I'd need an
example of how you'd use it with BitArray before I could build
a solution.
I have needed many times a fast BitMatrix, but I see it as a
data structure distinct from BitArray, so don't worry about
making them inter-operate.
A Matrix is just a multidimensional array right? I'll have to
read up on it a bit; doing simple division (Likely whole rows of
32bit at a time) would do that job, but expanding width several
times (compared to height) would be quite a bit slower; Although
not too horrible.
For me a BitMatrix must be as fast as possible, even if this
causes some waste of memory (see my implementation in the
attach of issue 6697) and I use it for medium and large bit
matrices. Generally I don't to count the set bits in a bit
matrix. So the two data structures need different capabilities
and they are better implemented in different ways (this means a
FastBitMatrix is not an array of a BitArray!).
more likely bool array/matrix.. Although if you heavily use
specific lines it could convert to bool[], and then back again,
but if you go all over the place it would be worse than just
using bool[].
Taking a row of a FastBitMatrix and turning it into a a
BitArray sounds cute, but generally I don't need to do this
operation, so I don't care about this feature.
