如何在 Java 中处理两个映射时增强性能

Question

我有两张地图 -Map<String, List<String>> input，另一张是Map<String, List<String>> output。

输入地图

{A=[Apple.txt, Axe.txt, Aid.txt], B=[Ball.txt, Boy.txt,Box.txt], C=[Cow.txt,Cob.txt]}

输出地图

{A=[Apple.txt, Axe.txt, Aid.txt], B=[Ball.txt, Boy.txt]}

我需要找到输出映射缺少的键值对。

expected output - B= [Box.txt], C=[Cow.txt,Cob.txt]

我需要确定输出映射缺少 Box.txt 对于 B 键和"C"键值对丢失。

我目前的方法：我使用一个forEach(时间复杂度O(n))和一个条目集流(时间复杂度：O(m))用于两个导致O(n*m)时间复杂度的映射。

inputMap.forEach((key,value) ->
{
final List<Path> countrifiedFolderList = outputFileMap.entrySet().stream()
.filter(entry -> entry.getKey().contains(key))
.filter(files -> !files.getValue().contains(inputFile)).map(Map.Entry::getKey)
.collect(Collectors.toList());
if (!countrifiedFolderList.isEmpty())
{....do processing
}

我需要增强性能问题，因为地图包含大量数据。我需要以小于 O(n*m) 的时间复杂度获取结果。

Answer 1

为什么不：

map1.keySet().containsAll(map2.keySet());

更新

使用一个流：

Map<String, List> result = input.entrySet().stream()
.filter(entry -> !output.keySet().contains(entry.getKey()) ||
!output.get(entry.getKey()).containsAll(entry.getValue()))
.map(entry -> {
List<String> expected = new ArrayList<>(entry.getValue());
List<String> current = output.get(entry.getKey());
expected.removeAll(current != null ? current : List.of());
return Map.entry(entry.getKey(), expected);
})
.collect(Collectors.toMap(Entry::getKey, Entry::getValue));

如果你想衡量性能，我建议使用你的数据结构、样本大小、硬件等进行微观基准测试。 如果您对微基准测试感兴趣，我建议您使用 JMH。

Answer 2

如果它们是树状图，则它们的键已经排序。 您可以在 O(n) 中一起浏览这两个列表。 Oboe的解决方案是HashMaps最好的解决方案，它将是O(n*log2(m))。

Answer 3

考虑到output映射是一个Map<String, Set<String>>，然后作为最终结果，能够将完全存在于输出映射中的键视为空[]，很少有事情可以简化解决方案。

Map<String, List<String>> lookUpExclusives(Map<String, List<String>> input,
Map<String, Set<String>> output) {
return input.entrySet().stream()
.collect(Collectors.toMap(Map.Entry::getKey,
e -> e.getValue().stream()
.filter(val -> !output.getOrDefault(e.getKey(),
Collections.emptySet()).contains(val))
.collect(Collectors.toList())));
}

这将从该方法返回{A=[], B=[Box.txt], C=[Cow.txt, Cob.txt]}。就复杂性而言，对于输入映射条目值中的每个元素以及每个N条目的值，这将是M次数，因此也O(N*M)，但这应该是运行时复杂性中最可能的优化。

现在您已经有了这个复杂的运行时，您可以进一步链接另一个流操作来过滤结果中没有任何相应值的条目(例如A=[])。这可以通过在第一个collect之后将以下代码附加到上述管道来实现：

.entrySet().stream()
.filter(e -> !e.getValue().isEmpty())
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

它仅导致复杂性为O(N*M)+O(N)，实际上只能表示为O(N*M)。这里的优点是您可以按照预期的格式获得结果，例如{B=[Box.txt], C=[Cow.txt, Cob.txt]}.