zxc0328 / diary-content Goto Github PK

具体的细节请参考Using Tries和Trie树介绍及实现（传统&双数组）

一种和字符串相关的数据结构。这种数据结构可以用来统计大量的字符串，因为前缀树的结构可以压缩占用的空间。

由此想到的是学而的热搜词可以用nginx日志的统计来实现。大数据里面有时候就是围绕着日志去做，我们在这方面还完全没有有意识的去利用日志。所以有时候也很难理解大数据相关的技术到底应该用在什么地方。

最近很火的这篇面试文章里面，提到<script> tag的async和defer有什么区别。这个问题我之前没有了解，然后我只知道js运行会阻塞HTML的解析，但style的解析会不会阻塞呢？

<script> tag的async和defer的区别

对于一个普通的<script>标签，会阻塞浏览器主线程解析DOM。

有async和defer属性的标签则不会阻塞浏览器。从网络中fetch资源这个过程是异步的。但script的执行还是会阻塞主线程。然后区别是defer的script会把所有资源放在DOM构建完成后执行，而且执行顺序是按script标签在文档中出现的顺序。async则是在资源下载完成之后就立即执行，所以顺序是不确定的。两者的时序图可以参考这篇文章。

所以如果是一个独立的模块，可以用async。

But there’s a caveat to this and thats the third point — the script will be exe­cuted the moment it is down­loaded. This can be a non-issue if a script is com­pletely self con­tained. How­ever, in many sit­u­a­tions, scripts may depend on other scripts to have done some ini­tial­iza­tion before they can exe­cute. e.g. jquery plu­g­ins require the jquery vari­able to already exist on the page.

style的解析

style的解析，包括其他的图片等等不会修改DOM树的资源，一般会开一个新的线程解析，因此不会阻塞主线程。但有一种edge case：

There is an issue, though, of scripts asking for style information during the document parsing stage. If the style is not loaded and parsed yet, the script will get wrong answers and apparently this caused lots of problems. It seems to be an edge case but is quite common. Firefox blocks all scripts when there is a style sheet that is still being loaded and parsed. WebKit blocks scripts only when they try to access certain style properties that may be affected by unloaded style sheets.

对于style构建成CSS OM树然后和DOM树结合成为Render树这个过程，How Browsers Work这篇文章里有很详细的解释。但我目前还不是很理解。这个需要进一步的研究。

Links

• How Browsers Work: Behind the scenes of modern web browsers
• Difference between async and defer attributes in script tags
• async vs defer attributes

最近看了Unix diff这个命令，看到输出的格式和Git的diff差不多，想到Git的diff底层应该就是Unix的diff。diff两个文件，diff两个字符串，diff两个dom数组，其实都是可以用一种同样的diff算法去处理。只要diff的对象是一个数组，然后每个item都可以通过==运算符来比较的话，那就可以用diff算法去diff出差别。

Unix diff用的算法叫最小公共子序列，这其实是一个经典的动态规划问题。当时我没有想到这个算法有什么实际作用，现在遇到vdom diff和文件diff的时候才发现这个算法的用处。当然肯定有我不知道的其他很多用处，我觉得学算法，一开始可以了解一下一些基本的**以及经典算法，在后来，要结合业务场景去学，这样的效果才是最好的。

Unix diff算法其实是这篇论文的一个实现。由这篇论文，我可以看出算法科研方面主要在做什么。其实就是对经典的算法，做优化，在时间和空间复杂度上进行优化。经典算法的实现往往是比较简单的，但有优化的空间。我想算法岗的同学，应该做的就是把论文里的算法结合业务去实现吧。读懂论文并实现，以及知道什么业务适合什么算法，是很重要的能力。

我用JS实现了一下LCS，大致就是动态规划去填一个matrix，这个时候要保存公共子序列长度和操作的种类。matrix完成之后我们可以通过回溯去找到最长公共子序列，同时也可以找到把A字符串变成B字符串要进行的操作。

LCS算法有一种常用的优化，叫空间压缩，可以优化空间复杂度到线性。但这个优化的限制是，如果你只想求最长公共子序列的长度的话，那就可以用。但如果想求字符串最短编辑路径，就不能覆盖matrix里之前的节点。所以不能采用这种优化。

所以LCS问题和字符串最短编辑路径问题，其实是同一个。莱维斯坦距离和LCS的区别只在于动态规划的递推式中考虑了Substitution这种情况。

之前对于Function.prototype.bind的实现，就是觉得返回一个新函数，组合一下参数，然后apply一下原来的函数就行。今天看到刘指导的笔记。然后看了韩子迟的文章，意识到这个pollyfill还需要注意返回的新函数被new操作符调用时的情况。

具体就是，如果函数被用new操作符调用，那函数的this就指向自己，这个我不是很清楚，打算去确认一下。然后就手动写一个new的逻辑。把这个搞清楚了，面试必问的，new操作符的过程这个问题，就可以很好的解答了。

Links

underscore 源码解读之 bind 方法的实现