챌린지 4 에서 즐거운 시간을 보냈으면 좋겠습니다. 앞으로 좋은 챌린지가 될 만한 아이디어가 있다면 알려주세요. 저는 항상 좋은 자료를 찾고 있어요!
축하합니다, @랜던 ! 1,000자리 숫자 100쌍(9.88초)과 가장 긴 숫자(7,150) 챌린지에서 가장 빠른(비직원) 항목을 제출했습니다. 1,000자리 숫자 100쌍을 10초 이내에 모두 읽을 수 있는 유일한 스크립트였을 뿐만 아니라(가장 가까운 것은 10개만 읽을 수 있었습니다), 가장 가까운 항목보다 3.5배 더 큰 두 숫자를 곱할 수도 있었습니다! 게다가 모든 스크립트(직원 및 비직원) 중에서 가장 짧은 1,000자를 약간 넘었습니다. 아래 스크립트에 포함했습니다. 4개의 챌린지 후의 총점은 다음과 같습니다.
큰 숫자를 곱하는 것에 대해 이야기하기 전에, 숫자 문자열을 풀거나 벡터화하는 것에 대해 이야기해 보겠습니다.숫자 문자열을 숫자 벡터로 바꾸는 것입니다.지난 달에 보았듯이, 루프에서 Substr을 사용하여 숫자 문자열을 한 번에 하나씩 구문 분석하는 것은 고통스러울 정도로 느립니다.따라서 두 가지 일반적인 대안이 남습니다.1) 문자열을 개별 단위로 분해한 다음 벡터로 변환할 수 있는 형태로 다시 조립합니다(예: 파스하다 사용) 또는 2) 패턴 매칭을 사용합니다.처음에는 접근 방식 1을 사용하려고 했습니다.수년 동안 저는 JSL 패턴 매칭 함수에 대해 배우는 것을 거부했습니다.노력이 너무 많았고, 정보와 예제가 너무 부족했으며, 제가 너무 게으르기 때문입니다.Regex 함수 로 필요한 모든 것을 갖췄다고 생각했고, 제가 아주 잘 알고 있었습니다.더 이상은 아닙니다.
이러한 과제를 통해 패턴 매칭의 속도와 효율성에 눈을 뜨게 되었습니다. 이러한 기능을 담당하는 개발자이자 과제에 정기적으로 참여하는 @크레이지_헤일스 가 설명해 주었듯이, JSL의 패턴 매칭 루틴은 정규식 의 기반입니다. 효율성을 입증하기 위해 벡터화의 네 가지 다른 방법을 비교하는 벡터화 예제.JSL 의 코드를 실행해 보세요. 스크립트에 긴 난수 문자열을 생성하는 짧은 함수도 포함했습니다. 10,000개의 숫자로 구성된 문자열의 경우 루프에서 숫자를 하나씩 구문 분석하는 것이 지금까지 가장 느린데, 제 컴퓨터에서는 약 11초가 걸립니다. 단어 와 Concat List를 사용하여 숫자를 분해하고 재구성하여 벡터로 구문 분석할 수 있는 문자열을 만드는 것이 훨씬 더 좋습니다(0.0965초).
정규식 과 파스하다를 사용하여 같은 작업을 하는 것이 그보다 약간 더 좋습니다(0.08543). 패턴 매칭은 이 시간을 놀랍게도 4배(0.02179) 줄여줍니다! 50,000자리의 경우 시간 차이가 미미하지만 5,000,000자리를 고려하면 두 파싱 접근 방식 모두 약 10분이 걸리는 반면 패턴 매칭은 2초가 걸리며 다른 방법과 달리 거의 선형적으로 확장됩니다! JSL에서 패턴 매칭에 대해 자세히 알아보려면 @크레이지_헤일스 또는 @데이비드_번햄 이 작성한 스크립트를 살펴보세요( 자신만의 블로그 게시물 몇 개에 더 많은 정보와 예가 있습니다.)
곱셈 루틴으로 넘어갑니다. 모든 벡터화에 패턴 매칭이 사용됩니다. 또한, 마지막 챌린지의 가장 빠른 덧셈 알고리즘이 첫 번째 예제에 사용됩니다. 첫 번째 접근 방식( 곱하기Big Slow.JSL )은 지금까지 챌린지에서 배운 것 외에는 아무것도 사용하지 않습니다. 한 번에 두 개의 숫자를 곱하고, 피승수와 승수의 위치에 따라 0을 추가합니다(예: 백의 자리의 숫자를 십의 자리의 숫자와 곱할 때 0을 다섯 개 더함). 함수가 첫 번째 입력이 더 크도록 입력을 정렬했지만, 이는 아무런 이점이 없습니다. 동일한 수의 연산이 수행됩니다. 그러나 이는 마지막 예제에서 바뀔 것입니다. 이 함수는 느리며 100개의 100자리 숫자 세트를 처리하는 데 거의 30초가 걸립니다.
곱하기 더 크게 더 빠르게.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 )에서 O(n 1.58 ) 이하 로 줄입니다.큰 숫자에 대한 더 많은 덧셈 연산이 필요하기 때문에 JSL에서 더 빠를지 여부는 말하기 어렵습니다.이 게시물을 작성할 당시에는 이 두 알고리즘 중 어느 것의 빠른 JSL 버전을 구현하려고 했지만 구현할 수 없었습니다.
2020년 8월 1일: 곱하기큰가장빠른.JSL 에서 버그를 잡아준 @크레이지_헤일스 에게 감사드립니다. 문제를 수정했습니다. 또한 Craige의 MultiplyBig 스크립트를 추가했는데, 의도했지만 잊어버렸습니다. 그는 알고리즘 속도를 높이는 방법으로 조회 테이블을 사용합니다(몇 가지 단서 있음). 그의 스크립트는 평소처럼 철저히 주석입니다.
