On 7/25/06, Anton Luht <[EMAIL PROTECTED]> wrote:
For example, consider current implementation of java.util.BitSet.cardinality() . It just checks all bits one by one and increments count. [1] Gives an overview of algorithms for checking set bit count. The fastest algorithms are with table lookup, which requires additional memory, but there are algorithms that are several times faster than iteration (in C) and don't require tables. I believe such local optimizations with good comments and links to corresponding resources won't do any harm and are a good point to start with. Does it make sence? [1] http://www-db.stanford.edu/~manku/bitcount/bitcount.html Yes, BitSet code looks not optimized but at least it's readable :)
I always use wikipedia to read about classic algorithms implementation. E.g. here is bit counting algorithm too, but it with a reference to the book where it was published: http://en.wikipedia.org/wiki/Bit_array So when improving algorithm and making it not readable and 'tricky' I propose to add a reference to the original source. -- Mikhail Fursov
