为什么基于流的方法需要这么长时间才能完成？

Question

我一直在 HackerRank 做一些练习测试，并在某个时候决定只使用流来解决它（作为个人挑战）。我做到了。程序运行一般。但是，当涉及到 大量数据 时，程序需要很长的时间来完成。正因为如此，最终我因为"Terminated due to timeout :("没有解决这个问题。我完全同意。当我在自己的电脑上运行这个程序时，不仅花了很长时间才完成，而且我的 CPU 工作期间温度飙升...

这是我创建的代码：

List<Integer> duplicatesCount = arr.stream()
        .map(x -> Collections.frequency(arr, x))
        .collect(Collectors.toList());
OptionalInt maxDuplicate = duplicatesCount.stream().mapToInt(Integer::intValue).max();
Set<Integer> duplicates = arr.stream()
        .filter(x -> Collections.frequency(arr, x) == maxDuplicate.getAsInt())
        .collect(Collectors.toSet());
OptionalInt result = duplicates.stream().mapToInt(Integer::intValue).min();
return result.getAsInt();

谁能给我解释一下？流通常会对 CPU 施加如此大的压力吗？还是只是这个程序？

PS。我上面提到的数据（该程序无法处理的数据）有 73966 个数字，从 1 到 5。如果这很重要或有人感兴趣...

Answer 1

duplicatesCount 是通过对数组中的每个元素迭代整个数组来计算的，即它是二次方的。

因此，要处理包含 73,966 个元素的数组，您需要进行 5,470,969,156 次比较。很多了。

Map<Integer, Long> freqs = arr.stream().collect(groupingBy(a -> a, counting()))

将是一种更有效的方法来计算每个元素的频率。这大致等同于：

Map<Integer, Long> freqs = new HashMap<>();
for (Integer i : arr) {
  freqs.merge(i, 1L, Long::sum);
}

即它只是为数组中的每个元素增加一个映射值。

那么，看起来你正在寻找频率最大的最小数字：

int minNum = 0;
long maxFreq = 0;
for (Entry<Integer, Long> e : freqs.entrySet()) {
  if (e.getValue() > maxFreq) {
    minNum = e.getKey();
    maxFreq = e.getValue();
  } else if (e.getValue() == maxFreq) {
    minNum = Math.min(minNum, e.getKey());
  }
}
return minNum;

您也可以使用 lambda 执行此操作：

return Collections.max(freqs.entrySet(),
    Comparator.<Entry<Integer, Long>>comparingLong(Entry::getKey).thenComparing(Comparator.<Entry<Integer, Key>>comparingInt(Entry::getValue).reversed())).getKey();

不过我觉得命令式的方式更清晰

这一切都在线性时间内运行。

为什么基于流的方法需要这么长时间才能完成？

Why method based on streams takes so long to finish?

java

cpu

cpu-usage

java-stream