[javascript] 문자열 반복-Javascript

이 문제는 JavaScript 문자열이 “불변”하고 단일 문자를 문자열에 연결하여 추가하기 위해 메모리 할당 및 복사를 포함하여 생성해야한다는 사실로 인해 JavaScript에 대해 잘 알려진 “고전적인”최적화 문제입니다. 완전히 새로운 문자열입니다.

불행히도이 페이지에서 허용되는 답변은 틀 렸습니다. 여기서 “잘못된”은 간단한 1 문자 문자열의 경우 3 배, 짧은 문자열의 경우 8x-97x, 여러 번 반복되는 문장의 경우 300x, 반복되는 문장의 경우 300x, 무한히 잘못된 경우 알고리즘의 복잡성 비율의 한계를 n 무한대 진행 합니다. 또한이 페이지에는 거의 올바른 대답이 있습니다 (지난 13 년 동안 인터넷을 통해 순환하는 올바른 솔루션의 많은 세대와 변형 중 하나를 기반으로 함). 그러나이 “가장 올바른”솔루션은 50 %의 성능 저하를 야기하는 올바른 알고리즘의 핵심 사항을 놓치고 있습니다.

허용 된 답변, 최고 성능의 다른 답변 (이 답변의 원래 알고리즘의 저하 된 버전을 기반으로 함) 및 13 년 전에 만든 내 알고리즘을 사용한이 답변에 대한 JS 성능 결과

~ 2000 년 10 월 나는이 정확한 문제에 대한 알고리즘을 발표했다.이 정확한 문제는 광범위하게 조정되고, 수정 된 다음, 이해하기 어려워졌다. 이 문제를 해결하기 위해 2008 년 8 월에 http://www.webreference.com/programming/javascript/jkm3/3.html 기사를 게시 하여 알고리즘을 설명하고 일반적인 JavaScript 최적화의 간단한 예로 사용했습니다. 지금까지 Web Reference 는이 기사에서 내 연락처 정보와 내 이름을 제거했습니다. 그리고 다시 한 번,이 알고리즘은 광범위하게 조정, 수정 된 후 이해력이 떨어지고 잊혀졌습니다.

Text.js 내의 텍스트 곱셈 함수로서 Y2K 경에 Joseph Myers의 원래 문자열 반복 / 곱셈 JavaScript 알고리즘; 2008 년 8 월 웹 참조에 의해이 형식으로 출판 :
http://www.webreference.com/programming/javascript/jkm3/3.html (이 기사는이 기능을 JavaScript 최적화의 예로 사용했습니다. “stringFill3″이름)

/*
 * Usage: stringFill3("abc", 2) == "abcabc"
 */

function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

이 기사를 게시 한 후 2 개월 이내에이 같은 질문이 Stack Overflow에 게시되어 지금까지 내 레이더 아래로 날아갔습니다.이 문제에 대한 원래 알고리즘이 다시 한번 잊혀졌습니다. 이 Stack Overflow 페이지에서 사용 가능한 최상의 솔루션은 수정 된 버전의 솔루션으로, 여러 세대로 분리되어있을 수 있습니다. 불행히도 수정으로 솔루션의 최적 성이 손상되었습니다. 사실, 루프의 구조를 원래의 것에서 변경함으로써 수정 된 솔루션은 완전히 불필요한 불필요한 지수 복제 단계를 수행합니다 (따라서 정답에 사용 된 가장 큰 문자열을 자체적으로 추가 시간으로 결합 한 다음 버림).

아래는이 문제에 대한 모든 답변과 모든 사람의 이익을위한 일부 JavaScript 최적화에 대한 설명입니다.

기술 : 객체 또는 객체 속성에 대한 참조를 피하십시오

이 기법의 작동 방식을 설명하기 위해 필요한 길이의 문자열을 생성하는 실제 JavaScript 함수를 사용합니다. 앞으로 살펴 보 겠지만 더 많은 최적화를 추가 할 수 있습니다!

여기에 사용 된 것과 같은 기능은 텍스트 열을 정렬하거나 돈을 형식화하거나 블록 데이터를 경계까지 채우는 패딩을 만드는 것입니다. 텍스트 생성 기능은 텍스트에서 작동하는 다른 기능을 테스트하기 위해 가변 길이 입력을 허용합니다. 이 함수는 JavaScript 텍스트 처리 모듈의 중요한 구성 요소 중 하나입니다.

