메모화된 래퍼 함수를 사용하여 자바스크립트에서 계산 시간 절약

메모화된 래퍼 함수를 사용하여 자바스크립트에서 계산 시간 절약

다른 모든 실행을 차단하는 무거운 처리로 이어지는 기능 때문에 실제로 프로그램을 계속 사용하려면 약 15초 정도 기다려야 한다고 상상해 보십시오.

Leetcode, Hackerrank, co와 같은 코드화 도전 웹사이트는 특정한 이유로 존재한다. 예를 들어, 피보나치 급수는 단일 값을 계산하는 데 엄청난 양이 소요될 수 있습니다. 재귀를 사용하여 중간 결과를 사용하는 경우 기존 결과를 반복적으로 다시 계산하지 말고 Big O 표기법을 염두에 두어야 합니다.

개발자로서, 특히 사용자로서 이는 용납할 수 없는 일이므로, 메모 기능을 사용하여 기능을 포장하는 더 나은 방법을 찾고 배워야 합니다.

참고: 예는 자바스크립트로 되어 있지만, 이 기술은 표시된 구조를 지원하는 모든 언어에 적용할 수 있습니다.

이지 피스 레몬 스퀴지

단일 인수(숫자)를 받고 n까지 원소의 합을 반환하는 피보나치 함수를 예로 들어 이 주제에 대해 설명하겠습니다.

이 함수 안에 캐시를 구현하여 결과를 훨씬 더 빠르게 계산할 수 있었던 방법을 보여드리고자 합니다.

팁: 높은 숫자에 대한 계산 시간을 테스트할 수 있습니다. 그러면 차이를 알 수 있습니다.아니면 계속 읽으면서 내 시험 좀 봐 :)

이 카치드피보나치는 제법 잘 나가지만 기능적 요건에는 맞지 않는다. 또한 코딩 원칙의 특정 법칙(글로벌 스페이스, 기존 코드 변경)을 위반한다.

캐치드피보나치는 개념적으로는 일반적이지만 구현에서는 특히 그렇다. 즉, 메모화를 이용하기 위해서만 함수의 코드를 직접 수정해야 했습니다.

하지만 우리는 더 잘 할 수 있다.

대신, 여러분은 일을 자동으로 끝내는 방법을 고려해야 합니다.

다른 포장된 기능들과 같은 방식으로요.

그러면 해답은 메모화를 적용하기 위해 다른 함수를 감싸는 memoize() 함수가 될 것이다.

이거 어떻게 작동해요?

반환된 함수는 지정된 인수에 대해 인수가 이미 수신되었는지 확인합니다. 배열 캐시 의 일부이며 적절한 키를 사용하여 찾을 수 있습니다.

그러면 계산이 필요하지 않고 캐시된 값이 반환됩니다.

그렇지 않으면 결측값을 계산하여 캐시에 저장해야 합니다.

캐시 는 외부 액세스로부터 캐시를 숨기기 위한 폐쇄의 일부이다. 메모화된 함수가 하나의 인수( x )만 수신하고 원시 값이라고 가정하여 여기서 닫기를 사용했습니다. 그런 다음 캐시 개체의 키 값으로 직접 사용할 수 있습니다.

타이머 테스트 시작

이 접근 방식이 제대로 작동하는지 확인하려면 이러한 기능의 시간을 재야 합니다. 다음 타이밍 기능을 사용하여 창작물을 확인합니다.

원래의 피보나치 함수부터 시작해보자. 각 재귀 호출이 아닌 전체 계산 시간을 재려고 보조 testFibonacci() 함수를 만들고 simpleFibonacci.j s 파일에서 원본 fibonacci() 를 테스트합니다.

팁: 이 연습은 실제 계산 시간을 얻기 위한 적절한 방법이 아니다. 평균 테스트가 적절할 것입니다. 하지만 저는 메모가 효과가 있는지 확인하고 싶습니다.

기계로 테스트를 반복하면 시간이 달라집니다. 특정 CPU, RAM 등에 따라 다릅니다.

