Java 多字符串同时匹配文本,消耗 CPU 过高,如何优化?

2024-02-05 11:21:57 +08:00
 print1024

本人遇到一个性能方法的问题,这是打标的场景,主要逻辑是三个循环,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;
    }
    
3665 次点击
所在节点    Java
30 条回复
lrjia
2024-02-05 23:31:24 +08:00
@print1024 #15 不用循环查找的,做一个倒排索引就行了
lrjia
2024-02-06 01:54:36 +08:00
ac 自动机 + trie 。记 ac 自动机匹配到的关键字个数为 n ,最终匹配到的规则数为 m 。复杂度最差应该是 O(min(2^n, 10w * n)),一般情况应该是 O(nm) https://pastebin.ubuntu.com/p/JbcMYQqHfp/
VeteranCat
2024-02-06 08:52:44 +08:00
你这个优化思路应该是对数据集做索引,做完索引再去匹配。 这样单次需要处理的数据就少很多了。
crazyweeds
2024-02-06 09:07:59 +08:00
DFA 了解一下
gongxuanzhang
2024-02-06 09:18:30 +08:00
前缀树正解。。 而且你这个 try catch 莫名其妙
missya
2024-02-06 09:31:32 +08:00
试试 AI 打标
vivisidea
2024-02-06 09:53:29 +08:00
AC 自动机肯定适用。。AC 自动机只是把词库快速匹配出来,你说的逻辑是放在匹配后的处理逻辑,跟 AC 无关

最直接的就是 Trie 树,把所有的词都建一个 trie 树,匹配出一堆词之后再看这堆词属于哪个 label

不好理解的话就试个简单的,先做一道粗筛
包含所有词,意味着也包含所有字

把输入字符串 变成字符 hashset ,kewordrule 也变成多个 hashset ,把原来的多重循环变成 hashset 的交集运算,速度应该会比字符串循环快,粗筛出候选,再走原来的逻辑走精确匹配
print1024
2024-02-06 10:26:12 +08:00
@vivisidea @corningsun @GuuJiang @soupu626 @lrjia 目前采用了 @vivisidea 所说的这种方式,不过我是 AC 自动机+ HashMap<keyword,Set<XXDTO>>这种形式,在数据量大的情况下较 @corningsun 方式速度能提升 10 倍。感谢感谢
wysnxzm
2024-02-06 11:16:19 +08:00
@crazyweeds #24 DFA+1
MoYi123
2024-02-06 14:20:03 +08:00
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/

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://ex.noerr.eu.org/t/1014344

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX