praveenc7 commented on issue #17336: URL: https://github.com/apache/pinot/issues/17336#issuecomment-3644539312
> Wow.. We never expect `RoaringBitmap` to be slow.. Why is it having `O(n long n)` insertion complexity? From the reading I did on this looks like RoaringBitmap 1. Looks up the right container for the high bits 2. binary search on the sorted short[] to find the position → O(log k). if not present: shift tail of the array to insert → O(k) in the worst case 4. Per insertion: O(log k + k_shift and across millions of distinct inserts, the total cost is closer to O(n log n) (plus copies) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
