ARTS 第十三周（2019.6.24~2019.6.30）

[catcuts]

ARTS 第十三周（2019.6.24~2019.6.30）

• Algorithm 有效的字母异位词
• Review Nodejs线程完全指南
• Tip redux-saga 其 fork 与 spawn
• Share 一次性理清字符集与字符编码

Algorithm 有效的字母异位词

题目：

有效的字母异位词

代码（改进前）

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    let i = s.length, j = t.length;
    if (i !== j) return false;  // s 和 t 长度不等则提前返回
    let k = 26, letters = Array(52).fill(0);  // 前 26 个记录 s 后 26 个记录 t
    while (i--) {
        letters[s.charCodeAt(i) - 97]++;  // s 每个字母出现的次数
    }
    while (j--) {
        letters[t.charCodeAt(j) - 71]++;  // t 每个字母出现的次数
    }
    while (k--) {  // s 和 t 字母出现字数必须对应相等才算是互为字母异变词
        if (letters[k] !== letters[k + 26]) return false;
    }
    return true;
};

思路：
见注释。

本代码运行 34 个测试用例花费约 84ms，平均一个测试用例约 2。

虽然时间复杂度达到了较低水平，但是存在一个问题，就是：
使用了固定长度的数组（而且是两倍的），不能适用于扩展情况，如题目说的“如果字符串中包含 Unicode 怎么办”。

所以：

代码（改进后）：

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    let i = s.length, j = t.length;
    if (i !== j) return false;
    let chars = {};
    while (i--) {
        chars[s[i]] = (chars[s[i]] || 0) + 1;
        chars[t[i]] = (chars[t[i]] || 0) - 1;
    }
    while (j--) {
        if (chars[s[j]]) return false;
    }
    return true;
};

该代码运行 34 个测试用例花费约 84ms，平均一个测试用例约 2.5ms。
时间复杂度没有改进，还是 O(3n)，但是允许字符串中出现 Unicode。

另外，官方题解中提到还可以用 sort 对字符串排序，如果排序结果完全相同则为字母异位词。
但是 JavaScript 字符串没有 sort 方法，故不额外实现。

对比：
与高分对比：
本代码运行 34 个测试用例花费约 84ms，平均一个测试用例约 2.5ms；
高分代码运行 34 个测试用例花费约 84ms，平均一个测试用例约 2.5ms。
思路相近代码略。

Review Nodejs线程完全指南

阅读：
A complete guide to threads in Node.js

点评：
本文首先介绍了 Nodejs 的运行原理，即使用了一个主线程 + 事件循环 + 一些辅助线程来进行工作。
这样的工作方式通过异步 IO 实现了在 IO 密集型工作中的高性能，但同时也带来了缺陷，就是不适用于 CPU 密集型的工作（如人工智能，大数据等领域）。
为此，Nodejs 10.5 引入了 worker_threads 模块用于开发多线程任务。

然后理论与示例并茂，依次讲解了 worker_threads 的基本用法和数据交换，并且没有忽略其中的关键要点（特别是不同线程之间的数据交换和转移）。

最后编写了一个 setTimeout 的 worker 版本并与原生 setTimeout 对比作为应用示例。

Tip redux-saga 其 fork 与 spawn

举个例子。
以下代码如果调用的是 yield fork_endless() 那么程序永远不会打印 'Task continued after fork'。
因为 fork 创建出来的 fork 是 attached fork 也就是 “附着型 fork”，它的 fork 效果只限于调用该 fork 的函数；
而如果实际需要的是 detached fork 也就是 “分离型 fork”，那么应该使用 spawn。

const { createStore, combineReducers, applyMiddleware } = require('redux');
const createSagaMiddleware = require('redux-saga').default;
const { fork, take } = require('redux-saga/effects');

// reducer
let rootReducer = state => state;

// sagas
let rootSaga = function*() {
    console.log('Task started');

    // Task never continued since blocked by endless
    // yield endless();

    // Task will continued after fork(endless)
    // yield fork(endless);

    // but Task never continued after fork_endless()
    yield fork_endless();  // because inside fork_endless using fork which creates attached forks

    console.log('Task continued after fork');
};
function* fork_endless() {
    console.log('fork_endless started');
    yield fork(endless);  // use spawn if wanna create a detached fork
    console.log('fork_endless continued after fork');
    // although fork_endless continued after this fork
    // but this is attached fork
    // therefor the rootSaga never get continued until this fork task ends
    // while this fork task is endless
}
function* endless() {
    while (true) {
        yield take('REQUEST');
        console.log('Request received');
    }
}

// store
let sageMiddleware = createSagaMiddleware();
let store          = createStore(rootReducer, applyMiddleware(sageMiddleware));
sageMiddleware.run(rootSaga);

setInterval(() => { store.dispatch({ type: 'REQUEST', payload: 123 }) }, 1000);

Share 一次性理清字符集与字符编码

分享一篇原创 一次性理清字符集与字符编码