계속 진행하면서, 가장 중요한 최적화 기법 중 두 가지를 더 다루면서 원본 코드를 문자열 생성을위한 최적화 된 알고리즘으로 개발할 것입니다. 최종 결과는 JavaScript 주문 양식, 데이터 형식 및 전자 메일 / 문자 메시지 형식 및 기타 여러 용도로 항목 가격과 총계를 정렬하여 모든 곳에서 사용했던 강력한 산업용 고성능 기능입니다.

문자열을 만들기위한 원본 코드 stringFill1()

function stringFill1(x, n) {
    var s = '';
    while (s.length < n) s += x;
    return s;
}
/* Example of output: stringFill1('x', 3) == 'xxx' */ 

구문은 명확합니다. 보시다시피, 우리는 더 많은 최적화를 진행하기 전에 이미 지역 함수 변수를 사용했습니다.

s.length코드에서 성능을 저하 시키는 객체 속성 에 대한 하나의 무고한 참조가 있음에 유의하십시오 . 더 나쁜 것은이 객체 속성을 사용하면 독자가 JavaScript 문자열 객체의 속성에 대해 알고 있다고 가정함으로써 프로그램의 단순성을 줄입니다.

이 개체 속성을 사용하면 컴퓨터 프로그램의 일반성이 손상됩니다. 프로그램은 x길이가 1 인 문자열이어야 한다고 가정 합니다. 이것은 stringFill1()단일 문자의 반복을 제외한 모든 것에 대한 기능 적용을 제한합니다 . HTML 엔터티와 같이 여러 바이트가 포함 된 단일 문자도 사용할 수 없습니다  .

이 불필요한 객체 속성 사용으로 인한 최악의 문제는 빈 입력 문자열에서 테스트하면 함수가 무한 루프를 생성한다는 것입니다 x 입니다. 일반성을 확인하려면 가능한 가장 적은 양의 입력에 프로그램을 적용하십시오. 사용 가능한 메모리 양을 초과하라는 메시지가 표시되면 프로그램이 중단됩니다. 아무것도 생성하지 않을 때 충돌하는 이와 같은 프로그램은 허용되지 않습니다. 때때로 예쁜 코드는 유독 한 코드입니다.

단순성은 컴퓨터 프로그래밍의 모호한 목표 일 수 있지만 일반적으로 그렇지 않습니다. 프로그램에 합리적인 수준의 일반성이 없으면 “프로그램이 진행되는 한 충분합니다.”라고 말하는 것은 유효하지 않습니다. 보시 string.length다시피이 속성을 사용하면이 프로그램이 일반 설정에서 작동하지 않으며 실제로 잘못된 프로그램이 브라우저 나 시스템 충돌을 일으킬 수 있습니다.

이 JavaScript의 성능을 향상시키고이 두 가지 심각한 문제를 처리 할 수있는 방법이 있습니까?

물론이야. 정수만 사용하십시오.

문자열 생성을위한 최적화 된 코드 stringFill2()

function stringFill2(x, n) {
    var s = '';
    while (n-- > 0) s += x;
    return s;
} 

코드를 타이밍하는 것은 비교하기 stringFill1()및stringFill2()

function testFill(functionToBeTested, outputSize) {
    var i = 0, t0 = new Date();
    do {
        functionToBeTested('x', outputSize);
        t = new Date() - t0;
        i++;
    } while (t < 2000);
    return t/i/1000;
}
seconds1 = testFill(stringFill1, 100);
seconds2 = testFill(stringFill2, 100); 

지금까지의 성공 stringFill2()

stringFill1()100 바이트 문자열을 채우려면 47.297 마이크로 초 (백만 분의 1 초)가 stringFill2()걸리고 같은 작업을 수행하려면 27.68 마이크로 초가 걸립니다. 객체 속성에 대한 참조를 피함으로써 성능이 거의 두 배가됩니다.

기술 : 긴 문자열에 짧은 문자열을 추가하지 마십시오

우리의 이전 결과는 실제로 매우 좋았습니다. 개선 된 기능 stringFill2()은 처음 두 가지 최적화를 사용하기 때문에 훨씬 빠릅니다. 지금보다 몇 배나 더 빨리 개선 될 수 있다고 말하면 믿을 수 있습니까?

우리는 그 목표를 달성 할 수 있습니다. 지금은 긴 문자열에 짧은 문자열을 추가하지 않는 방법을 설명해야합니다.

단기적인 행동은 원래의 기능과 비교할 때 상당히 좋은 것으로 보입니다. 컴퓨터 과학자들은 함수 또는 컴퓨터 프로그램 알고리즘의 “점근 적 행동”을 분석하는 것을 좋아하는데, 이는 더 큰 입력으로 테스트하여 장기적인 행동을 연구하는 것을 의미합니다. 때때로 추가 테스트를 수행하지 않으면 컴퓨터 프로그램을 개선 할 수있는 방법을 결코 알지 못합니다. 어떤 일이 발생하는지 확인하기 위해 200 바이트 문자열을 만들 것입니다.

