高性能JavaScriptでパズルを解く

未熟な最適化は、すべての悪の根源です.また、この記事のルートです.
私はプログラミングのパズルが好きです.私も速く行きたい.私たちはいくつかのLeetCode問題を取り、数回それらを解決しようとしています.我々は、これらの素晴らしい言葉の後です:

faster than 100.00% of JavaScript online submissions

我々がtartingしている環境はnodejs 10.15.0 with --harmony ( source ). オンライン裁判官システムは、私が言うことができる限り、テストケースのための比較的小さな入力を使用します.

最初の問題
771. Jewels and Stones ~ あなたは文字列を与えているJ 宝石である石の種類を表すことS あなたが持っている石を表す.各文字S あなたが持っている石の種類です.あなたは宝石がどれだけ多くの宝石を知ってほしい.
ここの奇朴な解決策は、石を通してループすることです.一般的に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;
};

ランタイムは2次です.O(N^2) . 彼らのオンライン裁判官は、実際にこの解決を受け入れません!我々は大きな脂肪時間制限を超えて取得します.レッスン?ループの入れ子は可能な場合は避けるべきです.
AをつかみましょうSet ループのいずれかを取り除く.ランタイムをリニアに下げるO(N) . JavaScriptのセットを調べるのは一定の時間です.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) しかし、我々は最適化を行うことができます.
石や宝石は、文字として定義されます.So a-z and A-Z . これは、我々の価値が落ちることができるだけで52種類のバケツがあることを意味!セットの代わりにブール配列を使用できます.アルファベット文字を数字に変換するには、ASCIIコードポイントをcharCodeAt . インデックスを設定しますtrue 宝石を表す.
しかし、JavaScriptにはboolean配列がありません.標準の配列を使用し、それを長さに初期化できます52 . または、私たちはInt8Array コンパイラが追加の最適化を行うことができます.入力された配列は0-52 としてJ and S .
あなたは、我々の長さが間違っている点を見つけましたか?これは私がテストしていたとき忘れていたものです.文字は7文字あるz and A ASCIIコードチャートでは、必要な長さは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;
};

ET voila、我々の100% fastest submission . 私のテストでは、これは実際に設定されたバージョンの2倍速くなった.テストをスキップした他の最適化は、forループの代わりにwhileループを使って長さをキャッシュし、数値の前にインクリメンタを置くことでした++myJewels 対myJewels++ ).

第二の問題
345. Reverse Vowels of a String ~ 文字列を入力とし、文字列の母音だけを逆にする関数を書き込みます.
これのためのナイーブな解決は2回目のループに取り替えて、配列を二回ループさせるかもしれません.まず試してみましょう.

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) , そして、それはよく読みます、しかし、私は我々が我々がそうしなければならないより1つのより多くの時間をループしていると思うのを助けることができません.つのポインタアプローチを試みましょう.歩いて、ステップバイステップでは、前面から戻って、同じ時間で、我々が見る任意の母音を交換.中間母音があるならば、我々はちょうどそれを残します.

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% あなたに.
まずセットを投げ出した.母音の数は一定です、そして、我々は続けているすべてのハントを必要としません.私はswitch文を試みました、そして、次に、chif if文がより速くなったとわかりました.私は、この論理が機能より速いことを発見しました.私は、それを表現に下げました.私が言っているものは、以下の通りです.それは、空いているダウンして、理想的で、歩くことです.しかしit's 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. Fibonacci Number ~ n番目のfibonacci数を計算します.
これは一般的なパズルです、そして、最終的な解決で非常に少ない可動部分があるので、それはランタイムを改善するのが最も困難でした.私はいくつかのRNGはleetcodeの等級にも関係していたはずです.naive解決方法を得ましょう.Fibonacciシーケンスはしばしば再帰を教えるために使用されます.ただし、使用されるアルゴリズムはO(2^n) (非常に遅い).
私は実際にこの関数で50番目の用語を計算しようとするとブラウザのタブをクラッシュさせました.

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

我々は得るfaster than 36.63% この答えに.ポーチ.生産では、これはmemoization(後の仕事のいくつかのキャッシュ)で解決することができるパズルの一種です.これは、我々が線形時間で必要とする値だけを計算するので、これは最適解です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は私たちのコードの各実行間のデータを格納しないので、何か違うことを試してみる必要があります.我々は一度だけシーケンスの1つの数を計算することに興味を持っている.私は、我々がその配列を捨てることができると思います.反復解法を見てみましょう.

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で値を交換するために我々が使わなければならない3番目の一時的な変数を避けました.ベンチマークをして、代わりに算術を使ったwas .. faster than 100.00% .
参加150 +人々は私にサインアップnewsletter プログラミングと個人の成長に!
私は技術についてつぶやきます.