Package io.deephaven.engine.table.impl.by

Class BitmapRandomBuilder

java.lang.Object
io.deephaven.engine.table.impl.by.BitmapRandomBuilder
All Implemented Interfaces:
RowSetBuilderRandom
public class BitmapRandomBuilder extends Object implements RowSetBuilderRandom
The output RowSet of an aggregation is fairly special. It is always from zero to the number of output rows, and while modifying states we randomly add rows to it, potentially touching the same state many times. The normal index random builder does not guarantee those values are de-duplicated and requires O(lg n) operations for each insertion and building the RowSet.

This version is O(1) for updating a modified slot, then linear in the number of output positions (not the number of result values) to build the RowSet. The memory usage is 1 bit per output position, vs. the standard builder is 128 bits per used value (though with the possibility of collapsing adjacent ranges when they are modified back-to-back). For random access patterns, this version will be more efficient; for friendly patterns the default random builder is likely more efficient.

We also know that we will only modify the rows that existed when we start, so that we can clamp the maximum key for the builder to the maximum output position without loss of fidelity.