참고: 다음의 챌린지 항목입니다. @David_Burnham 마감일 이전에 제출되었지만 내 이메일 시스템에 의해 격리되었습니다. 원래 블로그 게시물이 게시된 후에야 발견했습니다. 새 항목에 따른 변경 사항을 반영하도록 결과를 업데이트하는 중입니다.
챌린지 2에 코드를 제출해 주신 모든 분들께 감사드립니다. 일부 코드는 작은 값에 더 잘 작동하고 일부 코드는 큰 값에 더 잘 작동했기 때문에 점수를 매기는 것이 어려웠습니다. 아래 표는 챌린지의 각 부분에 대한 결과를 제공합니다. 3번의 실행이 있었습니다 프라임 , 5로 나누어지지 않는 5자리 난수 홀수, 5로 나누어지지 않는 8자리 및 9자리 홀수, 5로 나누어지지 않는 12~15자리 홀수 1000개. 결과는 마지막 두 가지 조건을 기반으로 했습니다. 포인트는 챌린지 간에 분배되었으며, 1개당 1.5포인트입니다. 성 , 2대1 nd , 3의 경우 0.5 rd . 가장 빠른 제출 시간도 제공됩니다(초 단위).
@leelaim isPrime(Small) 시간은 JMP 직원만큼 빨랐습니다(+3점). @랜든 isPrime(Big) 스크립트는 Parallel Assign 기능을 사용하여 속도를 향상시킵니다. 항목 중 두 개가 결과를 캐시했습니다. getPrimes 사용하여 네임스페이스 . 이 접근 방식은 결과에 두 번 이상 액세스해야 할 때 유용합니다(그러나 실행 시간은 캐시되지 않은 결과를 기반으로 함). 이 네 가지 항목이 모두 아래에 포함되었습니다.
두 가지 챌린지 이후의 순위표는 다음과 같습니다.
챌린지 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보다 작은 숫자에 해당 소수를 곱한 값이 되며, 이는 다른 소수로 제거됩니다(예를 들어 11*5는 5에 대해 체로 제거됩니다. 3인용 체로 11*9 등). 이러한 개선으로 런타임이 1.3545로 절반 이상 단축되었습니다. 두 번째는 1,000,000의 경우 0.01625, 100,000,000의 경우 2.6694의 시간을 사용하여 내부 루프에 JSL의 행렬 연산을 사용하면 거의 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을 초과하지 않도록 압축된 값을 포함하는 스크립트의 크기는 크기에 관계없이 400만 자 이상의 코드, 4.6MB의 디스크 공간, 로드하는 데 약 5.5초가 걸렸습니다. N . 다른 솔루션보다 느립니다. 가장 빠르지도 짧지도 않지만 문제에 대한 그의 독특한 접근 방식, 압축 사용 및 병렬 할당 .
발견 N 소수는 더 어려운 문제입니다. 체를 사용한다고 가정하면 최대 값의 벡터를 만들어야 합니다. N 번째 소수. 이를 위해서는 해당 값의 상한을 추정해야 합니다. 체질되지 않은 값을 찾으려면 알고리즘의 일부 또는 전체를 다시 실행해야 할 수 있으므로 과소평가하지 마십시오. n번째 prime.jmp의 추정값 6개의 서로 다른 추정치를 보여줍니다. 예상1 작은 값에 대해 값이 과소평가되는 경우를 제공합니다. N . 많은 추정치가 다음에만 적용됩니다. N 특정 값보다 큰 경우에는 대체 추정치를 제공하기 위해 주의를 기울여야 합니다. 추정2 에 좋다 N ≥ 13 및 추정3 더 큰 값에 대해 개선됩니다. 불행하게도 좋은 경계는 간단하지 않습니다. 예상4 에서 사용되었습니다 프라임 빠른 제출.jsl . 좋은 결과를 내지 못하고 매우 큰 값에 대해 과소평가하지만 N , 간단하고 기억하기 쉽습니다. 예상5 실제 값과 함께 비선형을 사용하여 파생되었습니다. 예상6 개선된다 예상5 테이블의 어떤 값도 과소평가되지 않도록 값을 약간 교란시킵니다. 100과 1e8 사이에 과소평가가 존재하지 않는다는 보장은 없습니다. 다른 표 열에는 각 기술에 대한 과소평가/과대평가가 나와 있습니다.
소수를 결정하는 것은 소수를 생성하는 것과 비슷한 경로를 따를 수 있습니다. 숫자가 주어지면 엑스 , 당신은 할 수 있습니다 나 = 2. 만약에 모드( N , 나 ) == 0 중지, 그렇지 않으면 증가 나 . 까지 계속 모드( N , 나 ) == 0 또는 나 == N . 아래 코드는 홀수만 확인하면 이점이 있습니다. 나 1차 테스트 후 나 = 2 그리고 다음 경우에 중지 나 > = 천장(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;
);
위 스크립트는 테이블의 8자리, 9자리 숫자 1,000개를 모두 확인하는데 약 1.4초가 소요됩니다. 큰 숫자 표.jmp ( 작은 ).
이를 더욱 개선하기 위해 소수의 벡터를 생성할 수 있습니다(최대 천장(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 위의 코드에서 인덱스된 행렬 값( inVals[i] ). 두번째, 위치 행렬 크기가 커짐에 따라 행렬 연결 속도가 느려집니다. 정렬된 행렬로 작업할 수 있다면, 위치 정렬됨 이진 검색을 수행하며 훨씬 빠릅니다.보다 속도 테스트 매트릭스 Operations.jsl 행렬 참조 및 연결에 대한 추가 예제는 다음을 참조하세요.
큰 수의 열에서 소수를 찾으려고 합니다( 큰 )가 더 문제다. 처음 10개를 찾는 데 약 1.9초가 걸립니다. 이 시점에서는 개선을 위해 전문적인 알고리즘을 사용해야 합니다. 밀러-라빈(MR) 소수성 테스트를 위해 일반적으로 사용되며 비교적 쉽게 구현되는 기술입니다. 결정론적 버전은 다음과 같습니다. millerRabin1.jsl . MR은 모듈러 지수화에 의존하므로 오버플로 오류가 발생하지 않도록 주의해야 합니다. 그 자체로 MR은 1000개를 모두 처리하는 데 5.28초가 걸립니다. 큰 숫자. MR이 위의 첫 번째 isPrime 알고리즘(2.34초)보다 느리다는 사실에 놀랄 수도 있습니다. 작은 숫자. 이는 숫자의 크기가 커질수록 계산 효율성이 높아지기 때문에 개선이 필요하기 때문일 수 있습니다. 위의 2)를 사용하여 특정 크기의 소수를 테스트합니다. 숫자가 소수이면 중지하십시오. 그렇지 않으면 MR로 전환하세요. 이 접근 방식은 다음에서 찾을 수 있습니다. millerRabin2.jsl . 확인할 이상적인 소수 수를 찾기 위해 일부 조정이 수행되었습니다. 이로써 시간은 2.33초로 절반으로 단축되었습니다.
