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

Question

我一直在 HackerRank 做一些练习测试，并在某个时候决定只使用流来解决它（作为个人挑战）。我做到了。程序工作一般。但是，当涉及到大量数据需要遍历时，程序需要很长时间才能完成。正因为如此，最终我没有解决测试，因为“因超时而终止:(”。我完全同意。当我在自己的 PC 上运行这个程序时，不仅需要很长时间才能完成，而且我的工作期间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 带来如此大的压力吗？还是只是这个程序？

附注。我上面提到的数据（这个程序无法处理的数据）有 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();

但我认为命令式的方式更清晰。

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