ARTS 第六周（2019.5.6~2019.5.12）

[catcuts]

ARTS 第六周（2019.5.6~2019.5.12）

• Algorithm 两个数组的交集 II
• Review 如何优化 JS 循环
• Tip socket.io 使用 jwt 认证
• Share 一次性理清 JS 实例化机制与继承机制

Algorithm 两个数组的交集 II

题目：

两个数组的交集 II

代码（给定未排序）：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let result = [];
    if (nums1.length < nums2.length) [nums1, nums2] = [nums2, nums1];
    for (let i = 0, len = nums1.length; i < len; i++) {
        let index = nums2.indexOf(nums1[i]);
        if (index !== -1) result.push(nums2.splice(index, 1));
    }
    return result;
};

代码（给定已排序）

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let result = [];

    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);

    if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];

    for (let i = 0, j = 0, len = nums2.length; j < len; i++, j++) {
        let num1 = nums1[i], num2 = nums2[j];
        if (num1 === num2) result.push(num1);
        else if (num1 < num2) j--;
        else i--;
    }

    return result;
};

思路：
不排序就是一个个遍历，没什么办法，时间复杂度 O(n²)
排序后再遍历，时间复杂度 O(log²n + n)
但只有在 n 较大的情况下，先排序才有优势
如果 n 比较小，不排序实际所需时间可能更少

对比：
与最高分对比：
不排序代码运行 61 个测试用例花费约 96ms，平均一个测试用例约 1.6ms
排序代码运行 61 个测试用例花费约 116ms，平均一个测试用例约 1.9ms
与最高分相近，查看代码思路也相近

// 代码略

Review 如何优化 JS 循环

阅读：
How to optimize your JavaScript apps using Loops

点评：
本文针对 JS 中不同形式的循环逐个提出了优化的思路和示例
核心思路就是：尽量减少循环的每一轮工作量，以及尽量减少循环的总次数
如：

1. For 循环

// 原本的循环
for (var i = 0; i < items.length; i++){
    process(items[i]);
}
// 避免每轮计算长度（优化了循环每轮工作量）
for (var i = 0, len = items.length; i < len; i++){
    //           ^
    process(items[i]);
}
// 索引移动和循环判断一起做（优化了循环每轮工作量）
for (var i = items.length; i--; ){
    //                      ^  ^
    process(items[i]);
}

2. While 循环

// original loop
var j = 0;
while (j < items.length){
    process(items[j++]);
}
// minimizing property lookups
var j = 0,
    count = items.length;  // 在这里计算长度，避免每轮都计算一次
while (j < count){
    process(items[j++]);
}
// minimizing property lookups and reversing
var j = items.length;
while (j--){  // 索引移动和循环判断合在一起做了
    process(items[j]);
}

3. Do-While 循环

// original loop
var k = 0;
do {
    process(items[k++]);
} while (k < items.length);
// minimizing property lookups
var k = 0,
    num = items.length;  // 同理，在这里计算长度，避免每轮都计算一次
do {
    process(items[k++]);
} while (k < num);
// minimizing property lookups and reversing
var k = items.length - 1;
do {
    process(items[k]);
} while (k--);  // 同理，索引移动和循环判断合在一起做了

另外还提到了 For-in 循环
For-in 循环不能用在数组遍历上，只能用于对象遍历上
并且在引用对象的属性时，会触发原型链查找
因为如此，它的速度远没有前面三个循环来得快，也没有什么优化空间

Tip socket.io 使用 jwt 认证

catcuts/demo_passport_for_socketio
这是一个使用 passport 进行认证的 socket.io 应用示例
认证策略包括：passport-local 和 passport-jwt

Share 一次性理清 JS 实例化机制与继承机制

分享原创一篇：一次性理清 JS 实例化机制与继承机制