davecromberge opened a new pull request, #760: URL: https://github.com/apache/datasketches-java/pull/760
## The problem `partition` takes its pivot from a fixed position, `arr[lo]`. On an ordered range that is the smallest element, so each partition strips one element instead of about half and `select` becomes quadratic: | array size | comparisons | needed | | --- | --- | --- | | 1,024 | 393,471 | 2,019 | | 4,096 | 6,292,479 | 8,157 | | 16,384 | 100,667,391 | 32,727 | Per-element cost doubles as `n` doubles. Reverse-ordered input is worse: 33,550,336 comparisons against 2. ## Where it bites No sketch reaches this today. Every internal caller passes an array read out of a hash table, and theta indexes slots by the low bits of the hash, which are independent of its magnitude — feeding a union gadget strictly ascending hashes still yields a table whose ascending-adjacent-pair fraction is 0.51. The exposure is that `QuickSelect` is public API, where ordered input is unremarkable. A compact ordered sketch's hashes are sorted, and they are the natural thing for a caller to have in hand. The current safety of this class rests on an incidental property of `HashOperations` probing that `QuickSelect` neither documents nor requires. ## The change Pivot on the median of `arr[lo]`, the middle element and `arr[hi]`. The middle element of an ordered range is its true median, so that input becomes the best case rather than the worst. It also leaves `arr[hi] >=` the pivot, which bounds the ascending scan, so both scans drop their per-element bound check. Speed on hash-table input is unchanged, within 6% in both directions depending on table fill. All-equal input costs ~1.7x more, on an operation taking microseconds. ## Tests The existing tests shuffle before every assertion, so ordered input was never covered. They now also run ascending, descending and all-equal input. The quadratic path returns the *correct* value, so it can only be caught by work done, hence a large ordered array under a time limit — that test takes 10,008 ms before this change and 13 ms after. -- 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]
