使用高性能 JavaScript 解决难题

过早优化是万恶之源，也是本文的根源。

我喜欢编程难题，也喜欢快速完成。我们将选一些 LeetCode 题目，反复练习，首先粗略地改进运行时复杂度，然后再寻找细微的优化点。我们追求的是这些精彩的词句：

比 100.00% 的 JavaScript 在线提交速度更快

我们的目标环境是nodejs 10.15.0（--harmony来源）。据我所知，在线评判系统对测试用例的输入相对较小。

第一个问题

771. 珠宝与石头~给定一个字符串，J分别代表宝石的种类和S你拥有的石头。字符串中的每个字符S代表你拥有的一种石头。你想知道你拥有的石头中有多少是珠宝。

这里一个简单的解决方案是循环遍历我们的石头，循环遍历每颗石头对应的宝石。在本文中，我们将使用标准的 for 循环，因为它们通常是 JavaScript 中迭代数据最快的方法。

var numJewelsInStones = function(J, S) {
    let myJewels = 0;
    // Jewels
    for (var i = 0; i < J.length; i++) {
        // Stones
        for (var j = 0; j < S.length; j++) { // Nested!
            if (J[i] === S[j]) {
                myJewels++;
            }
        }
    }
    return myJewels;
};

运行时间是二次函数O(N^2)。他们的在线评判员实际上不会接受这个解决方案！我们得到了一个大大的“超出时间限制”的错误提示。教训是什么？应该尽可能避免使用嵌套的 for 循环。

让我们用一个Set来摆脱其中一个循环。这样就能把运行时间缩短到线性的了O(N)。在 JavaScript 中查找 Set 是常数时间的O(1)。

var numJewelsInStones = function(J, S) {
    const jewels = new Set(J); // Set accepts an iterable object
    let myJewels = 0;
    for (var i = 0; i < S.length; i++) {
        if (jewels.has(S[i])) {
            myJewels++;
        }
    }
    return myJewels;
};

这份努力得到了回报faster than 97.84%。我对这段代码很满意。它高效易读。如果我需要大幅提升性能，我可能会选择 JavaScript 以外的其他技术。我们必须至少遍历两个字符串的长度一次，这是无法避免的。我们无法超越，O(N)但可以进行优化。

石头和珠宝被定义为字母。所以a-z和A-Z。这意味着我们的值只能落入 52 个不同的桶中！我们可以使用布尔数组代替 Set。要将字母转换为数字，我们将通过charCodeAt使用它的 ASCII 码位。我们将设置一个索引来true表示珠宝。

然而，JavaScript 中没有布尔数组。我们可以使用标准数组并将其初始化为 length 52。或者，我们可以使用Int8Array并允许编译器进行额外的优化。在使用和等一系列0-52随机字符进行基准测试时，类型化数组的速度提高了约 6% 。JS

你发现我们的长度不对了吗？这是我测试时忘记的。在 ASCII 码表中z，和之间有 7 个字符A，所以实际需要的长度是 59。

var numJewelsInStones = function(J, S) {
    const jewels = new Int8Array(59);
    for (var i = 0; i < J.length; i++) {
        jewels[J.charCodeAt(i)-65] = 1;
    }
    let myJewels = 0;
    for (var i = 0; i < S.length; i++) {
        if (jewels[S.charCodeAt(i)-65] === 1) {
            myJewels++;
        }
    }
    return myJewels;
};

瞧，我们的100% fastest 提交完成了。在我的测试中，这实际上比 Set 版本快了两倍。我跳过测试的其他优化包括缓存长度、使用 while 循环代替 for 循环，以及将增量器放在数字之前（++myJewelsvs myJewels++）。

第二个问题

345. 反转字符串的元音~编写一个函数，以字符串作为输入，并仅反转字符串的元音。

一个简单的解决方案可能是循环遍历数组两次，并在第二次循环时替换。我们先试试这个。

var reverseVowels = function(s) {
    const vowels = new Set(['a','e','i','o','u', 'A', 'E', 'I', 'O', 'U']);
    const reversed = [];
    let vowelsFound = [];
    // Find any vowels
    for (var i = 0; i < s.length; i++) {
        if (vowels.has(s[i])) {
            vowelsFound.push(s[i]);
        }   
    }
    // Build the final string
    for (var i = 0; i < s.length; i++) {
        if (vowels.has(s[i])) {
            reversed.push(vowelsFound.pop());
        } else {
            reversed.push(s[i]);
        }
    }
    return reversed.join('');
};

