Arts 第二十五周(9/2 ~ 9/8)

270 阅读15分钟

ARTS是什么?
Algorithm:每周至少做一个leetcode的算法题;
Review:阅读并点评至少一篇英文技术文章;
Tip:学习至少一个技术技巧;
Share:分享一篇有观点和思考的技术文章。

Algorithm

LeetCode 1178. Number of Valid Words for Each Puzzle

题目解析

题目给两组单词 words 和 puzzles,然后给出了两个规则:

  • word 包含 puzzle 的第一个字符
  • word 当中的所有字符都在 puzzle 中存在

如果一个 word 对于一个 puzzle 满足上面这两个条件,那么就称该 word 对于该 puzzle 来说是 valid 的,我们要输出,对于每个 puzzle 来说,所有 valid 的单词的数量。

这道题一开始只想到暴力的解法,就是把所有的 word 和 puzzle 都变成集合的形式,然后嵌套 for 循环去判断每个 word 中的字符是不是在 puzzle 中存在,这样来说时间复杂度是 O(n * m * wordLen),这里 n 表示的是 word 的数量,m 表示的是 puzzle 的数量,wordLen 表示的是单词的平均长度,这个时间复杂度会导致一些 test cases TLE,于是必须考虑使用其他的方法。

这道题,每个 word 或者是 puzzle 中的字符只会是小写的字母,也就是说字符的种类不是特别的多,在解决字符查找和匹配中有一个数据结构 - Trie 树,也就是 字典树,它能够很好地解决某些字符串查找的问题,特别是查找前缀。这里,我们的思路是,将所有的 word 用来建立字典树,因为 word 中只会含有小写的英文字母,所以每个树节点的子节点最多也只有 26 个,另外就是树的高度可以看作是最长的单词的长度,在字典树中每个节点表示的是一个字符,一条从上到下的路径表示的是单词,在节点处,我们还需要记录这个节点可以表示多少个 word (会有重复的情况)这么一来,当我们构建完整颗树,对于每个 puzzle,都可去树上找到符合条件的单词的数量,我们可以把时间复杂度变成 O(m * 26^puzzleLen),直观上,这个时间复杂度并没有比之前的快多少,但是从 testcase 的参数规模来看,puzzle 和 word 的长度都会比较小,但是总数量会非常的大,在这种情况下,这样的时间复杂度确实比之前更优。

这里还有一个 Trie 树上面压缩路径个数的技巧就是,对于每个 word,我们都先将其排序,这样一来 word 的总数量会大大减小,举个例子,abc, cba, bca 拍完序后都会变成 abc,在 Trie 树上我们只需要表示 abc 这么一条路径就够了,然后在末尾节点,这里就是 c 上,填写表示的单词个数就行,节省了空间也节省了时间。我这里使用 TreeSet, 也就是有序集合去提前预处理 word 和 puzzle,因为每个 word 和 puzzle 的长度并不大,因此使用 TreeSet 的时间开销并不大。


参考代码

private class TrieNode {
    TrieNode[] children = new TrieNode[26];
    int count = 0;
}

private void buildTrie(Set<Character>[] wordSet, TrieNode root) {
    if (wordSet == null || wordSet.length == 0) {
        return;
    }
    
    for (Set<Character> word : wordSet) {
        TrieNode pointer = root;
        
        for (char c : word) {
            if (pointer.children[c - 'a'] == null) {
                pointer.children[c - 'a'] = new TrieNode();
            }
            
            pointer = pointer.children[c - 'a'];
        }
        
        pointer.count++;
    }
}

public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    TrieNode root = new TrieNode();
    
    Set<Character>[] wordSet = convert2Set(words);
    Set<Character>[] puzzleSet = convert2Set(puzzles);
    
    buildTrie(wordSet, root);
    
    List<Integer> results = new ArrayList<>();
    
    for (int i = 0; i < puzzles.length; ++i) {
        int count = helper(puzzleSet[i], root, puzzles[i].charAt(0), false);
            
        results.add(count);
    }
    
    return results;
}

