참고: @데이비드_번햄 의 챌린지 항목이 마감일 전에 제출되었지만 이메일 시스템에서 격리되었습니다. 원래 블로그 게시물이 게시된 후에야 발견했습니다. 새 항목에 따른 변경 사항을 반영하도록 결과를 업데이트하고 있습니다.
챌린지 2에 코드를 제출해 주신 모든 분들께 감사드립니다. 점수는 챌린지였습니다. 어떤 코드는 작은 값에 더 잘 작동하고 어떤 코드는 큰 값에 더 잘 작동했기 때문입니다. 아래 표는 챌린지의 각 부분에 대한 결과를 보여줍니다. 프라임입니다 에 대해 세 번의 실행이 있었습니다. 5로 나누어지지 않는 5자리 랜덤 홀수 1000개, 5로 나누어지지 않는 8~9자리 홀수, 5로 나누어지지 않는 12~15자리 홀수였습니다. 결과는 마지막 두 조건에 따라 결정되었습니다. 점수는 챌린지 간에 나뉘었습니다. 1 등 은 1.5점, 2 등 은 1점, 3 등 은 0.5점입니다. 가장 빠르게 제출한 시간에 대한 시간도 제공됩니다(초).
@릴라임 isPrime(Small) 시간은 JMP 직원의 어떤 것보다 빨랐습니다(+3점). @랜던 isPrime(Big) 스크립트는 Parallel Assign 함수를 사용하여 속도를 개선합니다. 두 항목은 Namespace를 사용하여 getPrime에 대한 결과를 캐시했습니다. 이 접근 방식은 결과에 두 번 이상 액세스해야 할 때 유용합니다(그러나 실행 시간은 캐시되지 않은 결과에 따라 달라짐). 이 네 가지 항목은 모두 아래에 포함되었습니다.
두 가지 과제를 마친 후의 순위표는 다음과 같습니다.
챌린지 3은 6월 1일 수요일에 게시됩니다.
과제 2에서는 가능한 두 가지 방법으로 소수를 구하는 것이었습니다. 양의 정수 값 n이 주어졌을 때, 다음을 찾아야 합니다. 1) n개의 소수 또는 2) n 아래의 모든 소수. 구현하기가 다소 쉽기 때문에 2)부터 시작해 보겠습니다. 소수를 찾는 가장 간단한 방법은 시행착오입니다. 후보로 2와 빈 소수 집합을 출발점으로 하여, 현재 소수 집합에서 후보 숫자를 균등하게 나누는 것이 있는지 확인합니다. 그렇지 않으면, 소수 집합에 더하고 다음 후보로 넘어갑니다. 시작할 때 소수 집합에 아무것도 없으므로 2를 더합니다. 3을 확인하면 {2}의 아무것도 나누지 않고 소수 집합에 더합니다. 그러나 숫자 4는 {2,3}의 무언가를 나누고 더하지 않습니다. 구현 예는 아래에 나와 있습니다.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
이 접근 방식에는 몇 가지 장점이 있습니다. 이해하기 쉽고, 코드가 간결하며, 두 가지 소수 찾기 과제에 쉽게 적용할 수 있습니다. 안타깝게도 매우 느립니다. 100,000 이하의 소수를 찾는 데 19.43초가 걸렸습니다 .
조금 더 복잡한 접근 방식은 체를 사용하는 것입니다. 체는 숫자가 소수인지 테스트하는 대신, 소수에서 벗어난 숫자를 테스트합니다. 가장 오래되고 잘 알려진 것은 에라토스테네스의 체 입니다. 모든 것이 소수라고 가정하여 시작합니다. 첫 번째 소수로 2를 시작으로, 그것을 균등하게 나누는 모든 숫자를 찾아 소수 집합에서 제거합니다. 소수 집합에 여전히 있는 다음 숫자로 계속합니다. 아래는 최적화되지 않은 버전입니다.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
가장 눈에 띄는 장점은 속도입니다. 100,000 이하의 모든 소수를 찾는 데 걸린 시간은 0.2811초로 약 70배 빠르고 1,000,000의 경우 3.4025초였습니다. 코드는 여전히 간결하고 이해하기 쉽습니다. 사소한 단점은 소수가 아닌 숫자를 추적하기 위해 벡터를 만들어야 한다는 것입니다(즉, 연결로 목록을 늘릴 수 없습니다. 나중에 살펴보겠지만 반드시 이점은 아닙니다). 이는 필요한 벡터 크기를 정확히 알 수 없기 때문에 n개의 소수를 찾는 문제를 더 어렵게 만듭니다.
아래에 두 가지 최적화된 버전이 있습니다. 첫 번째 버전은 2의 모든 배수를 제거하는 것으로 시작한 다음 3부터 홀수에 대해서만 반복합니다. 외부 루프의 상한에 sqrt( n )을 사용하는 이유는 그보다 작은 모든 비소수가 이미 체로 걸러졌기 때문입니다. 예를 들어, 100 미만의 모든 소수를 찾으려면 10까지 체로 걸러내기만 하면 됩니다. 10보다 큰 소수에 대해 체로 걸러낸 숫자는 해당 소수와 10보다 작은 수의 곱이 되며, 10보다 작은 수는 다른 소수와 함께 제거됩니다(예: 11*5는 5에 대한 체로 제거되고, 11*9는 3에 대한 체로 제거됩니다). 이러한 개선 사항으로 런타임이 절반 이상 단축되어 1.3545가 됩니다. 두 번째는 내부 루프에 JSL의 행렬 연산을 사용하는 이점을 보여줍니다. 1,000,000의 경우 시간이 0.01625이고 100,000,000의 경우 시간이 2.6694로 거의 100배나 향상되었습니다!
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
더 잘할 수 있나요? 아킨의 체는 이론적으로 더 효율적이며 Primes Atkins 예제.JSL 과 Primes Atkins(최적화됨).JSL 에 구현되었습니다. 첫 번째는 최적화되지 않고 이해하기 쉬운 구현(1,000,000에 대해 2.236초)을 제공합니다. 에라토스테네스의 최적화되지 않은 버전보다 낫습니다. 그러나 최적화된 버전은 최적화된 에라토스테네스(100,000,000에 대해 4.914초)를 이길 수 없습니다. 게다가 프로그래밍적으로나 이론적으로 훨씬 더 길고 복잡합니다.
숫자 표에서 읽는 것은 어떨까요? 알고리즘을 작성하려는 의도는 아니지만, 그럴 수 없다고 한 건 아닙니다. @Craige_Hales가 이 접근 방식을 사용하여 솔루션을 제공했습니다. n이 1e8을 초과하지 않는다는 문제 사양을 감안할 때, 압축된 값을 포함하는 스크립트의 크기는 n 의 크기에 관계없이 400만 자 이상의 코드, 4.6MB의 디스크 공간, 약 5.5초가 걸렸습니다. 다른 솔루션보다 느렸습니다. 가장 빠르거나 가장 짧은 것은 아니지만 문제에 대한 그의 독특한 접근 방식, 압축 사용 및 병렬 할당 때문에 Craige의 스크립트를 포함했습니다.
n개의 소수를 찾는 것은 더 어려운 문제입니다.체를 사용한다고 가정하면 n 번째 소수까지의 값 벡터를 만들어야 합니다.이를 위해 해당 값의 상한을 추정해야 합니다.체질되지 않은 값을 찾기 위해 알고리즘의 일부 또는 전체를 다시 실행해야 할 수 있으므로 과소평가는 피해야 합니다 .nth prime.jmp의 추정값은 6가지 다른 추정값을 보여줍니다.Est1 은 작은 n 에 대해 값이 과소평가되는 경우를 제공합니다.많은 추정값은 특정 값보다 큰 n 에만 적용되며 이러한 경우 대체 추정값을 제공하는 데 주의해야 합니다.Est2는 n ≥ 13에 적합하고 Est3은 더 큰 값에 대해 이를 개선합니다.안타깝게도 좋은 경계는 거의 간단하지 않습니다.Est4 는 Primes 빠른 제출.jsl 에서 사용되었습니다.n 의 매우 큰 값 에 대해 과소평가하고 좋은 성과를 내지 못하지만 간단하고 기억하기 쉽습니다.Est5 는 실제 값을 사용하여 Nonlinear를 사용하여 도출되었습니다. 에스트6 는 그것은5입니다 보다 값을 약간 교란하여 표의 값 중 어느 것도 과소평가되지 않도록 개선되었습니다. 100과 1e8 사이에 과소평가가 존재하지 않는다는 보장은 없습니다. 다른 표 열은 각 기술에 대한 과소/과대평가를 제공합니다.
소수 여부를 결정하는 것은 소수를 생성하는 것과 비슷한 경로를 따를 수 있습니다. 숫자 x 가 주어지면 i = 2로 둘 수 있습니다. Mod( n , i ) == 0 이면 중지하고, 그렇지 않으면 i를 증가시킵니다. Mod( n , i ) == 0 또는 i == n이 될 때까지 계속합니다. 아래 코드는 i = 2에서 초기 테스트 후에 홀수 i 만 확인하고 i > = Ceiling(Sqrt( n )) 일 때 중지하는 이점이 있습니다.
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
위 스크립트는 큰 숫자의 표.jmp ( 작은 ) 표에 있는 8자리, 9자리 숫자 1,000개를 모두 확인하는 데 약 1.4초가 걸립니다.
이를 더욱 개선하려면 소수 벡터( Ceiling(Sqrt( n ) )까지)를 생성하고 이를 반복할 수 있습니다.
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
이렇게 하면 시간이 절반 이상 단축되어 0.6초 이하로 줄어듭니다.
속도를 개선하기 위한 두 가지 일반적인 참고 사항: 행렬 값을 두 번 이상 사용해야 하는 상황에서는 인덱스된 행렬 대신 변수를 사용하여 값을 변수에 할당하는 것이 더 빠릅니다. 이렇게 하면 코드가 길어질 수 있지만 시간은 절약할 수 있습니다. 위 코드에서 nextVal을 인덱스된 행렬 값( 인발스[i] )으로 바꿔서 시도해 보세요. 둘째, 행렬의 크기가 커질수록 장소 와 행렬 연결이 느려집니다. 정렬된 행렬로 작업할 수 있다면 Loc Sorted는 이진 검색을 수행하며 훨씬 빠릅니다. 행렬 참조 및 연결에 대한 추가 예는 Speed testing matrix operations.jsl을 참조하세요.
큰 숫자( 큰 ) 열에서 소수를 찾으려는 것은 더 문제가 됩니다. 처음 10개를 찾는 데는 약 1.9초가 걸립니다. 이 시점에서 개선을 위해서는 특수 알고리즘에 의존해야 합니다. Miller-Rabin(MR)은 소수성을 테스트하는 데 일반적으로 사용되고 비교적 쉽게 구현되는 기술입니다. 결정론적 버전은 밀러라빈1.jsl 에 나와 있습니다. MR은 모듈러 지수법에 의존하며 오버플로 오류가 발생하지 않도록 주의해야 합니다. MR 자체로 1000개의 큰 숫자를 모두 처리하는 데 5.28초가 걸립니다. MR이 작은 숫자를 처리하는 데 위의 첫 번째 isPrime 알고리즘(2.34초)보다 느리다는 사실에 놀랄 수 있습니다. 이는 숫자의 크기가 커질수록 계산 효율성이 높아지기 때문일 가능성이 높으며, 이는 개선 사항을 시사합니다. 위의 2)를 사용하여 특정 크기의 소수를 테스트합니다. 숫자가 소수이면 중지합니다. 그렇지 않으면 MR로 전환합니다. 이 방법은 밀러라빈2.jsl 에서 찾을 수 있습니다. 확인할 이상적인 소수의 수를 찾기 위해 약간의 튜닝이 수행되었습니다. 이를 통해 시간이 절반으로 단축되어 2.33초가 되었습니다.