하지만, 그 결과는 논리적으로 보인다: 기하급수적인 것이 존재하는 것처럼 보이고, 시간은 빠르게 성장한다.

이제 `testFibonacciMemoized()를 메모해 보겠습니다. 결과적으로 더 짧은 시간을 찾아야 하지 않겠어요?

시간을 보면 3호선과 4호선의 큰 변화를 볼 수 있을 거예요. 와! 2.7초에서 거의 0초까지… 멋져요! 근데 이건 뭐야?!

이전 번호(4-5행)를 사용하고 이전 번호로 돌아갑니다. 또한, 5호선부터 6호선까지의 전환도 마찬가지입니다.

testFibionacciMemoized() 시간을 지정했지만 코드가 해당 함수를 호출하지 않았습니다. 단 한 번만 발생하는 타이밍을 제외하고!

내부적으로 모든 재귀적 호출은 메모되지 않은 피보나치()에 대한 것입니다.

그래서 같은 번호로 더블 콜을 걸면 메모가 됩니다. 하지만 나머지는 아니야. 이것이 밀리초가 다시 늘어난 이유입니다. 올바른 결과를 얻으려면 코드를 다음과 같이 변경해야 합니다.

이 코드를 다르게 만드는 것은 피보나치 주변에 memoize()를 감고 그 안에 저장한다는 사실이다. 더 이상 addTiming 함수로만 호출되는 변수가 아니다. memoize() 를 성공적으로 포장했습니다.

즉, `fibonacci(42)를 계산할 때 모든 중간 피보나치 값(0 ~ 42)이 저장되므로 향후 호출은 실질적으로 계산할 노력이 없다. 그들은 값을 찾고, 그것이 엄청나게 낮은 계산 시간이 증명하는 것이다.

이제 메모화의 기본 사항을 이해했습니다. 더 복잡한 세계로 옮기자.

더 많은 논쟁, 더 재미있어요!

둘 이상의 파라미터를 수용하는 함수가 있을 경우 어떻게 해야 합니까? 배열이나 개체도 필요할 수 있다는 것은 상상도 할 수 없습니다.

이 기능에 대한 솔루션을 소개하기 전에, 단항 기능만 감싸고 나머지는 그대로 두는 기능으로 시작할 수 있습니다.

이렇게 하는 것은 if-표현식으로 함수의 .length 에 실제로 액세스하여 함수의 아리티를 확인하는 것을 의미한다.

단항 기능이 아닌 경우 실제로 메모 작업을 수행하지 않고 함수를 반환합니다.

함수를 메모하려면 캐시 키를 생성하는 방법을 찾아야 합니다. 다른 말로 하자면:

인수를 문자열로 변환하는 방법을 찾아야 합니다.

비기본 키를 캐시 키로 직접 사용할 수는 없습니다. 이 값을 str = String(x) 과 같은 문자열로 변환하려고 할 수 있지만 문제가 발생할 수 있습니다.

반면에, 어레이는 잘 작동하는 것 같습니다. 그렇지 않나요?

문자열() 기능은 언제나 정확하게 납작한 문자열을 만들어낸다. 중첩 배열은 문자열로만 변환됩니다. 그것은 우리가 원하는 메모화 행동에 좋지 않다. 다른 어레이에서 동일한 키를 생성하는 경우 문제가 발생합니다.

