java 8 stream finde MIN/MAX restriction

Question

For example there ara code for finde minimum from restricted amount of elements:

public int min(String s) {
    return s.chars().map(this::mapToFactor).min().getAsInt();
}

private int mapToFactor(int ch) {
    switch(ch) {
        case 'A': return 1;
        case 'C': return 2;
        case 'G': return 3;
        case 'T': return 4;
        default: return Integer.MAX_VALUE;
    }
}

Totaly exist only 5 number : 1,2,3,4,Integer.MAX_VALUE. When we faced with 1 then can skip future iteration and return result.

public int min(String s) {      
    int min = Integer.MAX_VALUE;
    for (Character ch : s.toCharArray()) {
        int current = mapToFactor(ch);
        if(current == 1) { 
            //How  I can implement this in Java 8 stream style?
            return 1;
        }
        if (current < min) {
            min = current;
        }
        return min;
    }
}

So on if our String will wary large then we can significantly down performance by using Java 8 stream instead of Java 7 style with skip iterrations if 1 found.

Could you please explain how to write Java 7 code above in java 8 stream style?

Possible duplicate of [How to short-circuit a reduce() operation on a Stream?](http://stackoverflow.com/questions/32495069/how-to-short-circuit-a-reduce-operation-on-a-stream) — user140547, Nov 04 '16 at 10:00
Possible duplicate of [Limit a stream by a predicate](http://stackoverflow.com/questions/20746429/limit-a-stream-by-a-predicate) — the8472, Nov 04 '16 at 10:58

siordache · Answer 1 · 2016-11-04T15:12:17.377

3

The solution below uses the takeWhile method introduced in Java 9. Despite this, the code is still Java 8 stream style.

public int min(String s) {
    IntSummaryStatistics statistics = s.chars().map(this::mapToFactor)
            .takeWhile(i -> i != 1).summaryStatistics();
    int index = (int)statistics.getCount();
    return (index < s.length() && s.charAt(index) == 'A') ? 1 : statistics.getMin();
}

edited Nov 04 '16 at 15:12

answered Nov 04 '16 at 13:21

siordache

112
1
3

score 2 · Answer 2 · answered Nov 04 '16 at 10:48

This is a typical premature optimizing case. If you care about performance, short-circuiting the iteratation, is the last thing, you should worry about.

Let’s look at your Java 7 variant:

for (Character ch : s.toCharArray()) {

Before you even start your iteration, you are calling String.toCharArray(), which creates a copy of the String contents in a newly allocated char[] object. Of course, to create that copy, the implementation has to iterate over the entire String. Before your own iteration even starts.

Then, you are boxing every char value into a Character object. For no recognizable reason, as your mapToFactor method expects an int value, so the Character object has to be unboxed there.

For these reasons, s.chars().map(this::mapToFactor).min().getAsInt() is likely much faster than your Java 7 variant for large strings in most environments. Especially, when we consider that having an A, i.e. reaching the minimum of 1 and being able to exit earlier, is not always the case.

Generally, you should measure actual execution times instead of guessing about assumed deficiencies of a particular method. And only start trying to optimize, if you encounter an actual performance problem. Since you were happy with your original code creating an entire copy of the String, you should be happy with the Stream variant without that unnecessary copy as well. It’s even possible that the HotSpot optimizer adds an early termination condition to the Stream’s internal loop after inlining and analyzing the code.

Eran · Answer 3 · 2016-11-04T08:35:41.673

1

You can run a Stream pipeline that would search for the first occurrence of 1. The problem with that is that if 1 is not found, you'll have to run another Stream pipeline to find the minimum.

Another way I can think of is running a Stream pipeline searching for the first 1 while maintaining the current minimum with peek :

int[] min = {Integer.MAX_VALUE}; // an int[] is used instead of int because the lambda 
                                 // expression cannot assign to a local variable
return s.chars() // get an IntStream of the characters of s
        .map(this::mapToFactor) // map the characters to 1-4 or Integer.MAX_VALUE
        .peek(i -> {if (i<min[0]) min[0]=i;}) // modify min to contain the current minimum
        .filter(i->i==1) // keep only 1s
        .findFirst() // get the first 1
        .orElse(min[0]); // if 1 is not found, return min[0]

Not so elegant, but only processes characters until the first 1 is found.

edited Nov 04 '16 at 08:35

answered Nov 04 '16 at 08:29

Eran

387,369
54
702
768

.peek(i -> {if (i – Alstresh Nov 04 '16 at 09:05
2

@Alstresh `peek` won't run on all the elements. You can add a `println` statement to the `peek` to see that it only processes elements until the first 1 is found. Regarding the state variable, I did say it's not so elegant. Perhaps you'll think of something better. – Eran Nov 04 '16 at 09:09
But any way it is not same as java 7 because 1) First we inerate over all stream to finde i == 1 2) If not found then iterate another one time to finde minimum. It significantly increase complexity in big string witout 'A' – Alstresh Nov 04 '16 at 10:12
1

@Alstresh: A Stream iterates only once. If you don’t understand how Streams work, don’t start such a discussion. There are enough documents in the internet describing the lazy behavior/stream pipeline sufficiently. – Holger Nov 04 '16 at 10:34
1

@Alstresh no, we iterate over the elements just once. If we don't find any 'A', min will contain the minimum at the end of this iteration. – Eran Nov 04 '16 at 10:37
2

Though this `peek` based solution is not only ugly, I doubt that this will raise the performance significantly, compared to the straight-forward, non-short-circuiting solution. – Holger Nov 04 '16 at 10:50

java 8 stream finde MIN/MAX restriction

3 Answers3