Shenlvmeng's Blog

引子

首先我们先来看下面一段代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

(function(){
    console.log(1);

    setTimeout(function () {
        console.log(5);
    }, 0);

    setTimeout(function () {
        setTimeout(function () {
            console.log(8);
        }, 0);
    }, 0);

    (function () {

        console.log(2);

        setTimeout(function () {
            console.log(6);
        }, 0);

        console.log(3);

        setTimeout(function () {
            console.log(7);
        }, 0);

        console.log(4);

    })();

    return 'result';
}());

尽管结构复杂，但是只要对JavaScript的异步和回调有点了解，就能知道它的输出结果是’1 2 3 4 “result” 5 6 7 8’。

并发模型

JavaScript中的异步和回调是语言本身的一种特色。包括上文中的setTimeout函数，Promise对象以及node.js的fs.readFile等。将耗时的操作非阻塞地完成，可以大大提高程序的执行效率。而这些都和JavaScript的并发模型密切相关。与C++, Java多线程处理方式不同，JavaScript中的并发是基于事件循环（Event Loop）的。

Event loop is a programming construct that waits for and dispatches events or messages in a program.

执行图

Stack

函数调用时所用的执行环境栈。当函数被调用时，会进入一个执行环境（execution context）。当在函数内部调用其他函数（或自身调用）时，会进入新的执行环境，并在函数返回时回到原来的执行环境，并将原先的执行环境销毁。根据ECMA定义的概念，代码在执行环境中，还会创建变量对象的作用域链，以确保当前执行环境的有序性。最外层执行环境是全局环境（如window）。具体作用域链和执行环境的介绍，将放在其他文章中进行。

函数执行过程中的执行环境栈即Stack。如下面的代码中，调用g时，形成第一个堆栈帧，包括参数21和局部变量m等。g调用f后，会创建第二个堆栈帧，置于其上，包含f的参数84和局部变量12等。f返回后，第二层栈帧出栈，g返回后，栈就空了。

1
2
3
4
5
6
7
8
9
10
11

function f(b){
    var a = 12;
    return a+b+35;
}

function g(x){
    var m = 4;
    return f(m*x);
}

g(21);

Heap

存放JS中引用类型的堆，JS的引用类型通过类似于图的形式存储，方便进行垃圾回收。具体介绍可以参考红宝书，这里从略。

Queue

JavaScript运行时的待处理消息队列，其中的每个消息都与对应的回调函数绑定（未绑定的消息不会进入队列）。当栈空时，会从栈中取出消息进行处理，这个过程包括调用回调函数，形成调用栈等。当栈在此为空时，代表这个消息处理完成。

首先我们要明确一点，JavaScript的并发是单线程的。在程序中（如浏览器）运行时，JS引擎跑着两个线程。一个负责运行本身的程序，叫做主线程。另一个负责主线程与其他线程的的通信，即Event Loop。当遇到异步的任务时，主线程将交由其他线程处理，并根据情况将对应的消息入队到信息队列（Message Queue）等待处理，如果消息未绑定回调函数，则不入队。

当调用栈清空后，队首消息依次出队，并调用绑定的回调函数，产生函数执行环境和调用栈等。直到消息队列清空为止。以上就是JavaScript中的事件循环。

不同的web worker或跨域的iframe都有各自的栈、堆以及消息队列。不同的环境通过postMessage方法进行通信（需要双方监听message事件）。

setTimeout和setInterval

在明白什么是时间循环后，setTimeout和setInterval这两个定时器函数就比较容易理解了。由于JavaScript运行在单线程的环境里，setTimeout和setInterval的定时时机实际上并不能得到保障。

定时器对队列的工作方式是，在在当前时间过去特定的时间后将代码插入，这并不意味着之后会立即执行，而只能保证尽早执行。。如下面的代码中，设定的250ms延时并不代表在onclick事件触发后的250ms立即执行。实际上，如果onclick的事件处理程序执行超过了250ms，定时器的设置将不再有意义（因为匿名函数的执行时机由onclick事件处理程序何时结束决定）。由此可见，setTimeout的时间间隔往往会比设计时长。

1
2
3
4
5
6

