ARTS 第二十三周（2019.9.2~2019.9.8）
Opened this issue · 0 comments
ARTS 第二十三周（2019.9.2~2019.9.8）
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 | 分布式系统的关键技术：全栈监控