V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
print1024
V2EX  ›  Java

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

  •  2
     
  •   print1024 · 74 天前 · 2744 次点击
    这是一个创建于 74 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本人遇到一个性能方法的问题,这是打标的场景,主要逻辑是三个循环,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;
        }
        
    
    30 条回复    2024-02-06 14:20:03 +08:00
    liprais
        1
    liprais  
       74 天前
    你想的太简单了
    建议再想想
    比如你这 10w 敏感词必须一个一个判断么?
    有没有可能搞成前缀树?
    BiChengfei
        2
    BiChengfei  
       74 天前
    试试 parallelStream ?
    感觉现在还可以啊,不算慢,资源消耗也还可以,关键实现简单,好维护
    print1024
        3
    print1024  
    OP
       74 天前
    @liprais 这是一个打标的场景,如果关键词全部包含则打上这个标签,考虑过建树但是匹配完如何知道是哪个关键词规则命中呢
    print1024
        4
    print1024  
    OP
       74 天前
    @BiChengfei parallelStream CPU 测试消耗比较大,我们线上 CPU 就 2 核,直接就打满了
    xtreme1
        5
    xtreme1  
       74 天前
    ac + double array trie
    alva0
        6
    alva0  
       74 天前
    改下设计?先将所有关键字去重,放在一个有序集合中,XXDTOList 中的关键字列表存下标,每次 YYDTO 先判断关键字集合,取出包含的所有下标,再与 XXDTOList 比较下标是否存在?这样子试下呢
    zizon
        7
    zizon  
       74 天前
    YYDTOList.steram().flatmap((yydto)=>{
    XXDTOList.stream().flatmap(::getKeywordRule()::stream()).flatmap((keyword)=>{
    return Map.Entry(keyword,yydto)
    })
    }).filter((entry)=>{
    return entry.values.contains(keyword)
    }).foreach()

    如果不改数据结构/算法本身的话.
    zizon
        8
    zizon  
       74 天前
    @zizon 哦,没有 early terminate.忽略.
    corningsun
        9
    corningsun  
       74 天前   ❤️ 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);
    }
    }

    }
    GuuJiang
        10
    GuuJiang  
       74 天前 via iPhone
    AC 自动机几乎是多模式匹配的不二解了,你说的“但是因为单条匹配到还要处理业务逻辑”是什么意思,不妨展开讲讲,看到底是什么原因导致了不适用 AC 自动机
    reeco
        11
    reeco  
       74 天前
    线上 CPU 就 2 核,啥优化都没用
    soupu626
        12
    soupu626  
       74 天前
    理论上这个关键词的命中率应该极低,可以先筛一波,比如关键词建个前缀 map ,这个前缀取多长看你们关键词的区分度,然后先用输入文本过一遍这个 map ,筛出来可能命中的关键词小集合,然后再来全量的遍历

    简单脑测了下,前面那个筛过的复杂度应该是 (N-L)*log(M) N 是输入字符串长度,M 是前缀 Map 大小 L 是前缀长度,这样筛出来的小集合理论上应该很小,再过一次 N*S 就行 S 是小集合大小
    print1024
        13
    print1024  
    OP
       74 天前
    @GuuJiang 因为这是一个打标的场景,A 标签规则是一组关键词,B 标签也是一组关键词,如果文本完全命中这些关键词的话怎么区分是 A 标签命中还是 B 标签命中呢
    GuuJiang
        14
    GuuJiang  
       74 天前 via iPhone   ❤️ 1
    @print1024 这个完全不是问题啊,首先 AC 自动机命中时本来就知道是哪一个关键词命中的,再额外维护一下从关键词到标签的反向关联不就行了,更简单的是在构造 AC 自动机的过程中直接把标签信息冗余到节点上
    print1024
        15
    print1024  
    OP
       74 天前
    @GuuJiang 这个反向关联关系不太好维护,因为多个关键词同时包含才能确定一个标签,拿到了命中的关键词后,去循环查找哪个标签下的关键词组合能够匹配上?那相当于还是要从头到尾遍历一次 XXDTOList 啊
    print1024
        16
    print1024  
    OP
       74 天前
    @corningsun 感谢,checkExistRule 是有问题的,我目前采用了你这种方式,线上 YYDTO 每条耗时差不多 150ms ,因为每次都要过 10w 条 XXDTO
    print1024
        17
    print1024  
    OP
       74 天前
    @soupu626 这是一个不错的思路,前缀 map 能细讲一下吗
    JKeita
        18
    JKeita  
       74 天前
    trie 树不就行了?
    JKeita
        19
    JKeita  
       74 天前
    trie 数+bitmap ,用 trie 数匹配到的所有关键字生成一个匹配结果的 bitmap ,然后再根据每个标签的关键字独有的 bitmap 一个个比对,成的话就执行相关策略
    yicixin
        20
    yicixin  
       74 天前
    不知道说的对不对,
    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 进行匹配
    lrjia
        21
    lrjia  
       74 天前
    @print1024 #15 不用循环查找的,做一个倒排索引就行了
    lrjia
        22
    lrjia  
       74 天前
    ac 自动机 + trie 。记 ac 自动机匹配到的关键字个数为 n ,最终匹配到的规则数为 m 。复杂度最差应该是 O(min(2^n, 10w * n)),一般情况应该是 O(nm) https://pastebin.ubuntu.com/p/JbcMYQqHfp/
    wanqiangcrack
        23
    wanqiangcrack  
       73 天前
    你这个优化思路应该是对数据集做索引,做完索引再去匹配。 这样单次需要处理的数据就少很多了。
    crazyweeds
        24
    crazyweeds  
       73 天前
    DFA 了解一下
    gongxuanzhang
        25
    gongxuanzhang  
       73 天前
    前缀树正解。。 而且你这个 try catch 莫名其妙
    missya
        26
    missya  
       73 天前
    试试 AI 打标
    vivisidea
        27
    vivisidea  
       73 天前   ❤️ 1
    AC 自动机肯定适用。。AC 自动机只是把词库快速匹配出来,你说的逻辑是放在匹配后的处理逻辑,跟 AC 无关

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

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

    把输入字符串 变成字符 hashset ,kewordrule 也变成多个 hashset ,把原来的多重循环变成 hashset 的交集运算,速度应该会比字符串循环快,粗筛出候选,再走原来的逻辑走精确匹配
    print1024
        28
    print1024  
    OP
       73 天前
    @vivisidea @corningsun @GuuJiang @soupu626 @lrjia 目前采用了 @vivisidea 所说的这种方式,不过我是 AC 自动机+ HashMap<keyword,Set<XXDTO>>这种形式,在数据量大的情况下较 @corningsun 方式速度能提升 10 倍。感谢感谢
    wysnxzm
        29
    wysnxzm  
       73 天前
    @crazyweeds #24 DFA+1
    MoYi123
        30
    MoYi123  
       73 天前
    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/
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2271 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 00:49 · PVG 08:49 · LAX 17:49 · JFK 20:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.