var btn = document.getElementById("my-btn");
btn.onclick = function () {
    setTimeout(function () {
        document.getElementById("message").style.visibility = "visible";
    }, 250)
}

setInterval道理类似，和setTimeout不同的是，setInterval函数会将回调函数定时地插入消息队列的末端。为了避免定时器代码在执行完成前就有新的相同代码插入，造成严重性能问题，聪明的JavaScript引擎仅在队列中没有其他定时器实例时才会插入新的定时器代码。

但是这么做却也带来了一个问题，那就是

1. 某些间隔会被跳过
2. 多个定时器间的间隔会比预期的要小。

后者可以通过循环调用setTimeout来避免。

另外，微软在IE 10中实现了setImmediate方法，来实现真正的回调函数“立即执行”，而在实际运行中似乎和setTimeout的时间类似。

Macrotask 和 Microtask

首先我们还是先来看一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

setImmediate(function(){
    console.log(1);
},0);
setTimeout(function(){
    console.log(2);
},0);
new Promise(function(resolve){
    console.log(3);
    resolve();
    console.log(4);
}).then(function(){
    console.log(5);
});
console.log(6);
process.nextTick(function(){
    console.log(7);
});
console.log(8);

它的结果是什么呢。这里我们就要知道setTimeout, setImmediate, Promise.then, process.nextTick这些异步操作的优先级了。回答这个问题之前，我们先了解一下Macrotask和Microtask两个概念。

Macrotask又叫task，是消息队列中一个个的message，一次event loop里面可能会有多个task，task有自己的task source，比如说setTimeout来自于timer task source，又或者和用户交互相关的来自user interaction task source。

Microtask和Macrotask类似，区别在于它更轻量级，并非每次都在task末尾才执行，只要函数栈为空掉，Microtask就会执行。由此可见它的优先级要更高些。

总结一下，它们的特点如下：

• 一个事件循环(event loop)会有一个或多个任务队列(task queue) task queue 就是 macrotask queue
• 每一个 event loop 都有一个 microtask queue
• task queue == macrotask queue != microtask queue
• 一个任务 task 可以放入 macrotask queue 也可以放入 microtask queue 中
• 当一个 task 被放入队列 queue(macro或micro) 那这个 task 就可以被立即执行了

简单点总结事件循环就是

1. 在 macrotask 队列中执行最早的那个 task ，执行浏览器渲染，然后移出
2. 执行 microtask 队列中所有可用的任务，然后移出
3. 下一个循环，执行下一个 macrotask 中的任务 (再跳到第2步，直到没有task和microtask)

在实现上，macrotask主要有setTimeout setInterval setImmediate I/O UI渲染；microtask主要有Promise process.nextTick Object.observe MutationObserver。由于microtask会耽误task的执行，尤其是在较多时甚至无法执行消息队列中的task，包括UI刷新。因此process.nextTick默认上限为1000，避免上述情况的出现。当调用次数过多时，会抛出栈溢出错误。

所以，上面的执行结果将是3 4 6 8 7 5 2 1

炎热的夏天，聒噪的蝉鸣，人与人间的热气的日光灯下蒸腾。黑板上寥寥数笔，是语文老师画的重点。周围略显浮躁的气氛，《过秦论》的声音此起彼伏。

她是我的一个老朋友，身材小巧，善手工，不乏男性追求。只是她的名字实在是太普通了。我一直都不知该怎么称呼。我和她认识在高一的期末。也许从最初起，我就错了。

眼前的设计展并没有太多游客，我又向她迈近一步。我们已经十多年没见面了。她还像以前那样活泼，浑身上下散发着灵感。

她高一送我的用指甲油涂成的艺术画，我一直都留着。她的点子总是很多，多得让我有些羡慕。我们一起聊过摄影、聊过梦想。雨过天晴，五月份的蓝天映在排球场的水洼里。广播站的屋顶，和风吹过，午后的太阳挂在天际线高楼边。她说她要攒钱买单反，最后拿奥斯卡奖。我说我要考个好大学。楼下，蝼蚁样的人来来去去，头也不回。

那天过后，她送了我第5版的《认识电影》。

这面墙上挂着剪纸和针织作品，角度位置、一分一毫恰到好处。她一动不动，背朝着我。我似乎被巨大的阻力拉扯着，吃力地走到她跟前。