private int helper(Set<Character> puzzleSet, TrieNode root, char first, boolean isFind) {
    if (root == null) {
        return 0;
    }
    
    int count = isFind ? root.count : 0;
    
    for (char c : puzzleSet) {
        if (c == first) {
            count += helper(puzzleSet, root.children[c - 'a'], first, true);
        } else {
            count += helper(puzzleSet, root.children[c - 'a'], first, isFind);
        }
    }
    
    return count;
}

private Set<Character>[] convert2Set(String[] words) {
    Set<Character>[] result = new Set[words.length];
    
    for (int i = 0; i < words.length; ++i) {
        result[i] = new TreeSet<Character>();
        
        for (char c : words[i].toCharArray()) {
            result[i].add(c);
        }
    }
    
    return result;
}

Review

Focus and Deep Work — Your Secret Weapons to Becoming a 10X Developer

之前一直提到的一个东西 “10X 程序员”,这里并不是具体指那些比一般程序员有 10 倍效率的程序员,而是说工作效率高,产出高的程序员,10X 其实是一个有点夸张的表示,如果你能做到 5X 甚至是 2X,1X 都会有很多公司青睐,1X 意味着干好自己的本职工作,这对于雇佣你来工作的公司来说,花钱雇你至少不是一桩亏本买卖,当然如果你能做的更好,那么你升职加薪的可能性也就会更大。文章中一直强调两个概念,专注深度工作,其中专注是深度工作的前提,对于专注,文章给了两条建议:

  • 在专注做某件事之前,排除一切的外界干扰,如手机、微信、甚至说是电脑上面的无关网页或者是程序,保证自己在投入做事的时候不会被这些外界事物分散注意力
  • 使用 番茄计时法,这个方法对我来说并不陌生,第一次看到这个方法是在 《学习之道》这本书中。其实这个方法听起来特别的简单,就是使用一个定时器定时,然后在这段时间里,你需要全神贯注地做一件事情,等到时间到了后,停止手上面的事情,然后开始放松,这个原理其实是 “每个人的集中注意力的时间是有限的”,就好比你一直全神贯注 3 个小时,那么可能头半个小时是你注意力最集中,效率最高的时候,后面的时间可能你会感觉到疲倦或是精力分散,文章中也给出了蕃茄计时法的几个重点:
    • 一开始可以把时间定为 25 min,根据自己的情况可以调整高低,不管时间是多少,需要保证的是你在这段时间内心无旁骛,全神贯注,一开始可以定低些,然后慢慢提升
    • 不仅让你更加投入,你还可以根据这个计时法来规划并拆分你的任务,让你对时间的敏感度提升,比如说,对于一个大任务,可以拆分成几个小任务,每个任务用一个番茄周期完成
    • 需要逐步记录并增加一天当中的番茄周期,一开始,不适应,可能一天只能完成一个番茄周期,但是慢慢地,坚持下去,你会发现你最大能够 handle 的番茄周期在增加

学习需要心无杂念,不被干扰,这个也是高效学习的前提,文章中强力推荐一本书 《Deep work》,感觉很有用,后面会找时间来看。


Tip

在学习浏览器专栏中,明白了几个经常听到的概念:

  • 静态语言动态语言:静态语言在程序运行之前就需要确认其变量的数据类型,动态语言在运行过程中需要检测数据类型
  • 弱类型语言强类型语言:弱类型语言支持隐式类型转换,强类型语言不支持隐式类型转换
  • 关于 垃圾回收 的几个算法:
    • Scavenge 算法
    • 标记 - 清除(Mark-Sweep)
    • 标记 - 整理(Mark-Compact)
    • 增量标记(Incremental Marking)
  • 即时编译(JIT):解释器和编译器配合字节码的技术

Share

这次分享两篇关于软件测试的文章:

How to test software, part I: mocking, stubbing, and contract testing

