素数の効率的な保存

StackOverflow https://stackoverflow.com/questions/1032427

質問

ライブラリの場合、制限Lまでの最初の素数を格納する必要があります。このコレクションには、O（1）ルックアップ時間が必要です（数が素数であるかどうかを確認するため）。次の素数を見つけるための数値（Lよりも小さいと仮定）。

Lが固定されていることを考えると、リストを生成するエラトステインのふるいは問題ありません。現時点では、パックされたブール配列を使用してリストを格納します。この配列には、3〜Lの奇数のエントリのみが含まれます。これには（L-2）/ 2ビットのメモリが必要です。より多くのメモリを使用せずに静的にLを増やしたいと思います。

同様のプロパティを持つより少ないメモリを使用するデータ構造はありますか？または、少なくとも一定のルックアップ時間で？ （その後、素数が得られるまで奇数を列挙できます）

（これを書いた言語は要素ですが、この質問は、どの言語でも同じです組み込みまたは簡単にプログラム可能なパックドビット配列）

役に立ちましたか？

解決

余分な素数を明示的にチェックして、冗長性を削除できます。

現時点では、2で割り切れる数を明示的に確認し、素数であるかどうかを奇数のみで保存することにより、2つだけこれを行います。

2と3の場合、剰余0から5を取得しますが、そのうちの1と5のみが2または3で割り切れず、素数になるため、1/3になります。

2、3、および5の場合、30個のうち8個の数字を取得できます。これは1バイトに格納すると便利です。

これについては、こちらで詳しく説明しています。

他のヒント

ビットマップとホイールのパックに代わるもの-しかし、特定のコンテキストで同様に効率的-は、連続する素数間の差を保存します。いつものように2番を省くと、すべての違いは均等になります。差分/ 2を保存すると、バイトサイズの変数を使用して最大2 ^ 40ishの領域（1999066711391の直前）を取得できます。

2 ^ 32の素数は194 MByteしか必要としませんが、オッズのみのパックされたビットマップの場合は256 MByteです。デルタに格納された素数の反復は、オッズのみのビットマップとして知られるモジュロ2ホイールを含むホイールストレージよりもはるかに高速です。

1999066711391以降の範囲では、より大きなセルサイズまたは可変長ストレージが必要です。後者は、非常に単純なスキームが使用されている場合でも非常に効率的です（たとえば、 LZ4 スタイルの圧縮）。これは、510/2より長いギャップの頻度が非常に低いためです。

効率を上げるために、範囲をセクション（ページ）に分割し、Bツリースタイルを管理するのが最善です。

差分のエントロピーコーディング（ハフマンまたは算術コーディング）は、永続的なストレージ要件を半分未満に削減します。これは、理論上の最適に近く、利用可能な最高のパッカーを使用して圧縮されたリストまたはホイールよりも優れています。

データが圧縮されていない状態で保存されている場合、バイナリまたはテキスト番号のファイルよりもはるかにコンパクトです。 Bツリースタイルのインデックスを適切に配置すると、必要に応じてセクションをメモリに簡単にマップし、それらを非常に高速に反復処理できます。

現時点では、2を特別なケースとして扱い、すべての奇数が配列内の要素にマッピングされる配列を持っています（奇数は素数です）。これを改善するには、2と3を特別なケースとして扱い、残りの素数が6n + 1または6n-1の形式であることを認識します（つまり、p <！> gt; 3、p mod 6 = 1または5）。これはさらに一般化できます- Wikipedia を参照してください。すべての素数p <！> gt; 5、p mod 30 = 1、7、11、13、17、19、23、または29。これを使い続けると、処理時間を犠牲にして必要なメモリを削減できます（ただし、O（1）のままですが、遅いO（1））。

たぶん、素数のみを含むトライデータ構造が探しているものです。文字をインデックスとして使用する代わりに、整数桁を使用できます。この実装は、 Judy-Array sです。

ただし、O（1）の要件を満たしていません。同様のキー（数値のほとんどの部分）に対して非常にメモリ効率が高く、O（m）（m = key-長さ）最大。

事前に生成されたツリーで素数を検索する場合、それが見つかるまで、または素数の前後にあるノードに既に到達するまで木を歩くことができます。

メモリが非常に安価であることを考えると、既存のスキームよりも速度の観点からはるかに良いことはできないと思います。

より良い解決策があれば、素数定理を利用すると思いますは、Lが大きくなるにつれて、

<！>＃960;（L）/（L / ln（L））は1に近づきます。

おそらく、より良い解決策は、スキップリストのようなデータ構造で適応パッキングソリューションを使用することです。

ある種のハッシュテーブルはどうですか？

非常に優れたハッシュ関数が必要です（n mod pのようなもので、pはq最低素数の倍数ではありません-衝突の数を最小限に抑えるために十分に高い<=>を選択してください） ）。

間隔ツリーはどうですか？ http://www.geeksforgeeks.org/interval-tree/

O（1）ではないかもしれませんが、非常に高速です。多分O（log（p（n）））のように、p（n）は数nまでの素数です。このようにすると、必要なメモリは素数の数だけに比例し、メモリコストが大幅に削減されます。

たとえば、p1で素数を見つけ、p2で次の素数を見つけたとします。 間隔（p1、p2）などを挿入し、その範囲内の任意の数の検索を実行すると、この間隔が返され、ケースの答えとなるp2を返すことができます。

Mersenne または他の簡単に表現できる素数がどれかを判断できる場合、該当する数値にフラグを付けてその表現を使用することで、数ビットを節約できる場合があります。

また、数値を前の数値との差として保存するのはどうですか？その場合、サイズはそれほど速くはなりません（ただし、ルックアップは遅くなります）。上記のアプローチと組み合わせると、メルセンヌプライムと最後のメルセンヌプライムとの差を保存できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top