Why is the call via stream() so much more time consuming than with if-clauses?

user_14430469 0
Viewed 82

Why is this method:

public static int howManyDifferentFields() {
    int difcolor = 0;
    difcolor++;
    if (fields[1] != fields[0]) {
        difcolor++;
    }
    if  (fields[2] != fields[1] && fields[2] != fields[0]) {
        difcolor++;
    }
    if (fields[3] != fields[2] && fields[3] != fields[1] && fields[3] != fields[0]) {
        difcolor++;
    }
    if (fields[4] != fields[3] && fields[4] != fields[2] && fields[4] != fields[1] && fields[4] != fields[0]) {
        difcolor++;
    }
    if (fields[5] != fields[4] && fields[5] != fields[3] && fields[5] != fields[2] && fields[5] != fields[1] && fields[5] != fields[0]) {
        difcolor++;
    }
    if (fields[6] != fields[5] && fields[6] != fields[4] && fields[6] != fields[3] && fields[6] != fields[2] && fields[6] != fields[1] && fields[6] != fields[0]) {
        difcolor++;
    }
    if (fields[7] != fields[6] && fields[7] != fields[5] && fields[7] != fields[4] && fields[7] != fields[3] && fields[7] != fields[2] && fields[7] != fields[1] && fields[7] != fields[0]) {
        difcolor++;
    }
    if (fields[8] != fields[7] && fields[8] != fields[6] && fields[8] != fields[5] && fields[8] != fields[4] && fields[8] != fields[3] && fields[8] != fields[2] && fields[8] != fields[1] && fields[8] != fields[0]) {
        difcolor++;
    }
    return difcolor;
}

so much faster than this?

public static int howManyDifferentFields2() {
    return (int) Arrays.stream(fields).distinct().count();
}

I would like to use the second way, because it is much less code. But this needs much more time! When I use the second method instead of the first, the program needs round about 8 times more time to finish. What can I do? Can I somehow rewrite the first method to be effective as it is but with less code? In my opinion the second method looks much better...

java-stream data-structures arrays java performance
2 Answers

Most people think streams are fast. But they’re not. There’s a lot of code backing them and it’s that hidden overhead that you’re hitting.

In the general case, a plain for loop is faster than a non-parallel stream (and even parallel streams when the number of elements is not large).

While streams make for neat and powerful code and have lots of benefits, for small streams performance isn’t one of them.

Your logic has O(n2) time complexity, but if n is fixed at 8 you’ll be OK and you can rewrite it as this near equivalent loop:

int difcolor = 8;
for (int i = 1; i < fields.length; i++) {
    for (int j = 0; j < i; j++) {
        if (fields[i] == fields[j]) {
            difcolor--;
            break;
       }
    }
}
return difcolor;

Starting with a perfect score then decrementing on the first match improves the efficiency because it reduces the number of operations by exiting the inner loop as early as possible, similar to your use of short circuiting &&.

You could also use a Set, which has O(n) time complexity and is more compact, but with only 8 elements it will probably be slower than the loop above:

Set<Integer> set = new HashSet<>(); // assuming fields is a int[] 
int difcolor = 0;
for (int field : fields) {
    if (set.add(field)) {
        difcolor++;
    }
}

This works in a similar way to your stream version, but without the stream overhead.

If the elements were sorted, you could do it in a single pass comparing only neighbours.

user_2561960

You go with this solution:-
You can use map to store distinct values.
Also there will default, one count for difcolor so you can start from -1

Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
        int difcolor = 0;
        
        for(int i=0;i <fields.length;i++) {
            if(!myMap.containsKey(fields[i])) {
                difcolor++;
                myMap.put(fields[i], i);
            }
        }
        System.out.println(difcolor);
user_40829460
Related