Re: Java 9 and IntSummaryStatistics et al.

[Peter Levart]

On 03/29/2017 06:06 PM, Chris Dennis wrote:
Remi: I really have to squint pretty hard to see that as anything other than 
“brute-force” - it’s still an O(N) calculation.

Here's O(log2(N)):

    static IntSummaryStatistics create(long count, long sum, int min, 
int max) {
        if (count < 2 || min == max) {
            return combineProduct(new IntSummaryStatistics(), count, min);
        } else {
            long minCnt = (count * max - sum) / (max - min);
            long maxCnt = count - minCnt - 1;
            long minSum = minCnt * min;
            long maxSum = maxCnt * max;
            long minMaxSum = minSum + maxSum;
            int mid = (int) (sum - minMaxSum);
            IntSummaryStatistics stats = new IntSummaryStatistics();
            combineProduct(stats, minCnt, min);
            combineProduct(stats, maxCnt, max);
            stats.accept(mid);
            return stats;
        }
    }

    static IntSummaryStatistics combineProduct(IntSummaryStatistics 
stats, long count, int value) {
        IntSummaryStatistics pow2 = null;
        while (count > 0) {
            if (pow2 == null) {
                pow2 = new IntSummaryStatistics();
                pow2.accept(value);
            } else {
                pow2.combine(pow2);
            }
            if ((count & 1L) == 1L) {
                stats.combine(pow2);
            }
            count >>>= 1;
        }
        return stats;
    }


Regards, Peter