本人遇到一个性能方法的问题，这是打标的场景，主要逻辑是三个循环，YYDTO 中有段文本，XXDTO 中有关键词列表，XXDTOList 量级大约 10 万条必须执行，判断关键词列表是否全部在文本中存在，如果存在则执行业务逻辑；
目前测试了 stream 、parallelStream 、正则和原生的 for 循环，发现下面 checkExistRule 是最快的，大约 50ms ，但是会一直消耗大量 CPU （串行下一直占用 100%）。之前还考虑使用 AC 自动机，但是因为单条匹配到还要处理业务逻辑，所以不太合适。
text 举例 ：
"＃DIESEL 大牌好友＃ @宋雨琦_G-I-DLE 演绎＃DIESEL2023 秋冬系列＃ 牛仔坠饰 D-VINA 包袋。渐变丹宁渲染不羁格调，另类包型注解无畏想象"

keywordRule 中举例：
[鼎赛龙, 男士春夏, D-FINING, 深灰色, 锥形牛仔裤] string[]
[DIESEL, 男士春夏, DFINING, 深灰色, 锥形牛仔裤] string[]
上面这是关键词列表中的一个，总共 10 万个，也就是 10 万个 List 中每个 List 包含 N 个字符串数组

请问有什么方式进行优化？能不能做到时间复杂度 O(1) 或者 O(m + n)级别？

for (YYDTO yydto : YYDTOList) { //2000
String text = yydto.getText();
for (XXDTO xxdto : XXDTOList) {//10w
List<String[]> keywordRule = xxdto.getKeywordRule();
if (checkExistRule(keywordRule, text)) {
// 处理业务逻辑
// yydto.set(xxdto.getName());
}
}
}

private boolean checkExistRule(List<String[]> keywordRule, String text) {
try {
for (String[] strings : keywordRule) {
for (String string : strings) {
if (!text.contains(string)) {
return false;
}
}
return true;
}
} catch (Exception e) {

}
return false;
}

你想的太简单了建议再想想比如你这 10w 敏感词必须一个一个判断么?有没有可能搞成前缀树？

试试 parallelStream ？感觉现在还可以啊，不算慢，资源消耗也还可以，关键实现简单，好维护

这是一个打标的场景，如果关键词全部包含则打上这个标签，考虑过建树但是匹配完如何知道是哪个关键词规则命中呢

parallelStream CPU 测试消耗比较大，我们线上 CPU 就 2 核，直接就打满了

ac + double array trie

改下设计？先将所有关键字去重，放在一个有序集合中，XXDTOList 中的关键字列表存下标，每次 YYDTO 先判断关键字集合，取出包含的所有下标，再与 XXDTOList 比较下标是否存在？这样子试下呢

YYDTOList.steram().flatmap((yydto)=>{ XXDTOList.stream().flatmap(::getKeywordRule()::stream()).flatmap((keyword)=>{ return Map.Entry(keyword,yydto) })}).filter((entry)=>{ return entry.values.contains(keyword)}).foreach()如果不改数据结构/算法本身的话.

哦,没有 early terminate.忽略.

