고성능 JavaScript를 사용한 문제 해결

너무 일찍 최적화하는 것은 만악의 근원이다.이것도 본문의 근본이다.
나는 프로그래밍 난제를 좋아한다.나도 빨리 뛰는 것을 좋아한다.우리는 일부 LeetCode 문제를 처리하고 여러 번 해결하여 먼저 큰 범위 내에서 운행할 때의 복잡성을 높인 다음에 비교적 작은 최적화를 찾을 것이다.우리는 이런 아름다운 말들을 찾고 있다.

faster than 100.00% of JavaScript online submissions

Dell은 nodejs 10.15.0 및 --harmonysource를 대상으로 합니다.내가 알기로는 온라인 법관 시스템은 테스트 사례에 대해 상대적으로 작은 입력을 사용한다.

첫번째 문제

771. Jewels and Stones~보석의 유형을 나타내는 문자열J과 당신이 가지고 있는 보석을 나타내는 문자열S을 얻었습니다.S의 모든 문자는 돌의 일종이다.보석도 보석인지 알고 싶어요.
하나의 간단한 해결 방안은 우리의 보석에서 순환하고, 모든 보석에서 순환하는 것이다.이 문서에서, 우리는 자바스크립트에서 데이터를 교체하는 가장 빠른 방식이기 때문에, 표준for 순환을 사용할 것이다.

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).그들의 온라인 법관은 사실상 이 해결 방안을 받아들이지 않을 것이다.우리는 큰 시간 제한을 초과했다.교훈가능한 한 포괄 순환을 피하십시오.
그 중의 순환을 없애기 위해 하나 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). 그러나 우리는 최적화를 할 수 있다.
보석과 보석은 자모로 정의된다.그래서 a-z와A-Z.이것은 우리의 가치관이 52개의 다른 영역으로 나눌 수 있다는 것을 의미한다.우리는 집합을 볼 수 있는 그룹으로 대체할 수 있다.문자를 숫자로 변환하려면 ASCII 코드점 viacharCodeAt를 사용합니다.우리는 보석을 표시하기 위해 색인을 true로 설정할 것이다.
그러나 JavaScript에는 부울 배열이 없습니다.우리는 표준 그룹을 사용해서 길이52로 초기화할 수 있다.또는 우리는 Int8Array를 사용하고 컴파일러가 추가 최적화를 할 수 있도록 허용할 수 있다.입력0-52과 J의 무작위 문자 범위S를 사용하여 기준 테스트를 진행할 때 유형화 수조의 속도가 약 6% 높아졌다.
너는 우리의 길이가 틀린 것을 발견했니?이것은 내가 테스트할 때 잊어버린 것이다.ASCII 코드 차트에는 z와A 사이에 있는 7개의 문자가 있으므로 필요한 길이는 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% fastestsubmission.내 테스트에서, 이것은 실제로는 Set 버전의 두 배이다.테스트의 다른 최적화는 캐시 길이입니다. for 순환이 아니라while 순환을 사용하고incrementor를 숫자 앞에 두십시오 (++myJewels vs myJewels++.

두 번째 문제.

345. Reverse Vowels of a String~문자열을 입력으로 하고 문자열의 모음만 반전시키는 함수를 작성합니다.
간단한 해결 방안은 수조에서 두 번 순환하고 두 번째 순환에서 바뀔 수 있다.일단 해보자.

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%하게 했다. 이 점에서 리코드의 기준은 결정적이지도 일치하지도 않는다는 것을 기억해야 한다.그들에게 있어서 혼합된 테스트 용례로 대량의 교체를 운행하는 것은 불가능하다.만약 네가 수수께끼 풀이를 연습하고 있다면, 97% 위에 멈춰라.그러나 이것은 본문의 중점이 아닙니다. 독자 여러분, 저는 당신들에게 제공할 것입니다. 100%일단 세트는 버렸어요.모음의 수량은 일정하기 때문에 우리는 모든 해시 연산을 진행할 필요가 없다.나는 switch 문장을 시도했지만, 나중에 링크if 문장이 더 빠르다는 것을 발견했다.나는 이런 논리가 함수보다 더 빠르다는 것을 발견했다.그리고 나는 그것을 표현식으로 간소화했다.다음 코드는 징그럽다.그야말로'너의 IDE와 토크-a-walk에게 다가가다'.하지만.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번째 피보나 계수를 계산한다.
최종 해결 방안에 운동 부품이 너무 적기 때문에, 이것은 흔히 볼 수 있는 난제이다.몇몇 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% . LetCode는 코드가 실행될 때마다 데이터를 저장하지 않기 때문에 다른 방법을 시도해야 합니다.우리가 흥미를 느끼는 것은 단지 한 번의 서열 중의 한 수를 계산하는 것이다.나는 우리가 그 진열을 버릴 수 있다고 생각한다.교체해를 봅시다.

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;
};

만약 이것이 당신이 볼 수 있는 다른 교체 버전과 약간 다르게 보인다면, 그것은 자바스크립트에서 세 번째 임시 변수를 사용하여 값을 교환하는 것을 피했기 때문입니다. (다른 방법도 있지만 속도가 너무 느립니다.)나는 몇 가지 기준 테스트를 했는데 산술was을 사용하는 것을 발견했다.faster than 100.00% .
150여 명을 가입하여 저의 newsletter 프로그램과 개인 성장을 등록하세요!
나는 트위터에서 과학 기술에 대해 이야기했다.