10

私はアトキンのふるいを実装しましたが、100,000,000 に近い素数までうまく機能します。それを超えると、メモリの問題のために故障します。

アルゴリズムでは、メモリ ベースのアレイをハード ドライブ ベースのアレイに置き換えたいと考えています。Python の "wb" ファイル関数と Seek 関数がうまくいくかもしれません。新しい車輪の発明に取り掛かる前に、誰かアドバイスをいただけますか? 最初に 2 つの問題が発生します。

  1. アトキンのふるいを「チャンク」してメモリ内のセグメントで作業する方法はありますか?
  2. アクティビティを一時停止して後で戻ってくる方法はありますか?メモリ変数をシリアル化して復元できることを示唆しています。

なぜ私はこれをしているのですか？娯楽を求め、麺を動かし続けるために年老いたオヤジ。

4

4 に答える 4

5

Python で SoA を実装するのは楽しそうに聞こえますが、実際には SoE よりも遅くなる可能性があることに注意してください。優れたモノリシック SoE 実装については、RWH の StackOverflow 投稿を参照してください。これらは、非常に基本的な実装の速度とメモリ使用量についてのアイデアを提供します。numpy バ​​ージョンは、私のラップトップで 10,000M 以上にふるいにかけます。

あなたが本当に欲しいのは、セグメント化されたふるいです。これにより、メモリの使用を合理的な制限 (たとえば、1M + O(sqrt(n))、必要に応じて減らすことができます) に制限できます。C++ での優れた議論とコードがprimesieve.orgに示されています。Python には他にもさまざまな例があります。 バーンスタインのSoAの実装である primegen は、セグメント化されたふるいとして実装されています (質問 1: はい、SoA はセグメント化できます)。これは、範囲のふるい分けと密接に関連しています (ただし同一ではありません)。これがふるいを使って 10^18 と 10^18+1e6 の間の素数をほんの一瞬で見つける方法です。すべての数をふるいにかけて 10^18+1e6 にするわけではありません。

ハードドライブを巻き込むことは、IMO、間違った方向に進んでいます。ドライブから値を読み取るよりも高速にふるい分けできるはずです (少なくとも適切な C 実装では)。範囲指定および/またはセグメント化されたふるいは、必要なことを行う必要があります.

ストレージを行うためのより良い方法がいくつかあります。私の SoE は、他のいくつかの SoE と同様に、mod-30 ホイールを使用するため、30 整数ごとに 8 つの候補があるため、30 値ごとに 1 バイトを使用します。バーンスタインの SoA は、60 個の値ごとに 2 バイトを使用して、同様の処理を行っているようです。RWH の python 実装はそこまでではありませんが、30 値あたり 10 ビットで十分に近いです。残念ながら、Python のネイティブ bool 配列は 1 ビットあたり約 10 バイトを使用しているように見えますが、numpy は 1 ビットあたり 1 バイトです。セグメント化されたふるいを使用してあまり心配しないか、Python ストレージでより効率的な方法を見つけるかのいずれかです。

于 2015-08-21T12:10:37.427 に答える
1

signalアプリケーションの終了時にハンドラーを使用してキャッチすることができます。これにより、終了する前に現在の状態を保存できます。次のスクリプトは、再起動時に継続する単純な数のカウントを示しています。

import signal, os, cPickle

class MyState:
    def __init__(self):
        self.count = 1

def stop_handler(signum, frame):
    global running
    running = False

signal.signal(signal.SIGINT, stop_handler)
running = True
state_filename = "state.txt"

if os.path.isfile(state_filename):
    with open(state_filename, "rb") as f_state:
        my_state = cPickle.load(f_state)
else:
    my_state = MyState()

while running:
    print my_state.count
    my_state.count += 1

with open(state_filename, "wb") as f_state:
    cPickle.dump(my_state, f_state)

ディスク書き込みの改善に関しては、Python 自体のファイル バッファリングを 1Mb 以上のサイズのバッファで増やしてみることができますopen('output.txt', 'w', 2**20)。withハンドラーを使用すると、ファイルがフラッシュされて閉じられることも保証されます。

于 2015-08-21T06:42:40.220 に答える