와 함께 나타나는 문제 stringFill2()

타이밍 함수를 사용하면 200 바이트 문자열의 경우 시간이 100 바이트 문자열의 27.68에 비해 62.54 마이크로 초로 증가합니다. 두 배나 많은 작업을 수행하려면 시간을 두 배로 늘려야하는 것처럼 보이지만 세 배나 네 배로 늘어납니다. 프로그래밍 경험에서 볼 때이 결과는 이상하게 보입니다. 어떤 것이라도 작업이보다 효율적으로 수행되기 때문에 함수가 약간 더 빨라야하기 때문입니다 (함수 호출 당 100 바이트가 아니라 함수 호출 당 200 바이트). 이 문제는 JavaScript 문자열의 교활한 속성과 관련이 있습니다. JavaScript 문자열은 “불변”입니다.

불변은 문자열을 만든 후에는 변경할 수 없음을 의미합니다. 한 번에 하나의 바이트를 추가함으로써 하나의 바이트 노력을 더 이상 사용하지 않습니다. 우리는 실제로 전체 문자열과 하나 이상의 바이트를 다시 만들고 있습니다.

실제로 100 바이트 문자열에 1 바이트를 더 추가하려면 101 바이트의 작업이 필요합니다. N바이트 문자열을 만들기위한 계산 비용을 간단히 분석해 봅시다 . 첫 번째 바이트를 추가하는 비용은 1 단위의 계산 노력입니다. 두 번째 바이트를 추가하는 비용은 한 단위가 아니라 2 단위입니다 (두 번째 바이트를 추가 할뿐만 아니라 첫 번째 바이트를 새 문자열 객체에 복사). 세 번째 바이트는 3 단위의 비용이 필요합니다.

C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). 이 기호 O(N^2)는 Big O of N squared로 발음되며 장기적으로 계산 비용이 문자열 길이의 제곱에 비례한다는 것을 의미합니다. 100자를 만들려면 10,000 단위의 작업이 필요하고 200자를 만들려면 40,000 단위의 작업이 필요합니다.

이것이 100 자보다 200자를 만드는 데 두 배 이상 걸린 이유입니다. 실제로 4 배나 오래 걸렸습니다. 우리의 프로그래밍 경험은 더 긴 문자열을 위해 작업이 약간 더 효율적으로 수행되고 있다는 점에서 정확하므로 약 3 배의 시간이 걸렸습니다. 함수 호출의 오버 헤드가 생성하는 문자열의 길이에 대해 무시할 수있게되면 실제로 문자열을 두 배로 만드는 데 4 배의 시간이 걸립니다.

