如何优化Java集合内对象两两比对的嵌套循环 实现按属性分组功能

问题核心 #

你当前的嵌套循环实现时间复杂度是O(n²)，元素数量稍大就会出现明显性能问题，同时还存在修改原对象属性的副作用，完全可以大幅优化。

场景1：按firstName完全相等分组（示例代码逻辑） #

这种场景完全不需要两两比对，单次遍历即可完成分组，时间复杂度降到O(n)，优化后代码如下：

import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

// 优化后的分组方法
private Map<String, List<Person>> personsGroupedByFirstName(List<Person> persons) {
    return persons.stream()
            // 过滤不可达的元素，和原逻辑保持一致
            .filter(Person::isReachable)
            // 按firstName直接分组，单次遍历完成
            .collect(Collectors.groupingBy(Person::getFirstName));
}

如果要保留原逻辑中「匹配后将元素设为不可达」的副作用，只需要加一行遍历修改即可：

private Map<String, List<Person>> personsGroupedByFirstName(List<Person> persons) {
    Map<String, List<Person>> result = persons.stream()
            .filter(Person::isReachable)
            .collect(Collectors.groupingBy(Person::getFirstName));
    // 批量设置已分组元素为不可达
    result.values().forEach(list -> list.forEach(p -> p.setReachable(false)));
    return result;
}

这个实现的循环次数等于元素总数，和你原代码的n²次循环相比性能提升非常明显，比如你示例里28个元素，原代码要跑784次循环，优化后只需要28次。

场景2：按莱文斯坦距离模糊分组（你的实际业务场景） #

如果是需要按字符串相似度分组，也不需要全量两两比对，可以用以下方式优化：

1. 先对所有firstName去重，只比对不同的名字，避免重复计算，比如1000个Person只有10个不同的firstName，比对次数从100万次降到100次
2. 按名字长度分桶，莱文斯坦距离小于阈值k的两个字符串长度差不可能超过k，比如你设置相似度阈值为2，长度差大于2的名字直接跳过计算，不需要调用莱文斯坦距离算法
3. 已经匹配过的名字直接标记，不需要重复比对

优化后示例代码：

import java.util.*;
import java.util.stream.Collectors;

// 相似度阈值，可根据业务调整
private static final int SIMILARITY_THRESHOLD = 2;

private Map<String, List<Person>> personsGroupedBySimilarFirstName(List<Person> persons) {
    Map<String, List<Person>> result = new HashMap<>();
    // 先按firstName预分组，相同名字的先放一起
    Map<String, List<Person>> preGroup = persons.stream()
            .filter(Person::isReachable)
            .collect(Collectors.groupingBy(Person::getFirstName));
    // 存储已经匹配过的名字
    Set<String> matchedNames = new HashSet<>();

    for (String name : preGroup.keySet()) {
        if (matchedNames.contains(name)) {
            continue;
        }
        List<Person> group = new ArrayList<>(preGroup.get(name));
        matchedNames.add(name);
        // 只和还没匹配的名字比对
        for (String otherName : preGroup.keySet()) {
            if (matchedNames.contains(otherName)) {
                continue;
            }
            // 先判断长度差，不符合直接跳过
            if (Math.abs(name.length() - otherName.length()) > SIMILARITY_THRESHOLD) {
                continue;
            }
            // 计算莱文斯坦距离
            if (calculateLevenshteinDistance(name, otherName) <= SIMILARITY_THRESHOLD) {
                group.addAll(preGroup.get(otherName));
                matchedNames.add(otherName);
            }
        }
        result.put(name, group);
    }
    // 如果需要设置不可达，和上面一样加一行即可
    result.values().forEach(list -> list.forEach(p -> p.setReachable(false)));
    return result;
}

// 莱文斯坦距离计算实现
private int calculateLevenshteinDistance(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
    for (int j = 0; j <= b.length(); j++) dp[0][j] = j;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            int cost = a.charAt(i-1) == b.charAt(j-1) ? 0 : 1;
            dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + cost);
        }
    }
    return dp[a.length()][b.length()];
}

内容的提问来源于stack exchange，提问作者looksgoodhoss