aherbert commented on PR #218: URL: https://github.com/apache/commons-numbers/pull/218#issuecomment-5442994759
Thanks for the bug report. This is benchmark testing code in a method not used in the production code. The provided fix discards the bounds containing the pivot returned by the linearSelect method and recomputes them. The correct fix is to identify why the linearSelect method is returning the wrong bounds. This is traced to an optimisation in the partitionKBM method. In the early fast-exit step it returns the bounds for a continuous block of constant data in [l, rr] as the original [l, r]. This is because despite the fact that a[r] can be greater than a[rr] (a[r] >= a[rr]) the range [l, r] is also fully partitioned. The optimisation allows an algorithm always passing the full remaining array into partitionKBM to avoid having to partition a single length array of [rr, r]. It breaks when the array passed to partitionKBM was a sub-range of the remaining data and the returned pivot range must correctly set the lower and upper bound of the constant region. The specific unit test failed as this was the only occurrence where: partitionKBM is used on a sub-range of the current data to partition; and the data contain a constant value v in all but one position (which is higher than v). The correct fix has been applied to the master branch with unit tests to avoid regression. -- 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]
