Java:快速计算多个集合之间共享的项目数

Question

我有 10 个输入集，每个集包含数百个项目(字符串)。

我想要什么:

我想找到至少由两个集合共享的项目，并按在不同集合中出现的次数降序对它们进行排序。

我的方法:

我创建了以下代码。但是，我想知道，是否存在更有效的方法...

Map<String, Integer> sharedCounts = new HashMap<>();

for (int i = 0; i < 10; i++) {
  Set<String> words = getWords(i);
  for (String word : words) {
    if (sharedCounts.containsKey(word)) {
      sharedCounts.put(word, commons.get(word) + 1);
    } else {
      sharedCounts.put(word, 1);
    }
  }
}

Map<String, Integer> sorted = sharedCounts.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); 

Answer 1

您计算计数的算法具有 O(SUM(N_i)) 的渐近复杂度，其中 N_i 是第 i 组单词的大小。这是最快的速度。

您似乎缺少一个过滤步骤，您在该步骤中丢弃了计数为 1 的单词。

Map<String, Integer> sorted = commons.entrySet().stream()
    .filter(e -> e.getValue() > 1) // <<== Add this line
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)); 

整体复杂度为 O(SUM(N_i)+N_distinct-dup*log(N_distinct-dup))，其中 N_distinct-dup 是具有重复的不同单词的数量。