(역사적 주 : html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n'JavaScript 소스 코드 컴파일러는 문자열을 JavaScript 문자열 객체로 만들기 전에 함께 결합 할 수 있기 때문에 소스 코드의 문자열에는이 분석이 반드시 적용되는 것은 아닙니다 . 불과 몇 년 전 KJS 구현은 더하기 부호로 결합 된 긴 소스 코드 문자열을로드 할 때 JavaScript가 중단되거나 중단되는 경우 계산 시간이 O(N^2)지나서 Konqueror 웹 브라우저 또는 KJS JavaScript 엔진 코어를 사용하는 Safari에 과부하가 걸리는 웹 페이지를 만드는 것은 어렵지 않았습니다. 마크 업 언어 및 JavaScript 마크 업 언어 파서를 개발할 때이 문제가 발생했으며 JavaScript Includes 용 스크립트를 작성할 때 문제의 원인을 발견했습니다.)

이처럼 빠른 성능 저하는 큰 문제입니다. JavaScript를 사용하여 문자열을 변경 불가능한 객체로 처리하는 방법을 변경할 수 없다면 어떻게 처리 할 수 ​​있습니까? 해결책은 문자열을 가능한 한 몇 번 재생성하는 알고리즘을 사용하는 것입니다.

명확히하기 위해, 우리의 목표는 짧은 문자열을 긴 문자열에 추가하는 것을 피하는 것입니다. 짧은 문자열을 추가하려면 전체 긴 문자열도 복제해야하기 때문입니다.

긴 문자열에 짧은 문자열을 추가하지 않도록 알고리즘이 작동하는 방식

새로운 문자열 객체가 생성되는 횟수를 줄이는 좋은 방법이 있습니다. 한 번에 둘 이상의 바이트가 출력에 추가되도록 더 긴 길이의 문자열을 함께 연결하십시오.

예를 들어, 길이가 문자열 인 경우 N = 9:

x = 'x';
s = '';
s += x; /* Now s = 'x' */
x += x; /* Now x = 'xx' */
x += x; /* Now x = 'xxxx' */
x += x; /* Now x = 'xxxxxxxx' */
s += x; /* Now s = 'xxxxxxxxx' as desired */

이렇게하려면 길이가 1 인 문자열을 만들고 길이가 2 인 문자열을 만들고 길이가 4 인 문자열을 만들고 길이가 8 인 문자열을 만들고 마지막으로 길이가 9 인 문자열을 만들어야했습니다. 비용은 얼마입니까?

이전 비용 C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.

새로운 비용 C(9) = 1 + 2 + 4 + 8 + 9 = 24.

길이 1의 문자열을 길이 0의 문자열에 추가 한 다음 길이 1의 문자열을 길이 1의 문자열에 추가 한 다음 길이 2의 문자열을 길이 2의 문자열, 길이 4의 문자열을 추가해야합니다. 길이가 9 인 문자열을 얻기 위해 길이가 4 인 문자열, 길이가 8 인 문자열, 길이가 1 인 문자열을 비교합니다. 우리가하고있는 일은 긴 문자열에 짧은 문자열을 추가하지 않는 것으로 요약 할 수 있습니다. 길이가 같거나 거의 같은 문자열을 함께 연결하려고합니다.

이전 계산 비용으로 우리는 공식을 찾았습니다 N(N+1)/2. 새로운 비용에 대한 공식이 있습니까? 예,하지만 복잡합니다. 중요한 것은 O(N)문자열 길이를 두 배로 늘리면 작업량을 네 배로 늘리지 않고 작업량을 약 두 배로 늘릴 수 있다는 것입니다 .

이 새로운 아이디어를 구현하는 코드는 계산 비용에 대한 공식만큼이나 복잡합니다. 읽을 때 >>= 11 바이트 씩 오른쪽으로 이동 한다는 것을 기억하십시오 . 따라서 n = 10011이진수 n >>= 1이면 값이 n = 1001됩니다.

인식하지 못하는 코드의 다른 부분은 비트 단위 및 연산자입니다 &. 식은 n & 1마지막 이진수 n가 1 이면 true를 평가 하고 마지막 이진수 n가 0이면 false를 평가합니다 .

새로운 고효율 stringFill3()기능

function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
} 

훈련받지 않은 눈에는보기에 좋지 않지만 성능은 그저 사랑 스럽습니다.

이 기능이 얼마나 잘 수행되는지 봅시다. 결과를 본 후에는 O(N^2)알고리즘과 알고리즘 의 차이점을 잊지 못할 것 O(N)입니다.

stringFill1()200 바이트 문자열을 만드는 데 88.7 마이크로 초 (백만 분의 1 초)가 stringFill2()걸리고 62.54가 걸리며 4.608 stringFill3()만 걸립니다. 이 알고리즘이 훨씬 더 나은 이유는 무엇입니까? 모든 함수는 로컬 함수 변수를 사용하는 이점을 얻었지만 두 번째 및 세 번째 최적화 기술을 활용하면의 성능이 20 배 향상되었습니다 stringFill3().

심층 분석

이 특별한 기능이 물에서 경쟁을 불러 일으키는 이유

앞에서 언급했듯이이 두 함수 stringFill1()와 stringFill2()가 느리게 실행 되는 이유 는 JavaScript 문자열을 변경할 수 없기 때문입니다. JavaScript로 저장된 문자열 데이터에 한 번에 하나 이상의 바이트를 추가 할 수 있도록 메모리를 재 할당 할 수 없습니다. 하나의 바이트가 문자열의 끝에 추가 될 때마다 전체 문자열이 처음부터 끝까지 재생성됩니다.

따라서 스크립트의 성능을 향상 시키려면 두 개의 문자열을 미리 연결 한 다음 원하는 문자열 길이를 재귀 적으로 작성하여 더 긴 문자열을 미리 계산해야합니다.

예를 들어 16 자 바이트 문자열을 만들려면 먼저 2 바이트 문자열이 미리 계산됩니다. 그런 다음 2 바이트 문자열을 다시 사용하여 4 바이트 문자열을 사전 계산합니다. 그런 다음 4 바이트 문자열을 다시 사용하여 8 바이트 문자열을 사전 계산합니다. 마지막으로, 2 바이트의 8 바이트 문자열을 재사용하여 원하는 새 16 바이트 문자열을 작성합니다. 전체 길이는 2 + 4 + 8 + 16 = 30입니다. 총 길이는 2 + 4 + 8 + 16 = 30입니다.

