本人遇到一个性能方法的问题,这是打标的场景,主要逻辑是三个循环,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;
}
1
liprais 324 天前
你想的太简单了
建议再想想 比如你这 10w 敏感词必须一个一个判断么? 有没有可能搞成前缀树? |
2
BiChengfei 324 天前
试试 parallelStream ?
感觉现在还可以啊,不算慢,资源消耗也还可以,关键实现简单,好维护 |
4
print1024 OP @BiChengfei parallelStream CPU 测试消耗比较大,我们线上 CPU 就 2 核,直接就打满了
|
5
xtreme1 324 天前
ac + double array trie
|
6
alva0 324 天前
改下设计?先将所有关键字去重,放在一个有序集合中,XXDTOList 中的关键字列表存下标,每次 YYDTO 先判断关键字集合,取出包含的所有下标,再与 XXDTOList 比较下标是否存在?这样子试下呢
|
7
zizon 324 天前
YYDTOList.steram().flatmap((yydto)=>{
XXDTOList.stream().flatmap(::getKeywordRule()::stream()).flatmap((keyword)=>{ return Map.Entry(keyword,yydto) }) }).filter((entry)=>{ return entry.values.contains(keyword) }).foreach() 如果不改数据结构/算法本身的话. |
9
corningsun 324 天前 1
首先推测 checkExistRule(List<String[]> keywordRule, String text) 的实现有问题,OP 的实现只会用到第一条规则。
其次 String 的 contains 匹配是数组下标查找,也是一层循环,效率不高。 建议是先分词,得到 哈希数组,然后再比较,示例代码如下: public static boolean checkExistRuleV2(List<Set<String>> keywordRule, Set<String> textSet) { return keywordRule.stream().anyMatch(textSet::containsAll); } Benchmark 压测结果如下:循环 10000 次的时间,从 13 ms 降低到 0.5 ms Benchmark Mode Cnt Score Error Units Print1024Test.checkExistRule avgt 6 13.877 ± 0.148 ms/op Print1024Test.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<String>> keywordRuleSet = keywordRule.stream() .map(Sets::newHashSet) .collect(Collectors.toList()); // 这里可能需要更好的分词手法,trim / 去掉逗号等 public static Set<String> textSet = Arrays.stream(text.split(" ")).collect(Collectors.toSet()); @Test 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(); } @Benchmark @Test @OutputTimeUnit(TimeUnit.MILLISECONDS) public void checkExistRule() { for (int i = 0; i < 10000; i++) { Print1024.checkExistRule(keywordRule, text); } } @Benchmark @Test @OutputTimeUnit(TimeUnit.MILLISECONDS) public void checkExistRuleV2() { for (int i = 0; i < 10000; i++) { Print1024.checkExistRuleV2(keywordRuleSet, textSet); } } } |
10
GuuJiang 324 天前 via iPhone
AC 自动机几乎是多模式匹配的不二解了,你说的“但是因为单条匹配到还要处理业务逻辑”是什么意思,不妨展开讲讲,看到底是什么原因导致了不适用 AC 自动机
|
11
reeco 324 天前
线上 CPU 就 2 核,啥优化都没用
|
12
soupu626 324 天前
理论上这个关键词的命中率应该极低,可以先筛一波,比如关键词建个前缀 map ,这个前缀取多长看你们关键词的区分度,然后先用输入文本过一遍这个 map ,筛出来可能命中的关键词小集合,然后再来全量的遍历
简单脑测了下,前面那个筛过的复杂度应该是 (N-L)*log(M) N 是输入字符串长度,M 是前缀 Map 大小 L 是前缀长度,这样筛出来的小集合理论上应该很小,再过一次 N*S 就行 S 是小集合大小 |
13
print1024 OP @GuuJiang 因为这是一个打标的场景,A 标签规则是一组关键词,B 标签也是一组关键词,如果文本完全命中这些关键词的话怎么区分是 A 标签命中还是 B 标签命中呢
|
14
GuuJiang 324 天前 via iPhone 1
@print1024 这个完全不是问题啊,首先 AC 自动机命中时本来就知道是哪一个关键词命中的,再额外维护一下从关键词到标签的反向关联不就行了,更简单的是在构造 AC 自动机的过程中直接把标签信息冗余到节点上
|
15
print1024 OP @GuuJiang 这个反向关联关系不太好维护,因为多个关键词同时包含才能确定一个标签,拿到了命中的关键词后,去循环查找哪个标签下的关键词组合能够匹配上?那相当于还是要从头到尾遍历一次 XXDTOList 啊
|
16
print1024 OP @corningsun 感谢,checkExistRule 是有问题的,我目前采用了你这种方式,线上 YYDTO 每条耗时差不多 150ms ,因为每次都要过 10w 条 XXDTO
|
18
JKeita 323 天前
trie 树不就行了?
|
19
JKeita 323 天前
trie 数+bitmap ,用 trie 数匹配到的所有关键字生成一个匹配结果的 bitmap ,然后再根据每个标签的关键字独有的 bitmap 一个个比对,成的话就执行相关策略
|
20
yicixin 323 天前
不知道说的对不对,
1.首先看了下示例代码,一个 rule 是一个二维字符串数组,一段文本匹配该 rule 的条件是该文本中出现了 rule 中所有的关键词,既然如此,一个 rule 是否可以简化成一个一维字符串数组,即把二维数组中所有的关键词去重后放入一个一维数组,这样问题可以稍微简化一下。 2.接着,换个思路,把 10w 个 rule 中的所有关键词去重后构造前缀树,用 text 去进行匹配这个 10wKeyTrie ,拿到该 text 匹配到的所有关键词,将匹配到的所有关键词排序后拼接,最终得到一个字符串,例如 text 匹配了关键词 深灰色、锥形牛仔裤和 DIESEL ,假设排序拼接后是 DIESEL 深灰色锥形牛仔裤,记这个最终字符串为 matchText 3.上文说了把一个 rule 简化成一个一维字符串数组,那么每个 rule 也可以进行类似的排序拼接,那么最终 10w 个 rule 就是 10w 个字符串,把这 10w 个字符串构造前缀树,叫 10wRuleTrie 吧,最后用 2.中最后得到的 matchText 放进这个 10wRuleTrie 里进行匹配,如果成功匹配上即说明满足该条 rule 。 其中的 10wKeyTrie 和 10wRuleTrie 都是可以在初始化的时候就可以构造好,每次循环内要做的就是对进行 text 与 10wKeyTrie 的匹配-->得到多个关键词,排序后拼接--> 与 10wRuleTrie 进行匹配 |
22
lrjia 323 天前
ac 自动机 + trie 。记 ac 自动机匹配到的关键字个数为 n ,最终匹配到的规则数为 m 。复杂度最差应该是 O(min(2^n, 10w * n)),一般情况应该是 O(nm) https://pastebin.ubuntu.com/p/JbcMYQqHfp/
|
23
wanqiangcrack 323 天前
你这个优化思路应该是对数据集做索引,做完索引再去匹配。 这样单次需要处理的数据就少很多了。
|
24
crazyweeds 323 天前
DFA 了解一下
|
25
gongxuanzhang 323 天前
前缀树正解。。 而且你这个 try catch 莫名其妙
|
26
missya 323 天前
试试 AI 打标
|
27
vivisidea 323 天前 1
AC 自动机肯定适用。。AC 自动机只是把词库快速匹配出来,你说的逻辑是放在匹配后的处理逻辑,跟 AC 无关
最直接的就是 Trie 树,把所有的词都建一个 trie 树,匹配出一堆词之后再看这堆词属于哪个 label 不好理解的话就试个简单的,先做一道粗筛 包含所有词,意味着也包含所有字 把输入字符串 变成字符 hashset ,kewordrule 也变成多个 hashset ,把原来的多重循环变成 hashset 的交集运算,速度应该会比字符串循环快,粗筛出候选,再走原来的逻辑走精确匹配 |
28
print1024 OP @vivisidea @corningsun @GuuJiang @soupu626 @lrjia 目前采用了 @vivisidea 所说的这种方式,不过我是 AC 自动机+ HashMap<keyword,Set<XXDTO>>这种形式,在数据量大的情况下较 @corningsun 方式速度能提升 10 倍。感谢感谢
|
29
wysnxzm 323 天前
@crazyweeds #24 DFA+1
|
30
MoYi123 323 天前
1. 把关键词列表放到一个 list, 去重排序, 并且把原先的关键词列表替换为这里的 rank, 关键词列表变成 list<list<rank>> 即把 string 离散化.
2. 把上面的 list<string> 变成 ac 自动机, 在文本中搜索. 得到一个 list<int> 3. 在 list<list<rank>>里搜索有哪几个 list<rank>是 list<int>的子序列, 在这里面抄一个最快的算法 https://leetcode.cn/problems/number-of-matching-subsequences/description/ |