高一结束的一场大雨冲散了太多人。我和她断了联系。小小的筒子楼里，杳无音信，只剩下朋友的称谓悬着，连着。于是在毕业时公车的巧遇后，就再没重逢过。彼时，她送我的那本《认识电影》，我已经看完了。最后，她去了武汉，我来了北京。

其实，之后我们也还有联系。她说武汉天气无常，说要好好学设计，说好久不见。我说北京气候干燥，说我写的信注意查收，说再约再约。那封信，却没听她提起过。

至少联系还在，那个称谓还在，没人碰。

靠近了，我来不及整理要说的只言片语，伸出手轻轻点了她的肩。

转眼四年过去，我们毕业了。她还在武汉，我还在北京。有许多传言，有人说她去学校东门外开了家奶茶店，有人说她和前男友又重归于好。之后发生的事，却是我没想到的。

她来北京了。只可惜我不用微博，否则能知道的更早些。

终于，我们约好在三里屯见面，1月22日。

那天是北京当年最冷的一天。凛冽的冷风肆虐，地面的积雪将整个广场吞没，周围茫茫一片白。水池里的水凝结着，高楼兀立着，指向苍莽的天空。我下了车，被一拥而上的寒意驱动得踏起小碎步。

“我到了”

七分钟后，

“我们下午看电影去吧。我团两张电影票。”

“我们先见面吧，外面真得很冷。”

路上的行人稀稀拉拉，四下只有汽车和寒风呼啸的声响。五分钟后。

“你到了吗？”

“电影票估计是买不到了，我马上到，你先去星巴克等我吧。”

“来这儿找我吧。”说着，我将定位发给了她。

话音刚落，手机因低温自动关机。这该死的自动关机。

这便成为了我和她说的最后一句话。

之后的事情似乎进行地很快了。我去了星巴克，没有人。我回到了定位地点，没有人。一小时后，我去了网吧恢复了手机，没有回复。我联系了我们的共同好友，没有消息。

“您拨打的号码是空号。”雪还在下着，天色已经不早了。

事后出于好奇，我翻了她最常用的微博。第一条状态已是半年前的毕业。看到这儿我就没再翻下去。好像毕业以后，她似乎就变成了另外一个人。疑问没得到解决，她就此消失在我的世界里。

多年后，我因工作原因开通了微博。不知怎地突然想起了她。好奇之下，又去了她的微博。向下翻看时才发现：世上哪有那么多戏剧性。她并没有变成另外一个人。那时看的微博只不过并不是按照时间排序而已。

……

2015/12/20，“You silly dog. I love you so much, plz be a handful forever.”

2016/1/2，“Bye&hi”

2016/1/8，“I get you!”

2016/1/25，“I love and enjoy it！ Skiing!”

2016/2/3，“那些不顺换来的——你，你们和在北京的日子。再见，我们回家。”

……

再之后，她出国留了学，学的设计。再之后和男友定居国外。

6/8，“I am back! The 2nd exhibition in China!”

这场展览是关于日常材料艺术的，其中也包括指甲油。尽管大落地窗外艳阳高挂，场馆却空旷而凉爽。

她近在眼前。我的手指碰到了她的肩，之后又穿了过去。她就像是空气，漂浮在我面前。只见她转过头，还是那副小巧的面孔。我失去了平衡，整个身体与她交错，重重砸在地上

……

炎热的夏天，听不到蝉鸣。我躺在出租屋的床上，一头汗水。午睡的时间，四周一片寂静。眼前没有黑板，也没有老师画的重点，心里像是一下子失去了些什么。

也许，真实的故事里，她和我根本没有这么多交集。也许，我们没聊过梦想。也许，她没送过我书，广播站也并没有屋顶。甚至，她从未在国内办过设计展。而我却是真的。

有时，失去一个朋友真是很容易，就像看一道流星，还没来得及许愿，就从你身边划过。如果她，名字普通的她，看到了这篇故事，也祝愿她一路顺风，拥有崭新的更好的生活。有些事情，本就无是非对错。

本文目的在日后再看到这些名词时能有扫盲的作用，所以未做深入探讨。