How to test software, part II: TDD and BDD

这次的 Share 部分就来谈谈几个话题

  • 为什么要写测试 (Why)
  • 具体写什么样的测试 (What)
  • 怎么样写好测试 (How)

为什么要写测试

首先对于第一个问题,我并不想花太多的时间来赘述,我只想说说测试的目的,测试的目的就是让程序员能够交付高质量的代码,并且让程序员对自己写的东西有足够的认识和自信。怎么解释呢?首先测试反应了我们对我们自己写的代码的预期,你可能会说,我们心里都知道预期了,还需要测试干嘛。对于非常简单的程序,测试确实并不能体现其价值,但是项目的规模一旦增大,你写的模块逐渐增多,写着写着你可能会忘记你之前写的模块的具体目的,一旦需求有变化,你需要改代码,那么你也可能不清楚该从哪里改起,因为东西太多了,如果有文档描述可能会好些,没有的话,你可能需要回过头去仔细看自己之前写的代码,然后将其修改,修改过后你也不清楚这样的修改是不是违背了自己当初的设计,因为仅仅看未完成的代码本身是很难发现其设计的

对于上面提到的这些不写测试会出现的问题是不是写了测试就一定能够解决呢?这个我不敢保证,但是写测试一定会减少上述问题出现的几率。首先你有了测试,当新的需求过来的时候,至少你可以根据测试去看高层设计逻辑,从测试看设计会比直接从代码看测试简单不少,因为对于一个模块,看其测试等同于跳过模块的具体实现直接看输入输出,如果你测试文件名称或是注释写好的话,需要仔细推敲的东西就会很少,而代码则充斥着种种细节,理不清方向,直接从细节入手,效率什么的可想而知。

另外一点就是,我们手握着测试,不管需求怎样变,代码怎么样改,我们都需要代码通过对应的测试,这样对代码的质量有了多一层保障,我们对自己写的东西才会有自信,当整个系统出了问题,我们心里其实可以大概率确定我们自己的代码没有问题,就算有问题也可以通过测试很快定位到程序的问题所在。总结下来,写测试的目的其实有两个:

  • 帮助程序员写出高质量,不出错的代码
  • 帮助程序员设计并且回顾整个项目的代码框架,对自己写的程序更加自信

具体写什么样的测试

上面的两篇文章中对这一点有比较好的解释,这里我盗用文章当中的一张图:

图上面显示的是一个金字塔,它其实表示的是 3 种测试,以及它们之间的区别和联系,我们从金子塔顶往下看。位于金字塔顶的是 “UI Layer Tests”,其实就是最高层的测试,举例子来说,如果整个项目是开发一款手机 app,那么这个测试就是等整个应用都完成了进行的测试,测试人员其实就等同于实际的用户,他们直接去操控 app 上面的 UI 去看 app 上面能不能呈现他们想要的结果,虽然说有工具可以辅助这样的测试,但是 这样的测试其实很难看出具体的数据是否存储正确,模块里面是不是隐藏着 bug,这就好像一个人在你面前蹦蹦跳跳,你只能确定其四肢健全,但是你不能说他身上没有任何疾病。因为这种测试需要整个项目都完成的差不多了,所有人都交付了他们负责的模块,这样的测试才能展开,因此这样的测试也快不起来,如果发现问题,需要向下排查,先定位到大的模块,再到小的模块,层层向下,最后才能定位到出错的代码,时间和资源开销也是昂贵的。

倒数第二层,“Integration Tests”,这个测试是属于模块和模块之间的连接测试,一个大的应用其实是由很多个小的模块,或是很多层组成,每个模块各司其职,但是这些模块之间是需要连接交互的,这种端到端的测试就是为了保证每个模块整体和模块之间的连接不出错。

