パイソン：パフォーマンスループして大きな配列を操作するとき

Question

私の質問である2倍：

1. オーバーの両方を効率的ループへの道があり、ループを操作する例のために列挙し、使用 配列を操作します同じ時刻に に？
2. Pythonでメモリ最適化バージョンの配列がありますか？ Sieve of Eratosthenesと - （RNG 2） Iの範囲内の素数を見つけるアルゴリズムを行った

（numpyのは、指定されたタイプの小さいアレイを作成するなど）。

メモ：2〜1,000,000の素数を検索すると問題が存在しません（合計実行時間も1秒未満です）。数千万と数億のうち、これは傷つき始めます。これまでテーブルをすべての自然数から奇数に変えると、私が検索できる最大範囲は4億（奇数で2億）でした。

forループの代わりには、少なくとも現在のアルゴリズムではパフォーマンスを低下させます。
numpyの型変換と小さいアレイを作成することができる、それは実際

oddTable = [0] * size 

及び使用の代わりに

oddTable = np.int8(np.zeros(size)) 

除いて、同じコードで処理するために約2倍の時間を要しながら配列型を保持するために、「プライム」と「プライムしない」の値を割り当てます。擬似コードを使用して

、アルゴリズムは次のようになります。

oddTable = [0] * size # Array representing odd numbers excluding 1 up to rng 

for item in oddTable: 
    if item == 0:  # Prime, since not product of any previous prime 
     set item to "prime" 
     set every multiple of item in oddTable to "not prime" 

Pythonは、リスト内のすべての項目をループするときに特にきちんとした言語ですが、インデックスとして

for i in range(1000) 

を言います

は、ループ中に操作することはできません。使用するイテレートを生成するために、範囲を数回変換する必要がありました。コードでは、 "P"は素数を、 "_"は素数ではなく0をチェックしません。

num = 1     # Primes found (2 is prime) 
size = int(rng/2) - 1 # Size of table required to represent odd numbers 
oddTable = [0] * size # Array with odd numbers \ 1: [3, 5, 7, 9...] 

new_rng = int((size - 1)/3) # To go through every 3rd item 
for i in range(new_rng):   # Eliminate no % 3's 
    oddTable[i * 3] = "_" 
oddTable[0] = "P"    # Set 3 to prime 
num += 1 

def act(x):    # The actual integer index x in table refers to 
    x = (x + 1) * 2 + 1 
return x 
     # Multiples of 2 and 3 eliminated, so all primes are 6k + 1 or 6k + 5 
     # In the oddTable: remaining primes are either 3*i + 1 or 3*i + 2 
     # new_rng to loop exactly 1/3 of the table length -> touch every item once 
for i in range(new_rng): 
    j = 3*i + 1     # 3*i + 1 
    if oddTable[j] == 0: 
     num += 1 
     oddTable[j] = "P" 
     k = act(j) 
     multiple = j + k # The odd multiple indexes of act(j) 
     while multiple < size: 
      oddTable[multiple] = "_" 
      multiple += k 
    j += 1       # 3*i + 2 
    if oddTable[j] == 0: 
     num += 1 
     oddTable[j] = "P" 
     k = act(j) 
     multiple = j + k 
     while multiple < size: 
      oddTable[multiple] = "_" 
      multiple += k 

Answer 1

各チャンクを容易に把握することができるように、あなたのコードがよりニシキヘビ作る小さな塊（機能）で、あなたのアルゴリズムを分割します。

私の2番目のコメントはあなたを驚かせるかもしれません：Pythonには "電池が含まれています"が付属しています。 ErathostenesのSieveをプログラミングするために、なぜ配列を明示的に操作してコードを汚染する必要がありますか？その目的のために用意されたstandard memoize decoratorを使用して、機能（例：is_prime）を作成しないでください。 （2.7の使用を強くお勧めする場合はmemoization library for python 2.7も参照してください）。

上記の2つのアドバイスの結果は、「最も効率的」ではないかもしれませんが、（正確な問題で経験したように）うまく機能し、すっきりとしたコードを素早く作成してプログラマーの時間（作成とメンテナンスの両方）。