双列表前缀搜索时间复杂度优化及Trie实现复杂度辨析

时间复杂度问题澄清 #

• 原始双重循环实现的实际时间复杂度为 O(n * m * k_avg)，其中n为codes集合大小，m为prefixes集合大小，k_avg为字符串startsWith逐字符对比的平均长度，并非严格O(n²)，仅当所有字符串长度一致、内容高度重合时才会退化到平方级。
• 你初版的PatriciaTrie实现，复杂度判断存在两个偏差：
  • 构建Trie的时间复杂度不是O(n)，而是O(total_len_codes)，即所有code字符串的字符总长度，每个字符都需要经过Trie路径完成存储。
  • 你担心的最坏情况确实存在：trie.prefixMap(p)操作分为两步，第一步定位前缀对应节点的时间是O(k)（k为前缀p的长度，和codes规模无关），第二步遍历该前缀下所有匹配code的时间是O(s_k)（s_k为前缀p匹配到的code总数量）。如果存在大量重叠前缀（比如m个前缀都能匹配全部n个code），总时间会退化到O(total_len_codes + mn)*，和原始实现性能接近甚至因为对象构造开销更慢。
• 另外两个实现都存在结果重复的问题：如果一个code同时匹配多个前缀，会被重复加入返回列表，需要根据业务要求判断是否要做去重处理。

当前实现的可优化点 #

• 没有做前缀冗余裁剪：如果前缀集合存在包含关系（比如同时存在"a"和"ab"），匹配"a"时已经拿到了所有"ab"开头的code，再查询"ab"属于完全重复的遍历。
• 直接使用并行流的收益不稳定：小数据量下ForkJoinPool的任务调度开销会超过并行带来的性能提升。
• 没有根据两个集合的规模差异选择Trie的构建方向，固定把codes存入Trie在部分场景下会带来不必要的内存和构建开销。

更高效的实现方案 #

核心选型原则 #

• 如果prefixes规模远小于codes规模（比如百万级codes、几十上百个前缀），优先选择将prefixes构建为Trie，单次遍历codes完成匹配，内存占用更低、遍历开销更小。
• 如果codes规模远小于prefixes规模，再选择你当前的将codes构建为Trie的方案，同时必须做前缀裁剪减少无效遍历。

优化后代码参考（codes建Trie场景） #

public static List<String> getAllPrefixedCodes(Collection<String> codes, Collection<String> prefixes) {
    // 1. 预处理前缀：去重、排序、裁剪冗余前缀
    List<String> sortedDistinctPrefixes = prefixes.stream()
            .distinct()
            .sorted()
            .collect(Collectors.toList());
    List<String> validPrefixes = new ArrayList<>();
    String lastMatchedPrefix = null;
    boolean containsEmptyPrefix = false;
    for (String prefix : sortedDistinctPrefixes) {
        if (prefix.isEmpty()) {
            containsEmptyPrefix = true;
            continue;
        }
        // 已有更短的前缀匹配当前前缀，说明当前前缀是冗余的
        if (lastMatchedPrefix != null && prefix.startsWith(lastMatchedPrefix)) {
            continue;
        }
        validPrefixes.add(prefix);
        lastMatchedPrefix = prefix;
    }

    // 2. 构建codes的PatriciaTrie
    final PatriciaTrie<String> codeTrie = codes.stream()
            .collect(Collectors.toMap(Function.identity(), Function.identity(),
                    (existVal, newVal) -> existVal, PatriciaTrie::new));

    // 3. 收集匹配结果，用Set去重避免多前缀命中同一code的重复问题
    Set<String> resultSet = new HashSet<>();
    if (containsEmptyPrefix) {
        resultSet.addAll(codes);
    }
    validPrefixes.forEach(p -> resultSet.addAll(codeTrie.prefixMap(p).values()));

    return new ArrayList<>(resultSet);
}

该实现的时间复杂度稳定在O(total_len_codes + total_len_prefixes + total_matched)，其中total_matched是所有非冗余前缀匹配到的code总数，不会出现重复遍历同一批数据的问题，在存在大量重叠前缀的场景下性能比初版Trie实现高几个数量级。

适配大规模codes场景的实现（prefixes建Trie） #

public static List<String> getAllPrefixedCodesLargeCodeSet(Collection<String> codes, Collection<String> prefixes) {
    // 仅将规模更小的prefixes存入Trie，大幅降低内存占用
    PatriciaTrie<Boolean> prefixTrie = prefixes.stream()
            .collect(Collectors.toMap(Function.identity(), v -> Boolean.TRUE,
                    (a, b) -> a, PatriciaTrie::new));
    
    return codes.stream()
            .filter(code -> !prefixTrie.prefixMap(code).isEmpty())
            .collect(Collectors.toList());
}

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