lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Yonik Seeley" <ysee...@gmail.com>
Subject Re: OpenBitSet
Date Fri, 12 May 2006 22:03:49 GMT
ntz8 or ntz8a could possibly be faster than what I have now for low
density bit sets:
http://www.hackersdelight.org/HDcode/ntz.cc

I don't know how to expand those to 64 bit, but they could always be
used on the two 32 bit chunks I guess.  Anyway, for higher density bit
sets, my current implementation should be faster.

-Yonik

On 5/12/06, Yonik Seeley <yseeley@gmail.com> wrote:
> > Is there also a nextSetBit(bitNr) somewhere on http://www.hackersdelight.org ?
> > This method is essential for filtering a query search.
>
> They have some algorithms for ntz (number of trailing zeros) for a
> single int value.  That's the harder part.  Using ntz to implement
> nextSetBit in an int or array of ints is easier and thus not covered.
>
> For OpenBitSet.nextSetBit(bitNr) I ended up coming up with my own
> ntz() using a combination of table lookup and single level binary
> search followed by linear search, which turned out to be fastest for
> implementing nextSetBit()

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message