这样我们就得到了faster than 97.00%。运行时间是线性的O(2N) -> O(N)，而且读起来也不错，但我忍不住觉得我们循环了字符串的次数比实际需要的多。我们试试双指针方法。一步一步地从前面和后面同时进行，交换我们看到的任何元音字母。如果中间有一个元音字母，我们就把它留下。

var reverseVowels = function(s) {
    const vowels = new Set(['a','e','i','o','u', 'A', 'E', 'I', 'O', 'U']);
    s = s.split('');
    let front = 0;
    let back = s.length - 1;
    while (front < back) {
        if (!vowels.has(s[front])) {
            front++;
            continue;
        }
        if (!vowels.has(s[back])) {
            back--;
            continue;
        }
        let temp = s[front];
        s[front] = s[back];
        s[back] = temp;
        front++;
        back--;
    }
    return s.join('');
};

我们减少了一次完整的迭代！这让我们很头疼faster than 98.89%，此时我们需要记住，LeetCode 的基准测试既不具有结论性，也不一致。它们不可能用混合测试用例进行大量迭代。如果你正在练习解谜，请停止在97%及以上。但这不是本文的重点，读者们，我会帮100%你搞清楚的。

首先，我放弃了 Set。元音字母的数量是常数，我们不需要进行那么多哈希运算。我尝试了 switch 语句，但后来发现链式 if 语句更快。我发现内联这种逻辑比函数更快。然后我把它简化成了一个表达式。我想说的是：接下来的代码很恶心。它恶心到你关掉 IDE 就走人了。但是……它 faster than 100.00%……

var reverseVowels = function(s) {
    s = s.split('');
    let front = 0;
    let back = s.length - 1;
    while (front < back) {
        if (s[front] !== 'a' &&
            s[front] !== 'e' &&
            s[front] !== 'i' &&
            s[front] !== 'o' &&
            s[front] !== 'u' &&
            s[front] !== 'A' &&
            s[front] !== 'E' &&
            s[front] !== 'I' &&
            s[front] !== 'O' &&
            s[front] !== 'U') {
            front++;
            continue;
        }
        if (s[back] !== 'a' &&
            s[back] !== 'e' &&
            s[back] !== 'i' &&
            s[back] !== 'o' &&
            s[back] !== 'u' &&
            s[back] !== 'A' &&
            s[back] !== 'E' &&
            s[back] !== 'I' &&
            s[back] !== 'O' &&
            s[back] !== 'U') {
            back--;
            continue;
        }
        let temp = s[front];
        s[front++] = s[back];
        s[back--] = temp;
    }
    return s.join('');
};

（对不起）。

第三个问题

509. 斐波那契数~计算第 n 个斐波那契数。

这道题很常见，而且由于最终解法中变动的部分太少，所以最难改进运行时间。我敢肯定 LeetCode 的评分也涉及到一些随机数生成器 (RNG)。我们先把这个简单的解法解决掉吧。斐波那契数列常用于教授递归。然而，该算法的运行时间非常O(2^n)慢。

事实上，当我尝试用这个函数计算第 50 项时，浏览器标签崩溃了。

var fib = function(N) {
    if (N < 2) {
        return N;
    }
    return fib(N - 1) + fib(N - 2);
}

我们得到了faster than 36.63%这个答案。哎哟。在生产环境中，这类难题可以通过记忆化（缓存部分工作以供后续处理）来解决。这是最好的解决方案，因为我们只需在线性时间内计算所需的值O(N)，然后针对该限制内的项再次运行该算法，这只需要常数时间O(1)。

const memo = [0, 1];
var fib = function(N) {
    if (memo[N] !== undefined) {
        return memo[N];
    }
    const result = fib(N - 1) + fib(N - 2);
    memo[N] = result;
    return result
};

faster than 94.25%LeetCode 不会在每次运行代码之间存储数据，所以我们必须尝试不同的方法。我们只需要计算一次序列中的一个数字。我觉得我们可以放弃这个数组。我们来看看迭代解法。

var fib = function(N) {
    if (N < 2) {
        return N;
    }
    let a = 1;
    let b = 1;
    for (let i = 3; i <= N; ++i) {
        a = a + b;
        b = a - b;
    }
    return a;
};

如果这看起来与你可能见过的其他迭代版本略有不同，那是因为我避免了 JavaScript 中交换值时必须使用的第三个临时变量（虽然也有其他方法，但速度太慢）。我做了一些基准测试，发现使用算术运算……faster than 100.00%

与 150 多名订阅我的关于编程和个人成长的新闻通讯的人一起！

我发布有关科技的推文@healeycodes。

文章来源：https://dev.to/healeycodes/solving-puzzles-with-high-performance-javascript-3o4k