contain-rs / bit-set

A Set of Bits
Apache License 2.0
63 stars 25 forks source link

implemented faster counting for set operations #20

Closed winstonewert closed 2 months ago

winstonewert commented 4 years ago

For most of the operations, the implementation was straightforward. Simply have the iterators delegate count to BlockIter, then have BlockIter provide an optimized count() function that uses count_ones() to determine how many bits are set.

Intersection proved more problematic. The issue is that it is implemented using a Take wrapping the BlockIter. Take doesn't delegate count() to its internal iterator, so it will fall back to repeatedly invoking next() to count up the items. Take also doesn't provide a way to take back the wrapped iterator. What I did was re-implement the functionality of Take directly on the Intersection iterator.

I also considered creating a variant of TwoBitPosition which returned None when one of the subiterators ran out instead of padding with zeros. This would allow a similar, but not quite the same optimization. I elected to take the approach of reimplementing Take to minimize the impact of the change.

pczarn commented 2 months ago

Thanks! Rebased and merged.

winstonewert commented 2 months ago

Well... that's my longest code review process ever. :)

pczarn commented 2 months ago

@winstonewert One of mine was even longer. :)

By the way, we must have already met on StackExchange's Code Review forums.

pczarn commented 2 months ago

@winstonewert Not really longer... This one was 3 years and 5 months: https://github.com/tmuxinator/tmuxinator/pull/183