注: デイビッド・バーナムからのチャレンジ エントリーは締め切り前に送信されましたが、私のメール システムによって隔離されていました。元のブログ投稿が公開された後に初めてそれを発見しました。新しいエントリーに基づく変更を反映するために結果を更新しています。
チャレンジ 2 にコードを提出してくださった皆様、ありがとうございました。一部のコードは値が小さいほどうまく機能し、一部のコードは値が大きくなるほどうまく機能したため、採点が難しかったです。以下の表は、チャレンジの各パートの結果を示しています。 プライムの実行は 3 回、5 で割り切れない 5 桁のランダムな奇数 1000 個、5 で割り切れない 8 桁と 9 桁の奇数 1000 個、5 で割り切れない 12 桁から 15 桁の奇数 1000 個でした。結果は最後の 2 つの条件に基づいています。ポイントはチャレンジ間で分割され、1位は 1.5 ポイント、2位は 1 ポイント、3位は 0.5 ポイントです。最速の提出の時間も秒単位で示されています。
リーライム isPrime(Small) time was as fast as any by a JMP staff member (+3 pts.). @ランドン isPrime(Big) script uses the Parallel Assign function to improve speed. Two of the entries cached their results for 素数を取得する using 名前空間. This approach is helpful when the results need to be accessed more than once (run times are based on uncached results, however). All four of these entries have been included below.
2 つのチャレンジ後のリーダーボードは次のとおりです。
チャレンジ 3 は 6 月 1 日水曜日に投稿されます。
課題 2 では、 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 つの最適化バージョンを示します。最初のバージョンは、2 の倍数をすべて削除することから開始し、3 以降の奇数のみをループします。外側のループの上限には Sqrt( n ) が使用されます。これは、それより小さい非素数はすべてすでにふるいにかけられているためです。たとえば、100 未満の素数をすべて見つけるには、10 にふるいにかけるだけで済みます。10 より大きい素数のふるいにかけられた数は、その素数と 10 未満の数の積になります。10 未満の数は、他の素数で削除されています (たとえば、11*5 は 5 のふるいでは削除され、11*9 は 3 のふるいでは削除されます)。これらの改善により、実行時間は半分以下になり、1.3545 になりました。 2 番目は、内部ループに 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 );
);
もっと良い結果が出せますか? アトキンのふるいは理論的にはより効率的で、 素数アトキンスの例.JSLとアトキンス素数（最適化）.JSLで実装されています。前者は最適化されていない、より理解しやすい実装です (1,000,000 で 2.236 秒)。最適化されていないエラトステネスのバージョンよりも優れています。ただし、最適化されたバージョンは最適化されたエラトステネス (100,000,000 で 4.914 秒) には勝てませんでした。さらに、プログラム的にも理論的にも、はるかに長くて複雑です。
数字の表から読み取る場合はどうでしょうか。これはアルゴリズムを書くという趣旨ではありませんが、できないとは言っていません。 @Craige_Hales は、このアプローチを使用したソリューションを提供しました。nが 1e8 を超えないという問題の仕様を考えると、圧縮された値を格納するスクリプトのサイズは、 nのサイズに関係なく、400 万文字を超えるコード、4.6 MB のディスク領域、および約 5.5 秒の読み込み時間が必要でした。他のソリューションよりも遅いです。最速でも最短でもありませんが、問題に対する Craige のユニークなアプローチ、圧縮の使用、および並列割り当てのため、このスクリプトを含めました。
n個の素数を見つけることは、より困難な問題です。ふるいを使用すると仮定すると、 n番目の素数までの値のベクトルを作成する必要があります。これを行うには、その値の上限を推定する必要があります。ふるいにかけられていない値を見つけるためにアルゴリズムの一部または全体を再実行する必要がある場合があるため、過小評価は避ける必要があります。 n 番目の素数の値を推定する.jmpには、6 つの異なる推定値が表示されます。Est1は、 nが小さい場合に値が過小評価されるケースを示しています。多くの推定値は、特定の値より大きいnにのみ適用され、このような場合には代替の推定値を提供するように注意する必要があります。Est2はn ≥ 13 に適しており、 Est3 はより大きな値に対してこれを改善します。残念ながら、適切な境界が単純であることはめったにありません。Est4は素数高速送信.jslで使用されました。これはそれほどうまく機能せず、 nの非常に大きな値に対して過小評価しますが、単純で覚えやすいものです。Est5は、実際の値を使用して Nonlinear を使用して導出されました。 Est6 は、表内のどの値も過小評価されないように値をわずかに変更することでそれは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;
);
上記のスクリプトでは、Table of big numbers.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 秒未満になります。
速度を向上させるための一般的な注意事項が 2 つあります。マトリックス値を複数回使用する必要がある場合は、インデックス付きマトリックスではなく変数を使用して、値を変数に割り当てる方が高速です。これにより、コードが長くなる可能性がありますが、時間の節約になります。上記のコードでnextVal をインデックス付きマトリックス値 ( インヴァルス[i] ) に置き換えて試してみてください。2 番目に、マトリックスのサイズが大きくなるにつれて、 場所とマトリックスの連結が遅くなります。ソートされたマトリックスを使用できる場合は、 Loc Sorted でバイナリ検索が実行され、はるかに高速になります。マトリックスの参照と連結に関するその他の例については、Speed testing matrix operations.jsl を参照してください。
大きな数 ( 大きい ) の列で素数を見つけようとすると、さらに問題が起こります。最初の 10 個を見つけるのに約 1.9 秒かかります。この時点で、改善のためには特殊なアルゴリズムに頼る必要があります。Miller -Rabin (MR) は、素数かどうかをテストするためによく使用され、比較的簡単に実装できる手法です。決定論的なバージョンはミラーラビン1.jslで提供されています。MR はべき乗剰余に依存しており、オーバーフロー エラーが発生しないように注意する必要があります。MR 自体は、1000 個の大きい数すべてを処理するのに 5.28 秒かかります。小さい数を処理するのに、上記の最初の isPrime アルゴリズム (2.34 秒) よりも MR の方が遅いことに驚かれるかもしれません。これは、数のサイズが大きくなるにつれて計算効率が高くなるためである可能性があり、改善が示唆されています。つまり、上記の 2) を使用して、特定のサイズの素数をテストします。数が素数の場合は停止します。それ以外の場合は、MR に切り替えます。このアプローチはミラーラビン2.jslにあります。チェックする素数の理想的な数を見つけるために、いくつかの調整が行われました。これにより、時間が半分の 2.33 秒に短縮されました。