二叉搜索树的查询时间复杂度为O(h)，但是h的大小和数据密切相关，随机构建二叉搜索树可以保证期望高度h为O(lgn)，但是我们并不总能随机地构造二叉搜索树。所以就有二叉搜索树的变体来保证基本操作具有好的最坏情况性能，如AVL树，红黑树，treap树，splay树等。它们在二叉搜索树的基础上增加了额外的约束，操作更加复杂，但是保证最坏情况的动态集合操作时间复杂度为O(lgn)。下面按照时间介绍之。

AVL树

AVL树是最早发明的自平衡二叉搜索树，查找、插入、删除在平均和最坏情况下都是O(lgn)，自平衡是通过插入和删除时一次或多次树旋转来完成的。节点的平衡因子是左子树减去右子树的高度，1、0、-1被认为是平衡的，-2或2被认为是不平衡的，需要重新平衡树。平衡因子储存在节点中，或是通过计算算出。

根据不平衡的情况，AVL分成左左、右右、左右、右左四种情况，分别需要1、1、2、2次旋转调整。图略。

由于AVL是高度平衡树，所以节点插入、删除后，重新平衡需要的旋转次数较多，但是因此带来的搜索效率更高。

红黑树

最常见的平衡二叉树，统计性能最好的二叉搜索树。红黑树是满足下列性质的二叉搜索树：

• 每个节点都是黑色或是红色
• 根节点是黑色
• 每个叶节点都是黑色
• 如果一个节点是红色，那么它的两个子节点都是黑色
• 对于每个节点，从它到其所有子孙叶节点的路径包含的黑色节点数目相同

由于没有AVL树对平衡的高度要求，红黑树在节点插入、删除时，只需最多3次旋转操作即可完成。虽然牺牲了查找效率，但是在经常改动的动态数据集合中，红黑树的性能要更好。可以说红黑树在复杂度和旋转次数上有比较好的折中，因此常用作数据结构的设计。

Treap树

Treap树得名于搜索树trea和堆reap，是有一个附加域满足堆特征的二叉搜索树，结构相当于随机插入数据的二叉搜索树，相较其他平衡二叉树，特点是实现简单，且能基本实现随机平衡。

在构成Treap树时，还需要满足堆特征，在插入、删除维护堆性质时，只需要两种旋转，相比Splay，编程复杂度要更小。性能在平衡二叉树和二叉搜索树之间。

Splay树

Splay树又叫伸展树，发明于1985年。它是一种自调整形式的二叉搜索树，利用了频繁查找的数据集有限，在二叉搜索树的每次搜索后，将搜索条目通过一系列旋转搬移到离树根更近的地方。它的优势在于不需要记录平衡树的冗余信息，且编程复杂度小很多。

Splay的操作为旋转，分单旋转、一字型、之字形几种。

这些树的编码都较为复杂，这里略去。

此篇承接上篇CSS和html5标签。写一些CSS3的新特性，flex布局和JS的基础知识。

CSS3

CSS3是较新的层叠样式表的规范，其中的一些特性并未得到现行浏览器的支持。需要在样式前面加上-ms-, -moz-或是-webkit-，才可获得最好的浏览器支持。

边框：CSS3支持设置圆角矩形（border-radius），边框阴影（box-shadow）甚至边框图片（border-image）.

背景：设置背景大小和重复方式（background-size，background-repeat），设置背景所属范围和绘制区域（background-origin，background-clip）

文本效果：文本阴影（text-shadow），断词方式（word-wrap），断句方式（word-break）

字体：支持从外部导入字体（font-face）

2D，3D变换：transform，有rotate，translate，scale，skew，translateX，translateY，rotateX，rotateY等属性。

渐变：transition，选择属性，时间和变换函数。一般结合伪类（如:hover）使用。

动画：keyframe（设置关键帧）+animation（决定动画的名称，持续时间，周期，方向等等）

多列：column-count，column-gap，column-rule，column-span等属性

用户界面：resize支持用户自己调整元素大小等等。

更多内容可以参考W3scool的CSS3讲解。

Flex布局

Flex是一种十分方面的布局方式，可以轻松实现居中对其等需求和响应式布局。目前在较新的浏览器中有支持。Flex需要在display属性中指定为flex。从而使得这个容器有了flex的特点。

