ARTS 第二十三周（2019.9.2~2019.9.8）

[catcuts]

ARTS 第二十三周（2019.9.2~2019.9.8）

• Algorithm 环形链表
• Review 巧用 setImmediate 平衡阻塞与性能
• Tip 条件式 JSON Schema
• Share [极客专栏] 24 | 分布式系统的关键技术：全栈监控

Algorithm 环形链表

题目

环形链表

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let curNode = head;
    while (curNode) {
        nextNode = curNode.next;
        curNode.next = 0;
        curNode = nextNode;
    }
    return curNode === 0;
};

思路：
把遍历到的每个节点的 next 设为 0，如果有一个节点的 next 等于 0 则有环。
一次迭代，故时间复杂度 = O(n)；不占用额外空间，故空间复杂度 = O(1)。
缺点：修改了链表。

对比：
与高分对比：
本代码运行 17 个测试用例花费约 96ms，平均一个测试用例约 5.6ms；
高分代码运行 17 个测试用例花费约 96ms，平均一个测试用例约 5.6ms。

最高分代码如下：
使用快慢指针，不会修改链表。思路见：LeetCode 题解 | 141. 环形链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = head, slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow){
            return true
        }
    }
    return false
};

Review 巧用 setImmediate 平衡阻塞与性能

阅读：
Node.js: How even quick async functions can block the Event-Loop, starve I/O

点评：
有一个 Web 服务，它有两个 API，一个执行 cpu 轻量任务（简单的查询系统数据并返回），另一个执行 cpu 密集任务（进行10^7次加密计算）。

这时，有两个客户端，一个每个 1 秒调用轻量 API，另一个在 5 秒后只调用一次重量 API。

效果是：前 5 秒第一个客户端可以顺利获得数据响应，而 5 秒后第一个客户端的请求就频频超时。

这是因为 cpu 密集任务阻塞了 nodejs 的事件循环。

如何才能使重量 API 不阻塞轻量 API，作者首先尝试了 async/await，但只是简单的把 cpu 密集任务函数外面加了个 async，在内部执行语句前面加了个 await。

这很显然没用，通过实际运行作者也发现了。因为 await 着的并不是一个异步操作，而还是一个同步操作，所以加和不加效果是一样的。

于是作者把单次加密计算装入一个 new Promise 里，然后再进行 10^7 次 await。

效果是有了，不阻塞，但是却降低了 cpu 密集任务的性能，cpu 并没有达到 100%。

于是作者开始分析 nodejs 事件循环的流程，以及其中每个环节的细节，并且深入探究 V8 源码，最后很有把握地得出解决方案。

也就是如题。

具体细节详见原文。

本篇文章干货非常多，读过之后受益匪浅，它不仅通过官方文档和技术文章结合自己的实践加深了对 nodejs 事件循环机制的理解，而且还介绍了不少实用的工具，如可视化堆栈跟踪 Visualize Stack Traces 等。

参考：

• The Node.js Event Loop, Timers, and process.nextTick()
• What is minimum millisecond value of setTimeout?
• Does Node.js enforce a minimum delay for setTimeout?

Tip 条件式 JSON Schema

在有些应用场景下，我们需要根据不同的数据输入采用不同的 schema，比如根据不同的证件类型采取不同的证件号码校验模式（pattern）。

JSON Schema 7.0 草稿中提出了 Applying subschemas conditionally 可以满足上述需求，但是还处于草稿阶段，所以 ajv 并没有实现。

变通之法是，使用 ajv-keywords 来辅助实现，比如：

{
    "type": "object",
    "properties": {
        "identityType": {
            "type": "string",
            "enum": ["身份证", "台胞证", "港澳通行证"]
        },
        "identityNo": {
            "type": "string"
        }
    }
    "allOf": [
        {
            "if": { "properties": { "identityType": { "const": "身份证"  } } },
            "else":{ "properties": { "identityNo": { "pattern": "身份证校验模式"  } } }
        },
        {
            "if": { "properties": { "identityType": { "const": "台胞证"  } } },
            "else":{ "properties": { "identityNo": { "pattern": "台胞证校验模式"  } } }
        },
        {
            "if": { "properties": { "identityType": { "const": "港澳通行证"  } } },
            "else":{ "properties": { "identityNo": { "pattern": "港澳通行证校验模式"  } } }
        }
    ]
}

注：其中 const 即 “恒等于”。

参考：

• ajv conditional schema validation based on data
• oneOf, anyOf, allOf, not
• Applying subschemas conditionally

Share [极客专栏] 24 | 分布式系统的关键技术：全栈监控

分享一篇极客“左耳听风”专栏文章（据说可限10位免费阅读哦）
24 | 分布式系统的关键技术：全栈监控