为什么通过stream()进行的调用比使用if语句要耗费更多时间?

huangapple go评论68阅读模式
英文:

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

问题

为什么这个方法:

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;
}

比起这个方法,为什么快那么多呢?

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

我想使用第二种方式,因为它的代码要少得多。但是第二种方式需要更多的时间!当我使用第二种方法代替第一种方法时,程序完成所需的时间大约增加了8倍。我该怎么办?我是否可以以某种方式重写第一种方法,使其保持原效率但代码更少?在我看来,第二种方法看起来更好...

英文:

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...

答案1

得分: 4

大多数人认为流是快速的。但事实并非如此。在它们背后有许多代码支持,正是这些隐藏的开销在影响着你。

一般情况下,普通的for循环要比非并行流快(即使在元素数量不大时,甚至比并行流还要快)。

虽然流可以产生整洁而强大的代码,并且有许多好处,但对于小型流来说,性能不是其中之一。


你的逻辑具有O(n^2)的时间复杂度,但如果n固定为8,你将没有问题,可以将其重写为以下几乎等效的循环:

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;

从完美分数开始,然后在第一次匹配时递减可以提高效率,因为它通过尽早退出内部循环来减少操作次数,类似于你使用的短路运算 &&

你还可以使用一个集合(Set),它具有O(n)的时间复杂度并且更紧凑,但是只有8个元素时,它可能会比上述循环慢:

Set<Integer> set = new HashSet<>(); // 假设fields是一个int[]
int difcolor = 0;
for (int field : fields) {
    if (set.add(field)) {
        difcolor++;
    }
}

这个方法的工作方式与你的流版本类似,但没有流的开销。

如果元素被排序,你可以在一次遍历中只比较相邻的元素。

英文:

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(n<sup>2</sup>) 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 &lt; fields.length; i++) {
for (int j = 0; j &lt; 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 &amp;&amp;.

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&lt;Integer&gt; set = new HashSet&lt;&gt;(); // 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.

答案2

得分: 1

你可以采用这个解决方案:-
您可以使用映射(Map)来存储不同的值。
此外,对于 difcolor,将有一个默认值,即一个计数,所以您可以从 -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);
英文:

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

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

huangapple
  • 本文由 发表于 2020年10月14日 22:53:49
  • 转载请务必保留本文链接:https://go.coder-hub.com/64356017.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定