第一层,也就是我们开发程序员熟悉的 Unit test,这一层的测试直接对应到函数或者文件,金字塔越往下越基础,万丈高楼平地起,基础的东西其实才是最重要的,这些测试往往就是几行代码或者一两个文件,人力方面的话,只需要一个人,就是写对应实现代码的人,这其实是非常廉价的,但是 Unit test 数量相对来说会比较多,覆盖的面会更加的细致,写 Unit test 一开始可能会觉得很烦,但是写多了,它其实可以增加你对代码的认识,以及清楚你自己的设计。


怎么样写好测试

在开始之前需要解释几个名词,分别是 mockstubTDD

往往我们在代码中实现的函数或者是模块是相互连接的,但是在写测试,特别是端到端的测试的时候,我们没有办法马上得到其他连接模块的信息,但是我们这里又需要其他模块的输出内容作为输入,这时我们就需要假定这个模块实现好了,那么它的正常情况下的输出会是哪些?这其实就是 mock,也就是模拟其他相关模块的动作,计算机领域很多地方都利用了这样的理念,比如说一个 server 其实是知道其他 servers 会传什么样格式的信息过来,这是因为有协议的存在,协议的目的其实就是把部分组装成整体的一个东西。这里说的 mock 也是类似的概念。

和 mock 类似的是 stub,对于一个模块来说,stub 和 mock 的区别在于,mock 是模拟整个外部环境,而 stub 只是模拟部分外部环境,比如说当前的系统连接着一个大的系统,mock 的话就是模拟整个系统,而 stub 仅仅是模拟这个大的系统和当前的系统相关的部分。

TDD,全称 Test-Driven-Development,这是一个测试的策略,它可以用下图表示

TDD 主张先写测试,写完测试,这个时候还没有写对应的代码,那这里测试是不能通过的,这一阶段就是图中的 Red,完成之后我们会进入第二阶段 Green,在这一阶段我们开始实现具体代码,这一阶段我们需要确保两件事情:

  • 实现代码中的代码架构要和测试代码中的架构吻合
  • 实现代码需要完完整整通过测试

其实到这里,可以说程序的雏形已经出来了,但是问题是,需求是有变更的,另外随着我们对我们写的代码的反复确认,以及 code review 之类的流程,我们会发现代码中存在的问题,比如代码风格,布局,甚至实现逻辑等等,我们往往会对代码进行重构来提升代码的整体质量,这时我们就会来到第 3 个阶段 Refactor,在这一阶段,我们会调整代码,但是这个时候我们是有测试的,我们需要保证重构后的代码依然可以通过测试,因此第三个阶段过后又会回到第一个阶段,也就是我们需要根据需求变化调整之前写的测试,然后再调整代码,这样循环迭代来保证代码的质量。

有了策略和具体的方法,让我们回到 “具体写什么样的测试” 中提到的 3 种不同的测试,如果要把 TDD 理念应用到金字塔中,该如何进行呢?首先我们需要从上到下写测试,先是最顶层的 UI Layer Tests,与其说写测试,你可以认为是帮助自己理清整个设计的框架,我们只需要把测试放在这里,甚至说用伪代码写都可以,最主要是认清整个项目或者说是产品的宏观需求;然后到 Integration Tests,这一层也是写测试,并不是写了就不变了,在这一层上,通过写测试让你清楚你的模块是如何和别的模块交互的,这里也没有涉及细节上面的实现;最后到底层,这里你需要好好设计你的模块了,到这里,我们基本上已经通过上面两层得知自己当前要实现的模块的具体位置、负责的功能还有就是和哪些其他模块进行交互,这个时候重点可能需要放在理清本模块中的脉络了,也就是具体要拆分成哪些文件,哪些函数,每个函数有哪些输入输出。等到我们实现完测试,然后我们可以开始写对应的实现代码,写实现代码的流程则是从下到上,也就是先确保每个函数的输入输出正确,然后保证模块正确,最后保证整个系统正确


总结

这就是基本的测试,开发程序员也需要了解测试,你可以看到 Unit test 是基础,而最能写好 Unit test 的人是写实现代码的人本身。写好程序从写好测试开始,加油~