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

[盖楼抽奖] ShowMeBug 自动补全功能原理大揭秘

  •  
  •   ShowMeBug2020 · 2021-07-14 17:09:26 +08:00 · 1353 次点击
    这是一个创建于 1252 天前的主题,其中的信息可能已经有所发展或是发生改变。

    经常有读者问小编,说用 ShowMeBug 做笔面试编程题时代码自动补全功能体验特别好,想知道是怎么实现的。问的人多了,小编就安排了一篇文章来说明自动补全的原理。

    我们日常生活中最常见的自动补全场景是搜索引擎的搜索框,比如下图:

    最简单粗暴的方式肯定是将用户输入的搜索词依次与列表中的字符串进行前缀匹配,如果前缀匹配,就在搜索结果中显示。当要搜索的字符串集合较小时,这么做可以接受,但如果搜索对象集较大,就不那么高效了。

    const texts = ["show", "me", "bug", "money"];
    
    const createFilter = (queryString) => {
      return (text) => {
        return (
          text.toLowerCase().indexOf(queryString.toLowerCase()) ===
              0
        );
      };
    };
    
    texts.find(createFilter('sh')) // return show
    

    如果不用这种方式,那就要考虑字典树了。引用维基百科中关于字典树的定义:

    字典树是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。

    因为是树,其查询效率非常高,如果要查询的字符串长度是 k,则查找的时间复杂度为 O(k)。

    不过字典树比较耗费空间,虽然可以通过三向字典树来进一步节省空间,但对于目前这个需求来说,字典树就够了。

    首先,我们要构建一棵字典树,那该怎么构建呢?

    和二叉树不同,字典树有多个分叉,常见的实现是通过多层数组映射来构建,假设输入的字符串只有 26 个小写英文字母,第一层节点是一个包含 26 个元素的数组 A,数组 A 下标 0 表示 a,依次类推;如果输入的字符 s 后面还有字符 h,则此时数组 A 中 s 的值会保存另一个包含 26 个元素的数组 B,并在数组 B 中表示字符 s 的下标中再存储一个数组 C,依次类推。

    class TrieNode {
        data;
        children = Array(26);
        isEndingChar = false;
        constructor(data) {
            this.data = data;
        }
    }
    
    class Trie {
        root = new TrieNode('/');
    
        insert(text) {
            let p = this.root;
            for (let i = 0; i < text.length; i++) {
                const idx = text[i].charCodeAt() - 'a'.charCodeAt();
    
                if (!p.children[idx]) {
                    const newNode = new TrieNode(text[i]);
                    p.children[idx] = newNode;
                }
                p = p.children[idx];
            }
            p.isEndingChar = true;
        }
    
        find(pattern) {
            let p = this.root;
            for (let i = 0;i < pattern.length; i++) {
                const idx = pattern[i].charCodeAt() - 'a'.charCodeAt();
                if (!p.children[idx]) {
                    return false;
                }
                p = p.children[idx];
            }
    
            return p.isEndingChar;
        }
    }
    
    function main() {
        const trie = new Trie();
        trie.insert("show");
        trie.insert("me");
        trie.insert("bug");
        console.log(trie.find('sh')) // return false
        console.log(trie.find('show')) // return true
    }
    
    main()
    

    相信你现在已经理解自动补全的原理了,下次再用 ShowMeBug 进行笔面试时,可以考虑出字典树的题目哦~

    抽奖啦!抽奖规则

    评论 抽 5 个人

    截止日期为:2021.7.20 12:00

    从回复楼层中随机抽取

    中奖结果会以附言形式公布于本帖,并 @ 各位中奖用户

    奖品为 PingCAP DevCon 2021 年度技术大会单日票

    价值 588 元,还包午餐,是真的香~

    function createRandom(num,from,to)
    {
        var arr=[]; 
        var json={};  
        while(arr.length<num)
        {
            var ranNum=Math.round(Math.random()*(to-from))+from;
            if(!json[ranNum])
            {
                json[ranNum]=1;
                arr.push(ranNum); 
            }
        }
        return arr;
    }
    
    createRandom(10,0,回复楼层) //抽奖
    

    源码引自 yedanbo/createRandom().js

    第 1 条附言  ·  2021-07-14 18:37:55 +08:00
    这次的重点是抽奖哇[狗头保命],PingCap DevCon 送票啦,帮忙盖盖楼就完事啦哈哈哈~

    看来大佬们对 LSP 更感兴趣,我这边跟技术同学联系一下,下次让他们聊聊我们怎么做 Language Server Protocol 补全服务的哇~
    6 条回复    2021-07-22 18:29:52 +08:00
    roostinghawk
        1
    roostinghawk  
       2021-07-14 17:32:20 +08:00
    学习了,谢谢分享
    hronro
        2
    hronro  
       2021-07-14 17:42:43 +08:00
    进来以前我以为是基于 LSP 的补全,进来一看挺失望的
    awing
        3
    awing  
       2021-07-14 18:19:21 +08:00
    标题有点令人误解。。。LSP 大概是实在是没什么可以讲的

    不如改成列表选择性能优化( x

    只是一个列表选择器的算法优化

    这令我想到 `coc-list` `fzf` 之类的列表选择应该也有这种优化
    winkidney
        4
    winkidney  
       2021-07-14 18:23:10 +08:00
    重点难道不是抽奖嘛哈哈哈,坐等中奖了,代码补全什么的我是没看的[狗头保命]
    hronro
        5
    hronro  
       2021-07-22 10:19:49 +08:00
    抽奖没了?因为参与的人少?
    ShowMeBug2020
        6
    ShowMeBug2020  
    OP
       2021-07-22 18:29:52 +08:00
    @roostinghawk @hronro @awing @winkidney 恭喜中奖呀~ 添加我的 wx 领奖吧:cathynoxo

    记得带上账号和帖子的截图哈 O(∩_∩)O~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5976 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 02:16 · PVG 10:16 · LAX 18:16 · JFK 21:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.