2019-10-15 Daily Report

概览

秋色连波,波上寒烟翠。

时间:Tuesday, October 15, 2019 09:30 AM

作者:Syncher Pylon


  • 处理邮件
  • 更新 Todo List
  • 学习算法
  • 学习英语

今日笔记

JavaScript 的特点: 单线程 +异步

为什么要单线程?

JavaScript does not support multi-threading because the JavaScript interpreter in the browser is a single thread (AFAIK). Even Google Chrome will not let a single web page’s JavaScript run concurrently because this would cause massive concurrency issues in existing web pages. All Chrome does is separate multiple components (different tabs, plug-ins, etcetera) into separate processes, but I can’t imagine a single page having more than one JavaScript thread.

为什么要异步?

在单核 CPU 的机器上,所谓的并发都只是理论上的,CPU 在特定的时刻只能执行一个任务。随着计算机的发展,今天的计算机几乎都是多核的,同一时刻不同的 CPU 执行着各自的任务,着才是真正意义上的并发。在 JavaScript 中,往往有些任务耗时较长,且这些任务有 JavaScript 发起但并没有一直在占用解释器线程,也就是说这些任务需要其他进程(线程)做额外的处理。如果同步执行这些任务将会导致 UI 阻塞,影响用户体验。

UI 加载图片 A 和 B 耗时为 $T_A$ 和 $T_B$,如果同步执行总耗时为:

$$ T_A + T_B$$

如果异步执行,总耗时为:

$$max(T_A, T_B)$$

随着应用复杂性的增加,异步任务会越来越多,同步与异步的优劣为凸显出来。

如何在单线程中实现异步? – Event Loop

在 JavaScript 中,所有的代码都是有序执行的,

1
2
3
4
5
6
let a = 1;
console.log(a);
let b = 2;
console.log(b);

// output: 1 2

所谓的异步只不过是编排代码执行顺序的一种方式,

1
2
3
4
5
6
7
setTimeout(function() {
console.log(1);
}, 1000);
console.log(2);

// output: 2 1
// why?

所有的异步任务最终解决方案都是回调函数,Promise 和 Genarator 都是基于回调函数的上层建筑。那么,基于回调函数的异步是如何实现的呢?

不同的 JavaScript 解释器对异步的实现细节不尽相同,但他们的本质是一样的,那就是事件循环。一段 JavaScript 代执行时,会将任务分为两类(这种任务的分类是广义的,为了简化问题本文使用这种定义):

  • 同步任务
  • 异步任务

简单来说,

  1. 同步任务在主线程中执行,异步任务有专门的线程执行(AJAX 线程)
  2. 异步线程执行完成后进入事件队列
  3. 主线程会在同步任务执行完成后会读取事件队列中的异步任务的结果并执行回调函数
  4. 上述过程不断重复,直到所有任务都执行完成,着就是常说的事件循环 (Event Loop)

异步的解决方案之 Promise

参考 https://promisesaplus.com/ 标准。

Promise 使用

使用 Promise 读取 hello.txt 文件,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const fs = require("fs");
const samplePromise = new Promise((resolve, reject) => {
console.log(1);
fs.readFile("./hello.txt", { encoding: "utf8" }, function(err, contents) {
console.log(2);
// 读取失败
if (err) {
reject(err);
return;
}
// 读取成功
resolve(contents);
});
});

Promise 构造函数

创建 Promise 时需要传递一个含有两个有名参数的执行函数,我们称之为 excutor,一般而言 excutor 中的有名参数统一命名为 resolvereject。使用最原始的回调函数方式在 excutor 中处理异步逻辑(通常而言,这里的异步逻辑是指调用 JavaScript 执行环境提供的异步API,包括 setTimeout, setInterval, XMLHttpRequst 对象,以及 Node 环境下的很多系统调用),以异步处理结果作为实际参数调用 reject 或者 resolve

至此,我们可以抽象 Promise 如下定义:

1
2
3
4
var Promise = function(excutor) {
// We need to define reject and resolve before call the excutor
excutor(reject, resolve);
}

文件读取成功和失败时,分别执行 resolvereject,这说明 excutor 所需的两个参数都必须是函数类型。因此在 Promise 中执行 excutor 之前需要定义两个函数类型的参数 rejectresolve,如下:

1
2
3
4
5
var Promise = function(excutor) {
function resolve(value) {}
function reject(reason) {}
excutor(reject, resolve);
}

Promise 的初始状态为pending,它可以由此转为 fulfilled(一致称之为 resolved)或 rejected

graph TB
0((pending)) --> |done| 1((resolved))
0 -->|failed| -1((rejected))

因此还需要一个 status 属性表示 Promise 的状态:

1
2
3
4
5
6
7
8
var Promise = function(excutor) {
var self = this;
self.status = 'pending';

function resolve(value) {}
function reject(reason) {}
excutor(reject, resolve);
}

then 方法

创建 Promise 实例后,在构造函数中执行异步逻辑,然后在 then 中获取回调结果,基本语法:

1
2
3
4
5
6
7
myPromise.then(onResolve, onReject); 
// onResolve, onReject is a function with one parameter, such as:
myPromise.then((data) => {
console.log(data);
}, (err) => {
console.log(err);
});

读取文件案例如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const fs = require("fs");
const samplePromise = new Promise((resolve, reject) => {
console.log(1);
fs.readFile("./package.json", { encoding: "utf8" }, function(err, contents) {
console.log(2);
// 读取失败
if (err) {
reject(err);
return;
}
// 读取成功
resolve(contents);
});
});

// processing data
samplePromise
.then((data) => {
console.log(data);
}).catch((err) => {
console.log(err);
});