어떤 객체의 String() 표현은 변함없이 `[객체, 객체]의 명언이기 때문에 객체를 인수로 받아들여야 한다면 상황은 더 나빠진다.

당신은 무엇을 해야 합니까? 가장 간단한 해결책은 JSON.stringify() 를 사용하여 우리가 받은 모든 인수를 유용하고 구별되는 문자열로 변환하는 것이다.

더 나은 성능을 얻기만 하면 됩니다. 메모하려는 함수가 단일 인수를 수신하는 경우 기본 값입니다. 따라서 캐시 키로 직접 사용할 수 있습니다.

다른 모든 경우에는 인수 배열에 적용되는 JSON.stringify() 결과를 사용해야 합니다.

이러한 구별에 따라 메모화 고차 함수의 정제된 버전으로 이어진다.

이것은 보편성 측면에서 가장 안전한 버전이다.

함수의 파라미터 유형을 확실히 알 때마다 첫 번째 메모 기능이 더 빠릅니다.

여러분의 희망에 따라, 여러분은 훨씬 간단하고, 따라서 여러분의 눈에는 훨씬 더 나은 코드를 갖고 싶을 수도 있습니다. 그런 다음 이 버전의 보다 간단하고 보편적인 메모라이징 기능을 사용합니다.

팁: 이번에는 CPU 사이클이 몇 번 낭비되어 코드 비용이 더 간단해집니다. Ciao Gondim은 세계에서 가장 빠른 메모 작성 라이브러리를 작성한다. JSON 때부터.Stringify()는 성능이 좋지 않습니다. 여기서 가장 빠른 방법을 확인할 수 있습니다.

지금은 충분히 메모하셨으면 합니다. 이 부분은 끝났습니다.

남은 것은 시험이다. 메모화 고차 함수를 테스트하는 것은 흥미로운 문제를 제기합니다. 어떻게 하시겠습니까?

메모라이제이션 테스트

좋은 생각 없어요? 아니야?

좋아, 그럼 내가 먼저 할게. 캐시를 조사하는 것도 한 가지 방법이 될 수 있어. 하지만 이건 사적인 거야. 글로벌 캐시를 사용하는 함수를 다시 쓰는 것도 유효한 옵션이 아닙니다.

좀 더 직접적인 분석 방법을 생각해 보셨습니까? 실제 통화 건수를 세는 것처럼요?

따라서 비암기화된 원본 피보나치() 를 사용하여 함수가 일반적으로 작동하는지 테스트하고 호출을 확인할 수 있습니다.

별거 없어요. 원래의 피보나치() 함수를 확인하고 호출과 생성된 값을 테스트하기만 하면 됩니다. 피보나치(6)가 8이라는 사실을 알면 쉽게 확인할 수 있다.

그런데 이 함수가 25배라는 것을 어떻게 알 수 있을까.

정답은 fibonacci(6) 를 계산하는 데 필요한 모든 재귀 호출에 대한 그래프를 참조하십시오.

각 노드는 기능에 대한 호출을 나타냅니다. 계산해 보면 피보나치(6)를 계산하기 위해 25로 전화를 걸었다는 것을 알 수 있다.

이제 메모된 기능 버전으로 이동하여 동일한 결과를 생성하는지 테스트해 보겠습니다.

이처럼 피보나치(6)를 계산하면 11배, 피보나치(5)와 피보나치(3)를 계산하면 3배(14의 합)밖에 안 되는 이유를 짐작할 수 있겠는가.

이 질문의 첫번째 부분에 답하려면,)LaunchSchool을 통해 도표(그림 피보나치(6)을 분석한, 왼쪽 가지 가자.

이 질문의 두 번째 부분에 대한 답변: 피보나치(n)에서 피보나치(6)로 이전 값을 모두 캐싱했으므로 피보나치(5)를 피보나치(4)와 피보나치(3)를 이렇게 계산하면 3개의 통화(실제로 각 통화당 1개씩)만 추가되는 이유를 쉽게 알 수 있다.

다른 모든 필수 값은 이미 계산되어 캐시되어 있습니다.

결론

여러분은 이미 존재하는 기능을 메모하기 위해 실제로 여러 포장 기능을 처리하는 방법에 대해 배웠습니다.

기능의 우수성은 중요하지 않습니다. 이제 적절한 솔루션을 마련하는 데 필요한 모든 도구를 확보했습니다.

주요 목표는 이미 존재하는 코드와 작업 코드를 건드리지 않음으로써 응용 프로그램을 계속 확장하는 것입니다.

그러나 함수의 작동 방식을 실제로 변경하려는 경우는 다릅니다. 하지만 그것은 다음 기사에 대한 이야기입니다.

참고문헌

from http://sup-poster.tistory.com/6 by ccl(A) rewrite - 2021-09-18 16:00:42