java - 为什么基于流的方法需要这么长时间才能完成?
问题描述
我一直在 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 带来如此大的压力吗?还是只是这个程序?
PS。我上面提到的数据(这个程序无法处理的数据)有 73966 个从 1 到 5 的数字。如果这很重要或有人感兴趣......
解决方案
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;
你也可以用 lambdas 做到这一点:
return Collections.max(freqs.entrySet(),
Comparator.<Entry<Integer, Long>>comparingLong(Entry::getKey).thenComparing(Comparator.<Entry<Integer, Key>>comparingInt(Entry::getValue).reversed())).getKey();
但我认为势在必行的方式更清晰。
这一切都在线性时间内运行。
推荐阅读
- android - 更新到 fcm 后,带有 android 棒棒糖的设备崩溃
- c# - Trying to call a function from another form, but it won't work
- jsf - 使用 onclick 事件捕获数据表中单元格的值 -primefaces
- gitlab - Gitlab:如何向请求访问的用户发送消息
- c# - Check if a file is directory in UWP
- azure-machine-learning-studio - 如何在 Azure 机器学习中限制请求参数
- python - 程序跳过列表元素
- python - 将值分配给图像数组的随机块的有效方法?
- java - 如何在java中的坐标数组中找到左上角坐标
- c# - Instantiate the next item when the first item is dropped