文件读取成功时,then 的 resolve 参数中的 data 参数即为 Promise 构造函数中执行 resolve 时传入的参数,也就是说 data <=> contents

因此, resolve 至少应该完成两件事情:

  1. 更新 status 为 resolved
  2. 将回调数据储存起来,方便 then 方法读取
1
2
3
4
function resolve(value) {
self.status = 'resolved';
self.data = value;
}

then 函数执行时,如果 Promise 为 resolved 状态,则执行传入的 onResolved 函数

1
2
3
4
5
6
7
Promise.prototype.then = function(onResolved, onRejected) {
var self = this;

if (self.status === 'resolved') {
return onResolved(self.data); // 读取 resolve 保存的数据做为成功的参数
}
}

但是,Promise/A 标准中明确规定了 then 要返回一个新的 Promise 对象,所以代码应该如下:

1
2
3
4
5
6
7
8
9
10
Promise.prototype.then = function(onResolved, onRejected) {
var self = this;

if (self.status === 'resolved') {
return new Promise(function(resolve, reject) {
var x = onResolved(self.data);
resolve(x);
});
}
}

需要考虑的问题是,如果调用 then 方法时 Promise 还是 pending 状态我们该怎么办?

如果 then 函数执行时,Promise 的状态依然为 pending,那么我们无法确定后续状态是什么,因此只能将 then 的传递的参数 onResolved 先存起来,等待 Promise 状态变成之后再执行。

  1. 给构造函数添加一个 onResolveCallback

    1
    2
    3
    4
    5
    6
    7
    8
    9
    var Promise = function(excutor) {
    var self = this;
    self.status = 'pending';
    self.onResolveCallback = function() {}

    function resolve(value) {}
    function reject(reason) {}
    excutor(reject, resolve);
    }
  2. 将 onResolved 存储

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    Promise.prototype.then = function(onResolved, onRejected) {
    var self = this;

    if (self.status === 'resolved') {
    return new Promise(function(resolve, reject) {
    var x = onResolved(self.data);
    resolve(x);
    });
    }

    if (self.status === 'pending') {
    return new Promise(function(resolve, reject) {
    self.onResolveCallback = function(value) {
    var x = onResolved(value);
    resolve(x);
    }
    })
    }
    }
  3. 状态更新成 resolved 后执行 onResolveCallback

    1
    2
    3
    4
    5
    function resolve(value) {
    self.status = 'resolved';
    self.data = value;
    self.onResolveCallback(value);
    }

整理一下

上述代码梳理如下:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
var Promise = function(excutor) {
var self = this;
this.status = 'pending';
this.onResolvedCallback = function() {};

function resolve(value) {
self.status = 'resolved';
self.data = value;
self.onResolvedCallback(value);
}

function reject(reason) {}

excutor(resolve, reject);
}

Promise.prototype.then = function(onResolved, onRejected) {
var self = this;
if (self.status === 'resolved') {
return new Promise(function(resolve, reject) {
var x = onResolved(self.data);
resolve(x);
});
}

if (self.status === 'pending') {
return new Promise(function(resolve, reject) {
self.onResolvedCallback = function(value) {
var x = onResolved(self.data);
resolve(x);
}
});
}
}


// ----------------- Test Case ----------
const fs = require("fs");
console.log(2);
var promise1 = new Promise(function(resolve, reject) {
console.log(1);
fs.readFile("./package.json", function(err, contents) {
if (err) {
reject(err);
}

resolve(contents);
})
}).then((data) => {
console.log(3);
console.log(data);
});


console.log(4);

目前代码在正常情况下,似乎可以运行并得到预期结果,只不过还有一些问题:

  1. 构造函数中的 excutor 是有外部创建的,如果执行异常应该直接 reject,如

    1
    2
    3
    new Promise(function(resolve, reject) {
    resolve(data); // data 未定义,程序异常
    });

    所以,构造函数应该对外部定义的函数做风险处理,then 函数中也同理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    var Promise = function(excutor) {
    var self = this;
    this.status = 'pending';
    this.onResolvedCallback = function() {};

    function resolve(value) {
    self.status = 'resolved';
    self.data = value;
    self.onResolvedCallback(value);
    }

    function reject(reason) {}
    try {
    excutor(resolve, reject);
    } catch(e) {
    reject(e);
    }
    }
  2. 调用 then 时,如果传入的 onResolved 返回值是一个 Promise,即 x instanceof Promise,应等待 x 的状态稳定,并采用 x 的状态和值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    var p1 = new Promise(function(resolve, reject) {
    resolve();
    });
    var p2 = p1.then(function(data) {
    return new Promise(function(resolve, reject) {
    resolve(data * 10);
    });
    });

    p2.then((data) => {
    console.log(data)
    });

算法学习笔记

https://leetcode.com/problems/single-element-in-a-sorted-array/

二分规律:如果都是成对出现,那么 A[2 * i] = A[2 * i + 1],所以简单二分如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def singleNonDuplicate(self, A: List[int]) -> int:
l, r = 0, len(A) // 2

while l < r:
m = (l + r) // 2

# f(m) A[2*i] == A[2*i + 1]
# A[m]
if A[2 * m] != A[2 * m + 1]:
r = m
else:
l = m + 1

return A[2 * l]

注意返回的值是 A[2 * l]

英语学习笔记

  • That being said: 也就是说

  • introduce

    bring into use or operation for the first time.

    make someone known by name to another in person.

  • complicated: 复杂的

  • denote: 表示;指示

本文标题:2019-10-15 Daily Report

文章作者:Syncher

发布时间:2019年10月15日 - 09:10

最后更新:2019年10月18日 - 18:10

原始链接:https://0x400.com/2019-10-15-diary-2019-10-15.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。