-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Please post to a public mailing list instead of private developers'
addresses (I no longer have time to actively contribute to classpath).
According to R.T.J.M. van der Heijden on 3/27/2006 7:42 AM:
> Dear Tom and Eric,
>
> I found your e-mail addresses in the source code of a Java class
> 'BitSet'. For a software project, I want an efficient implementation
> that counts the number of bits that overlap (intersect) between sets. Of
> course, I can create a new set as being the intersection between the two
> sets and then determine the cardinality of that. After the count is
> available, the newly created intersecting set becomes garbage. However,
> it could be much more efficient to calculate and return the overlap
> directly by accessing the bits variable in both sets (I give a possible
> implementation below). Unfortunately, this is not possible because the
> 'bits' variable is private in BitSet.
>
> Considering the above, I would suggest to set the accessibility of the
> 'bits' variable to 'protected', or to add some kind of overlap-counter.
> Having 'bits' set to 'protected' allows more extensions, of course.
Sorry, but Classpath strives for compatibility with the Sun
specifications, which will not permit making fields publicly accessible
that are not documented as such.
> However,
> I think you might have other suggestions on how to solve this problem.
>
> I would be glad to hear from you.
>
> Best regards,
>
> Rene van der Heijden
>
>
>
> ///////////////////////////////////////////////////////////////////////////////////////////
>
> // The following is a suggested part of an extension of BitSet, or part
> of BitSet itself //
> ///////////////////////////////////////////////////////////////////////////////////////////
>
>
> int countOverlap(BitSet OtherSet)
> // counts the number of bits in the intersection of This and the
> OtherSet without intervenence of a new set
> {
> // determine the length to test
> int n = Math.min(bits.length,OtherSet.bits.length);
> // count the overlap; taken from the implementation of cardinality
> int overlap = 0;
> for (int i = n - 1; i >= 0; i--)
> {
> long a = bits[i] & OtherSet.bits[i];
> // Take care of common cases.
> if (a == 0)
> continue;
> if (a == -1)
> {
> overlap += 64;
> continue;
> }
> // Successively collapse alternating bit groups into a sum.
> a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L);
> a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L);
> int b = (int) ((a >>> 32) + a);
> b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f);
> b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff);
> overlap += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff);
> }
> return overlap;
> }
>
>
>
A good garbage collector recognizes temporary objects that are created for
a single use, and then discarded. I doubt adding a method will buy you
much improvement.
- --
Life is short - so eat dessert first!
Eric Blake ebb9@xxxxxxx
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFEJ/uC84KuGfSFAYARApNOAKDMbxNTxx+KSqoG3iuJLbp83ERvnwCgiHmF
UH6/WwVtUYWRFGEux+SYDJ0=
=y6mw
-----END PGP SIGNATURE-----
