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

Question

我一直在 HackerRank 上进行一些实践测试，并在某个时候决定仅使用流来解决它(作为个人挑战)。我做到了。程序运行一般。然而，当需要处理大量数据时，程序需要很长时间来完成。因此，最终我没有解决测试，因为“由于超时而终止:(”。我完全同意。当我在自己的电脑上运行这个程序时，不仅花了很长时间才能完成，而且我的工作时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();

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

这一切都以线性时间运行。