다행히도, 당신은 재미있게 놀았기를 바랍니다. 챌린지 4 . 앞으로도 좋은 챌린지가 될 수 있는 아이디어가 있다면 알려주세요. 항상 좋은 자료 잘 보고 있습니다!
축하해요, @랜든 !귀하는 100쌍의 1,000자리(9.88초) 및 가장 긴 자리(7,150) 챌린지 모두에서 가장 빠른(직원이 아닌) 항목을 기록했습니다. 이는 10초 이내에 1,000자리 숫자 100쌍을 모두 읽을 수 있는 유일한 스크립트일 뿐만 아니라(다음으로 가장 가까운 숫자는 10개만 처리할 수 있음), 다음으로 가장 가까운 항목보다 3.5배 더 큰 두 숫자를 곱할 수도 있습니다! 게다가 1,000자가 조금 넘는 대본(직원 및 비직원) 중 가장 짧았습니다. 아래 스크립트에 포함시켰습니다. 4개의 챌린지 후 총 포인트는 다음과 같습니다.
큰 숫자의 곱셈에 대해 이야기하기 전에 숫자 문자열을 풀거나 벡터화하는 방법, 즉 숫자 문자열을 숫자 벡터로 바꾸는 방법에 대해 이야기해 보겠습니다. 지난 달에 본 것처럼 다음을 사용하여 한 번에 하나씩 숫자 문자열을 구문 분석합니다. 하위 문자열 루프에서 고통스럽게 느립니다. 이로 인해 우리에게는 두 가지 일반적인 대안이 남게 됩니다. 1) 문자열을 개별 단위로 분해한 다음 이를 벡터로 변환할 수 있는 형식으로 다시 합치는 것입니다(다음을 사용). 구문 분석 , 예) 또는 2) 패턴 일치를 사용합니다. 나의 초기 성향은 접근 방식 1을 사용하는 것입니다. 수년 동안 나는 JSL 패턴 일치 기능에 대해 배우는 것을 거부했습니다. 노력은 너무 컸고 정보와 예제가 너무 부족했으며 너무 게으르다. 나는 내가 필요한 모든 것을 가지고 있다고 생각했습니다. 정규식 기능, 내가 아주 잘 알고 있던 것. 더 이상은 없어.
이러한 과제를 통해 패턴 일치의 속도와 효율성에 눈을 뜨게 되었습니다. 나에게 설명했듯이 @Craige_Hales , 이러한 기능을 담당하는 개발자이자 정기적으로 챌린지에 참가하는 JSL의 패턴 일치 루틴은 다음과 같은 기반이 됩니다. 정규식 건설되었습니다. 효율성을 입증하려면 다음에서 코드를 실행하세요. 벡터화 예제.JSL , 벡터화의 네 가지 방법을 비교합니다. 또한 스크립트에 긴 난수 문자열을 생성하는 짧은 함수도 포함했습니다. 10,000개의 숫자로 구성된 문자열의 경우 루프에서 한 번에 하나씩 숫자를 구문 분석하는 것이 가장 느립니다. 내 컴퓨터에서는 약 11초가 걸립니다. 사용 단어 그리고 연결 목록 숫자를 벡터로 구문 분석할 수 있는 문자열로 분해하고 재구성하는 것이 세계적으로 더 좋습니다(0.0965초).
다음을 사용하여 동일한 작업을 수행합니다. 정규식 그리고 구문 분석 (0.08543)보다 약간 더 좋습니다. 패턴 매칭은 이 시간을 놀라운 4배(0.02179)로 줄여줍니다! 50,000자리에서는 시간 차이가 미미하지만 5,000,000자리를 고려하면 두 구문 분석 접근 방식 모두 약 10분이 걸리는 반면, 패턴 일치는 2초가 걸리므로 다른 방법과 달리 거의 선형적으로 확장됩니다! JSL의 패턴 일치에 대해 자세히 알아보려면 다음이 작성한 스크립트를 살펴보세요. @Craige_Hales 또는 @David_Burnham (누가 더 많은 정보와 예시가 포함된 자신의 블로그 게시물 몇 개 .)
곱셈 루틴을 진행합니다. 패턴 일치는 모든 벡터화에 사용됩니다. 또한 첫 번째 예에서는 마지막 챌린지에서 가장 빠른 추가 알고리즘이 사용됩니다. 첫 번째 접근법( MultiplyBig Slow.JSL ) 지금까지의 과제에서 배운 것 외에는 아무것도 사용하지 않습니다. 한 번에 두 자리의 숫자를 곱합니다. 피승수와 승수의 위치에 따라 0을 추가해야 합니다(예: 백 자리의 숫자에 십의 자리 숫자를 곱할 때 5개의 0을 추가합니다). 첫 번째 입력이 더 커지도록 입력을 정렬하는 기능에도 불구하고 이는 아무런 이점이 없습니다. 동일한 수의 작업이 수행됩니다. 그러나 마지막 예에서는 이것이 변경됩니다. 이 기능은 100자리 숫자 100개를 처리하는 데 거의 30초가 걸릴 정도로 느립니다.
~ 안에 MultiplyBig Faster.JSL 레지스터의 자릿수는 1에서 7로 증가합니다. 이는 JSL이 오버플로 없이 표시할 수 있는 자릿수의 약 절반입니다. 이 선택의 이유는 두 개의 큰 7자리 숫자를 곱할 때 명백하며 그 결과는 최대 14자리가 될 수 있습니다. 7자리 레지스터에는 14자리 숫자가 포함될 수 있으므로 마지막 예에서 사용된 추가 루틴은 7자리 이상의 숫자가 다음 레지스터로 전달되도록 변경되어야 합니다. 그럼에도 불구하고 결과 코드는 양수만 고려하면 되므로 상당히 짧아집니다. 또한 100개의 100자리 숫자 쌍(0.04375초)을 곱하면 결과가 크게 향상됩니다. 이 구현은 또한 100개의 1000자리 쌍(1.54초)을 곱하는 합리적인 작업을 수행합니다.
간단한 변화 하나로 더욱 빠르게 이동할 수 있습니다. 한 번에 하나의 레지스터를 곱하는 대신, MultiplyBig Fastest.JSL JSL 매트릭스 연산을 사용하여 더 짧은 숫자의 각 레지스터를 더 큰 숫자 전체에 곱합니다. 이 접근 방식은 이전 접근 방식보다 빠르며, 100개의 1,000자리 쌍에 대해 0.3015초로 5배 향상된 속도를 기록합니다.
그리고 더욱 빠르게 갈 수 있습니다. 파일 MultiplyBig - Brady.JSL , 1,000자리 숫자를 곱할 때 약간 느린 반면, 숫자의 크기가 약 2,000자리 이상에 도달하면 더 뛰어납니다. 이는 동일한 루프에서 곱셈과 덧셈이 수행될 수 있도록 연산 순서를 변경함으로써 달성되었습니다. 이 뒤에 있는 세부 사항은 제가 다루고 싶은 범위를 벗어나지만, @brady_brady 그는 관심이 있으면 이 게시물에 추가할 수 있는 짧은 글을 기꺼이 작성하겠다고 말했습니다. 더 빠르게? 아마도. O(n에서 곱셈 연산 수를 줄이는 암호학에서 일반적으로 사용되는 두 가지 주목할만한 곱셈 알고리즘이 있습니다. 2 ) 에게 에 1.58 ) 또는 낮추다 . 더 많은 수의 추가 작업이 필요하기 때문에 JSL에서 더 빠른지 여부를 말하기는 어렵습니다. 이 게시물에서 나는 이러한 알고리즘 중 하나의 빠른 JSL 버전을 구현하려고 시도했지만 실패했습니다.
2020년 8월 1일: 덕분에 @Craige_Hales 버그를 잡기 위해 MultiplyBig Fastest.JSL . 문제를 수정했습니다. 또한 Craige의 MultiplyBig 스크립트를 추가하려고 했는데 잊어버렸습니다. 그는 알고리즘 속도를 높이기 위한 방법으로 조회 테이블을 사용합니다(몇 가지 주의 사항 포함). 그의 대본은 늘 그렇듯이 철저히 주석이다.