장기적으로이 효율성은 역순으로 추가하고 첫 번째 항 a1 = N으로 시작하고 r = 1/2의 공통 비율을 갖는 기하 계열을 사용하여 계산할 수 있습니다. 기하 계열의 합은로 주어집니다 a_1 / (1-r) = 2N.

16 자까지 길이가 3, 4, 5 등인 새 문자열을 작성하기 위해 문자 하나를 추가하여 길이 2의 새 문자열을 작성하는 것보다 효율적입니다. 이전 알고리즘은 한 번에 단일 바이트를 추가하는 프로세스를 사용했습니다. 총 비용은입니다 n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.

분명히 136은 30보다 훨씬 많으므로 이전 알고리즘은 문자열을 작성하는 데 훨씬 더 많은 시간이 걸립니다.

두 방법을 비교하기 위해 재귀 알고리즘 ( “분할 및 정복”이라고도 함)이 길이가 123,457 인 문자열의 속도가 훨씬 빠릅니다. 내 FreeBSD 컴퓨터에서 stringFill3()함수에 구현 된이 알고리즘 은 0.001058 초 안에 문자열을 생성하는 반면, 원래 stringFill1()함수는 0.0808 초 안에 문자열을 생성합니다. 새로운 기능은 76 배 더 빠릅니다.

줄 길이가 길어질수록 성능 차이가 커집니다. 더 크고 더 큰 문자열이 만들어 질 때의 한계에서 원래 함수는 C1(일정한) 시간 과 거의 비슷하게 작동 N^2하고 새 함수는 C2(일정한) 시간 과 같이 작동 N합니다.

우리의 실험에서 우리는의 가치를 결정할 수 C1있을하는 C1 = 0.0808 / (123457)2 = .00000000000530126997, 그리고 값 C2이 될을 C2 = 0.001058 / 123457 = .00000000856978543136. 10 초 안에 새 함수는 1,166,890,359자를 포함하는 문자열을 만들 수 있습니다. 동일한 문자열을 만들려면 이전 함수에 7,218,384 초의 시간이 필요합니다.

이것은 10 초에 비해 거의 3 개월입니다!

이 문제에 대한 나의 원래의 해결책이 인터넷에 10 년 넘게 떠 올랐고, 아직도 그것을 기억하는 소수의 사람들은 여전히 ​​잘 이해하지 못했기 때문에 나는 (몇 년 늦게) 대답하고 있습니다. 여기에 기사를 쓰면 도움이 될 것이라고 생각했습니다.

고속 JavaScript를위한 성능 최적화 / 3 페이지

불행히도, 여기에 제시된 다른 솔루션 중 일부는 여전히 적절한 솔루션이 10 초 안에 생성하는 동일한 양의 출력을 생성하는 데 3 개월이 걸리는 솔루션 중 일부입니다.

여기에서 기사의 일부를 스택 오버플로에 대한 정식 답변으로 재현하는 데 시간을 갖고 싶습니다.

여기서 최고의 성능을내는 알고리즘은 내 알고리즘을 기반으로하며 다른 사람의 3 세대 또는 4 세대 적응에서 상속되었을 수 있습니다. 불행히도 수정으로 인해 성능이 저하되었습니다. 여기에 제시된 솔루션의 변형은 아마도 for (;;)C로 작성된 서버의 주요 무한 루프처럼 보이고 혼란스러운 표현을 이해하지 못했을 것 입니다. 불필요한 불필요한 시간을 문자열로 기하 급수적으로 복제하지 마십시오.

답변

String.prototype.repeat = function(times){
    var result="";
    var pattern=this;
    while (times > 0) {
        if (times&1)
            result+=pattern;
        times>>=1;
        pattern+=pattern;
    }
    return result;
};

"yo".repeat(2);
// returns: "yoyo"

'abc'.repeat(3); //abcabcabc

String.prototype.repeat = function(num) {
    return new Array(isNaN(num)? 1 : ++num).join(this);
    }

var foo = 'bar';
alert(foo.repeat(3));              // Will work, "barbarbar"
alert(foo.repeat('3'));            // Same as above
alert(foo.repeat(true));           // Same as foo.repeat(1)

alert(foo.repeat(0));              // This and all the following return an empty
alert(foo.repeat(false));          // string while not causing an exception
alert(foo.repeat(null));
alert(foo.repeat(undefined));
alert(foo.repeat({}));             // Object
alert(foo.repeat(function () {})); // Function