Passing a non-associative function to reduce

user_530160 0
Viewed 970

My program has this line:

Function<String, Integer> f = (String s) -> s.chars().reduce(0, (a, b) -> 2 * a + b);

The function being passed to reduce is not associative. Reduce's documentation says that the function passed must be associative.

How can I rewrite this as an expression which doesn't break reduce's contract?

java-stream java-8 java
2 Answers

Under the current implementation and IFF you are not going to use parallel - you are safe with what you have right now. Obviously if you are OK with these disclaimers.

Or you can obviously create the function with a for loop:

 Function<String, Integer> f = s -> {
        int first = s.charAt(0) * 2 + s.charAt(1);
        int total = first;

        for (int x = 1; x < s.length() - 1; x++) {
            total = total * 2 + s.charAt(x + 1);
        }

        return total;

    };
user_10593720

You can convert this function to an associative function, as explained in this answer at the example of List.hashCode(). The difference lies only in the factor (2vs.31) and the start value (1vs.0).

It can be adapted to your task, which is especially easy when you have a random access input like a String:

Function<String, Integer> f =
    s -> IntStream.range(0, s.length()).map(i -> s.charAt(i)<<(s.length()-i-1)).sum();

This would even run in parallel, but it’s unlikely that you ever encounter such humongous strings that a parallel evaluation provides a benefit. So what remains, is that most people might consider this solution less readable than a simple for loop…

Note that the above solution exhibits a different overflow behavior, i.e. if the String has more than 32 chars, due to the usage of the shift operator rather than multiplying with two.
The fix for this issue makes the solution even more efficient:

Function<String, Integer> f = s ->
    IntStream.range(Math.max(0, s.length()-32), s.length())
             .map(i -> s.charAt(i)<<(s.length()-i-1)).sum();

If the string has more than 32 chars, it only processes the last 32 chars, which is already sufficient to calculate the same result as your original function.

user_27114880
Related