首先推测 checkExistRule(List<String[]> keywordRule, String text) 的实现有问题，OP 的实现只会用到第一条规则。其次 String 的 contains 匹配是数组下标查找，也是一层循环，效率不高。建议是先分词，得到 哈希数组，然后再比较，示例代码如下： public static boolean checkExistRuleV2(List<Set> keywordRule, Set textSet) { return keywordRule.stream().anyMatch(textSet::containsAll); }Benchmark 压测结果如下：循环 10000 次的时间，从 13 ms 降低到 0.5 msBenchmark Mode Cnt Score Error UnitsPrint1024Test.checkExistRule avgt 6 13.877 ± 0.148 ms/opPrint1024Test.checkExistRuleV2 avgt 6 0.528 ± 0.035 ms/op单元测试代码package org.corning.v2ex.year2024;import com.google.common.collect.Lists;import com.google.common.collect.Sets;import org.junit.jupiter.api.Test;import org.openjdk.jmh.annotations.Benchmark;import org.openjdk.jmh.annotations.Mode;import org.openjdk.jmh.annotations.OutputTimeUnit;import org.openjdk.jmh.runner.Runner;import org.openjdk.jmh.runner.options.Options;import org.openjdk.jmh.runner.options.OptionsBuilder;import org.openjdk.jmh.runner.options.TimeValue;import java.util.Arrays;import java.util.List;import java.util.Set;import java.util.concurrent.TimeUnit;import java.util.stream.Collectors;public class Print1024Test { public static List<String[]> keywordRule = Lists.newArrayList( new String[]{"鼎赛龙", "男士春夏", "D-FINING", "深灰色", "锥形牛仔裤"}, new String[]{"DIESEL", "男士春夏", "DFINING", "深灰色", "锥形牛仔裤"} ); public static String text = "＃DIESEL 大牌好友＃ @宋雨琦_G-I-DLE 演绎＃DIESEL2023 秋冬系列＃ 牛仔坠饰 D-VINA 包袋。渐变丹宁渲染不羁格调，另类包型注解无畏想象"; public static List<Set> keywordRuleSet = keywordRule.stream() .map(Sets::newHashSet) .collect(Collectors.toList()); // 这里可能需要更好的分词手法，trim / 去掉逗号等 public static Set textSet = Arrays.stream(text.split(" ")).collect(Collectors.toSet()); public void runBenchmarks() throws Exception { Options options = new OptionsBuilder() .include(this.getClass().getName() + ".*") .mode(Mode.AverageTime) .warmupTime(TimeValue.seconds(1)) .warmupIterations(6) .threads(1) .measurementIterations(6) .forks(1) .shouldFailOnError(true) .shouldDoGC(true) .build(); new Runner(options).run(); } (TimeUnit.MILLISECONDS) public void checkExistRule() { for (int i = 0; i < 10000; i++) { Print1024.checkExistRule(keywordRule, text); } } (TimeUnit.MILLISECONDS) public void checkExistRuleV2() { for (int i = 0; i < 10000; i++) { Print1024.checkExistRuleV2(keywordRuleSet, textSet); } }}

AC 自动机几乎是多模式匹配的不二解了，你说的“但是因为单条匹配到还要处理业务逻辑”是什么意思，不妨展开讲讲，看到底是什么原因导致了不适用 AC 自动机

线上 CPU 就 2 核，啥优化都没用

理论上这个关键词的命中率应该极低，可以先筛一波，比如关键词建个前缀 map ，这个前缀取多长看你们关键词的区分度，然后先用输入文本过一遍这个 map ，筛出来可能命中的关键词小集合，然后再来全量的遍历简单脑测了下，前面那个筛过的复杂度应该是 (N-L)log(M) N 是输入字符串长度，M 是前缀 Map 大小 L 是前缀长度，这样筛出来的小集合理论上应该很小，再过一次 NS 就行 S 是小集合大小

因为这是一个打标的场景，A 标签规则是一组关键词，B 标签也是一组关键词，如果文本完全命中这些关键词的话怎么区分是 A 标签命中还是 B 标签命中呢

这个完全不是问题啊，首先 AC 自动机命中时本来就知道是哪一个关键词命中的，再额外维护一下从关键词到标签的反向关联不就行了，更简单的是在构造 AC 自动机的过程中直接把标签信息冗余到节点上

这个反向关联关系不太好维护，因为多个关键词同时包含才能确定一个标签，拿到了命中的关键词后，去循环查找哪个标签下的关键词组合能够匹配上？那相当于还是要从头到尾遍历一次 XXDTOList 啊

感谢，checkExistRule 是有问题的，我目前采用了你这种方式，线上 YYDTO 每条耗时差不多 150ms ，因为每次都要过 10w 条 XXDTO

这是一个不错的思路，前缀 map 能细讲一下吗

trie 树不就行了？

trie 数+bitmap ，用 trie 数匹配到的所有关键字生成一个匹配结果的 bitmap ，然后再根据每个标签的关键字独有的 bitmap 一个个比对，成的话就执行相关策略

不知道说的对不对， 1.首先看了下示例代码，一个 rule 是一个二维字符串数组，一段文本匹配该 rule 的条件是该文本中出现了 rule 中所有的关键词，既然如此，一个 rule 是否可以简化成一个一维字符串数组，即把二维数组中所有的关键词去重后放入一个一维数组，这样问题可以稍微简化一下。2.接着，换个思路，把 10w 个 rule 中的所有关键词去重后构造前缀树，用 text 去进行匹配这个 10wKeyTrie ，拿到该 text 匹配到的所有关键词，将匹配到的所有关键词排序后拼接，最终得到一个字符串，例如 text 匹配了关键词 深灰色、锥形牛仔裤和 DIESEL ，假设排序拼接后是 DIESEL 深灰色锥形牛仔裤，记这个最终字符串为 matchText3.上文说了把一个 rule 简化成一个一维字符串数组，那么每个 rule 也可以进行类似的排序拼接，那么最终 10w 个 rule 就是 10w 个字符串，把这 10w 个字符串构造前缀树，叫 10wRuleTrie 吧，最后用 2.中最后得到的 matchText 放进这个 10wRuleTrie 里进行匹配，如果成功匹配上即说明满足该条 rule 。其中的 10wKeyTrie 和 10wRuleTrie 都是可以在初始化的时候就可以构造好，每次循环内要做的就是对进行 text 与 10wKeyTrie 的匹配-->得到多个关键词，排序后拼接--> 与 10wRuleTrie 进行匹配

＃15 不用循环查找的，做一个倒排索引就行了

ac 自动机 + trie 。记 ac 自动机匹配到的关键字个数为 n ，最终匹配到的规则数为 m 。复杂度最差应该是 O(min(2^n, 10w * n))，一般情况应该是 O(nm) pastebin.ubuntu.com/p/JbcMYQqHfp/

你这个优化思路应该是对数据集做索引，做完索引再去匹配。 这样单次需要处理的数据就少很多了。

DFA 了解一下

前缀树正解。。 而且你这个 try catch 莫名其妙

试试 AI 打标

AC 自动机肯定适用。。AC 自动机只是把词库快速匹配出来，你说的逻辑是放在匹配后的处理逻辑，跟 AC 无关最直接的就是 Trie 树，把所有的词都建一个 trie 树，匹配出一堆词之后再看这堆词属于哪个 label不好理解的话就试个简单的，先做一道粗筛包含所有词，意味着也包含所有字把输入字符串 变成字符 hashset ，kewordrule 也变成多个 hashset ，把原来的多重循环变成 hashset 的交集运算，速度应该会比字符串循环快，粗筛出候选，再走原来的逻辑走精确匹配

目前采用了 所说的这种方式，不过我是 AC 自动机+ HashMap<keyword,Set>这种形式，在数据量大的情况下较 方式速度能提升 10 倍。感谢感谢

＃24 DFA+1

1. 把关键词列表放到一个 list, 去重排序, 并且把原先的关键词列表替换为这里的 rank, 关键词列表变成 list<list> 即把 string 离散化.2. 把上面的 list 变成 ac 自动机, 在文本中搜索. 得到一个 list3. 在 list<list>里搜索有哪几个 list是 list的子序列, 在这里面抄一个最快的算法 leetcode.cn/problems/number-of-matching-subsequences/description/