flex-direction：指定伸缩容器的主轴方向，即子元素伸缩的方向。有row，row-reverse，column，column-reverse等值。其中row是常用且默认的。

flex-wrap：控制伸缩容器是单行或是多行，即侧轴新行的堆放方向。有no-wrap，wrap，wrap-reverse等值。默认值为no-wrap。

flex-flow：通常将flex-direction和flex-wrap结合起来用flex-flow统一表示。

align-items：控制容器内伸缩项目的侧轴对齐方式。有flex-start，flex-end，center，stretch，baseline等值。

justify-content：主轴上伸缩项目的对齐方式。有flex-start，flex-end，center，space-between，space-around等值。

align-content：多行间在伸缩容器里的对齐方式，有flex-start，flex-end，center，space-between，space-around，stretch等值。

order：通过css动态更改子元素的排列顺序。默认为0，值越大顺序越靠前，可以取负值。

flex-grow，flex-basis，flex-shrink等是更加复杂的用法。这里从略。结合@media screen and (max-width: xxxpx or min-width: xxxpx){ css code}会有很好的响应式布局效果。

更多内容和展示效果，可以在w3plus的flex讲解中找到。

JS与html经验小结

不成篇幅，这里用列表的形式给出。

1. alert()弹出对话框，无返回值；confirm()弹出确认框，返回boolean；prompt()弹出信息框，返回用户输入。
2. document，window，element等是html的js接口中的常用对象，具体可以MDN的技术文档。
3. element代表了页面DOM结构的节点，有文本节点和元素节点的区别。
4. document中的常用函数包括getElementById，getElementsByTagName， getElementsByClassName，createElement等，element中有innerHtml，style，classname等属性值。
5. 添加元素，appendChild，insertBefore，都需要父元素调用，通过parentNode获得。反之，可以通过firstChild，lastChild，nextSibling等获知子元素情况。删除元素使用removeChild。
6. parseInt()是JS的内建函数，用来将字符串转换为整型数，须开头为数字且遇到非数字为止。JS默认均用浮点数存储所有数据，通过isNaN判断是否为数字，isFinite判断是否为无穷。
7. array是JS的基础数据类型之一，以键值对的形式存储，和hashtable很像，有push, reverse, sort, shift, unshift, push, pop, join，reduce等用法。
8. 有foreach的用法
9. 函数也是对象，有诸如arguments，length等属性。可以作为返回值或是输入值。甚至有制造函数的函数。

更多内容可见MDN的技术文档。

前言：与实验室同学参加百度前端学院，做了几个任务，做小小的总结如下。

html5标签

html5标签增加了标签的语义化，更有助于爬虫爬取，代码阅读。对比无意义的div span等标签，article aside section等新标签的语义化更有助于文档结构化。

• article：独立的个体，可以是文章，博客等等。语义上article和article间是独立不相关的。
• section：彼此互补的部分，section间是有共同联系，互补的。section间共同构成一个整体。
• header：article的标题部分，可以是标题，作者，时间等等。
• hgroup：当标题部分的标题很多时，用hgroup包起来。只用h标签就能完成就不需要hgroup。
• aside：侧边栏，与article的主体部分相隔离，可以是额外介绍，可以是用户注册等。
• nav：导航栏，放置网站logo，导航列表等等。
• footer：尾注，可以是版权声明，帮助等等。
• caption：表题。可有可无。
• figure：放置图片，内设img标签。
• figcaption：图片标题
• cite/var/code/samp/kbd：引用、变量、代码、范例、键盘输入域
• datalist：输入列表
• time：时间，放置时间等，内有datetime属性

使用html5标签，格式化文档，将大大增加代码可读性。

css布局

block代表块级元素，有宽和高独占一行；inline代表内联元素，无宽和高，不独占；inline-block内联块元素，不独占一行，有宽和高。

position的取值有4中。static：默认，在文档流中；relative：相对于原位置位移，不移出文档流；absolute：相对于父容器位移，移出文档流；fixed，相当于屏幕位移，移出文档流；sticky，综合relative和fixed设置阈值。

完成多栏设置时，可用inline-block,position:absolute,float。其中float适用性最广，inline-block最简洁，position最笨。使用float时，注意清除浮动。