注: からのチャレンジエントリー@David_Burnham期限前に提出されましたが、電子メール システムによって隔離されました。 私がこのことに気づいたのは、元のブログ投稿が公開された後でした。 新しいエントリに基づいた変更を反映するために結果を更新しています。
チャレンジ 2 のコードを提出していただいた皆様、ありがとうございます。 一部のコードは値が小さいほどうまく機能し、一部のコードは値が大きいほどうまく機能するため、スコアリングは課題でした。 以下の表は、チャレンジの各部分の結果を示しています。 3回のランがありましたプライムです、5 で割り切れない 5 桁のランダムな奇数、5 で割り切れない 8 桁と 9 桁の奇数、および 5 で割り切れない 12 ～ 15 桁の奇数を 1000 個。 結果は最後の 2 つの条件に基づいています。 ポイントはチャレンジ間で分配され、1 つにつき 1.5 ポイントとなりました。セント、1対2 nd 、3 の場合は 0.5 rd 。 最速の送信にかかる時間も秒単位で示されます。
@リーライムisPrime(Small) のタイムは、JMP スタッフ メンバーのどのタイムよりも速かった (+3 ポイント)。 @降下するisPrime(Big) スクリプトは、速度を向上させるために Parallel Assign 関数を使用します。 エントリのうち 2 つは結果をキャッシュしました素数の取得を使用して名前空間。 このアプローチは、結果に複数回アクセスする必要がある場合に役立ちます (ただし、実行時間はキャッシュされていない結果に基づいています)。 これら 4 つのエントリすべてが以下に含まれています。
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 つの最適化されたバージョンを示します。 1 つ目は、2 の倍数をすべて削除することから始まり、次に 3 以降の奇数のみをループします。 Sqrt( n ) は、それより小さいすべての非素数がすでにふるいにかけられているため、外側のループの上限として使用されます。 たとえば、100 未満の素数をすべて見つけるには、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 );
);
もっと上手にできるでしょうか？ のアトキンのふるい理論的にはより効率的であり、プライムズ アトキンスの example.JSLそしてPrimes Atkins (最適化).JSL 。 1 つ目は、最適化されていない、より理解しやすい実装です (1,000,000 で 2.236 秒)。 最適化されていないバージョンの Eratosthenes よりも優れています。 ただし、最適化されたバージョンは、最適化されたエラトステネス (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 。 以下のコードは、奇数をチェックするだけでメリットが得られます。私での最初のテストの後私= 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;
);
上記のスクリプトは、テーブル内の 1,000 個の 8 桁と 9 桁の数字をすべてチェックするのに約 1.4 秒かかります。大きな数字の表.jmp (小さい）。
これをさらに改善するには、素数のベクトル (最大天井(平方メートル( 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 つの一般的な注意事項:行列値を複数回使用する必要がある状況では、インデックス付き行列の代わりに変数を使用して、値を変数に割り当てる方が高速です。 これによりコードが長くなる可能性がありますが、時間を節約できます。 置き換えて試してみてください次の値上記のコードでは、インデックス付き行列値 ( inVals[i] ）。 2番、ロック行列のサイズが大きくなるにつれて、行列の連結は遅くなります。 ソートされた行列を操作できる場合は、ロックソート済み二分探索を実行し、はるかに高速になります。見るスピード テスト マトリックス Operations.jsl行列の参照と連結に関する追加の例については、を参照してください。
大きな数値の列で素数を見つけようとしています (大きい）はさらに問題があります。 最初の 10 件を見つけるには約 1.9 秒かかります。 現時点では、改善のために特殊なアルゴリズムに依存する必要があります。 ミラー・ラビン (MR)は、素数性をテストするために一般的に使用され、比較的簡単に実装できる手法です。 決定論的なバージョンは次のとおりです。ミラーラビン1.jsl 。 MR はべき乗剰余演算に依存しているため、オーバーフロー エラーが発生しないように注意する必要があります。 MR 単独では、1000 件すべてを処理するのに 5.28 秒かかります。大きい数字。 驚くかもしれませんが、MR は、上記の最初の isPrime アルゴリズム (2.34 秒) よりも処理が遅いです。小さい数字。 これはおそらく、数値のサイズが大きくなるにつれて計算効率が向上するためであり、改善が示唆されています。上記の 2) を使用して特定のサイズの素数をテストします。 数値が素数の場合は停止します。 それ以外の場合は、MR に切り替えます。このアプローチは次の場所にあります。ミラーラビン2.jsl 。 チェックする素数の理想的な数を見つけるために、いくつかの調整が実行されました。 これにより、時間は半分の 2.33 秒に短縮されました。
