python - Python での大きな計算のメモリ使用量の処理

Question

Python で計算をしようとしていますが、メモリが不足しています。したがって、メモリを解放するためにファイルを読み書きしたいと考えています。非常に大きなリストオブジェクトのようなものが必要なので、ファイル内のオブジェクトごとに行を書き、メモリではなくその行に読み書きすることを考えました。行番号をインデックスとして使用するため、行の順序は重要です。そのため、他の行を移動せずにPythonで行を置き換える方法を考えていました（実際、行を移動しても、期待する場所に戻る限り問題ありません）。

編集

私は友人を助けようとしていますが、それはPythonで私よりも悪いか同じです。このコードは、指定された非素数を割る最大の素数を見つけることになっています。このコードは、100 万のような数字までは機能しますが、死んだ後、数字のリストを作ろうとすると、私の記憶は尽きてしまいます。

# a comes from a user input
primes_upper_limit = (a+1) / 2
counter = 3L
numbers = list()
while counter <= primes_upper_limit:
    numbers.append(counter)
    counter += 2L

counter=3
i=0
half = (primes_upper_limit + 1) / 2 - 1
root = primes_upper_limit ** 0.5
while counter < root:
    if numbers[i]:
        j = int((counter*counter - 3) / 2)
        numbers[j] = 0
        while j < half:
            numbers[j] = 0
            j += counter
    i += 1
    counter = 2*i + 3
primes = [2] + [num for num in numbers if num]
for numb in reversed(primes):
    if a % numb == 0:
        print numb
        break

別の編集

インデックスごとに異なるファイルを書き込むのはどうですか? たとえば、長い整数のファイル名を持つ何十億ものファイルと、ファイル内の数字だけですか?

Answer 1

a の最大の素約数を求めます。( Project Euler Question 3 ) 現在選択しているアルゴリズムと実装では、次のようにします。

1. 範囲内のすべての候補素数のリストを生成numbersします (3 <= n <= sqrt(a)、または現在のように (a+1)/2)
2. リストをふるいにnumbersかけ、素数のリストを取得します {p} <= sqrt(a)
3. 試行分割: a の割り切れる可能性を各 p でテストします。a のすべての素約数 {q} を格納します。
4. すべての除数 {q} を出力します。最大のものだけが必要です。

このアルゴリズムに関する私のコメントは以下のとおりです。オーウェンと私がコメントしているように、ふるい分けと試行分割は真剣にスケーラブルなアルゴリズムではありません。大きい (10 億、または 1 兆) 場合は、実際に NumPy を使用する必要があります。とにかく、このアルゴリズムの実装に関するいくつかのコメント:

1. あなたがするように (a+1)/2 ではなく、 √a ,までテストするだけでよいことをint(math.sqrt(a))ご存知ですか?
2. 候補の膨大なリストを作成しnumbers、素数をふるいにかける必要はありません。数字のリストはスケーラブルではありません。リストprimesを直接構築するだけです。while/for ループとxrange(3,sqrt(a)+2,2)(イテレータを提供します) を使用できます。あなたが言及したように、xrange() は でオーバーフローし2**31Lますが、sqrt 観測と組み合わせると、最大2**62
3. 一般に、これは a の素分解を取得するよりも劣ります。つまり、素数 p | を見つけるたびに。a、残りの因子a/pまたはa/p²またはa/p³などをふるい続ける必要があるだけです） 。非常に大きな素数 (または疑似素数) のまれなケースを除いて、これにより、作業している数値の大きさが大幅に減少します。
4. また、素数 {p} のリストを一度だけ生成する必要があります。その後、保存して検索を行い、再生成しません。generate_primes(a)だから私はから分離しfind_largest_prime_divisor(a)ます。分解は非常に役立ちます。

これが私のコードの書き直しですが、ふるいにかけられたリストを保持しているため、パフォーマンスは依然として数十億 (a > 10**11 +1) 低下します。素数の list の代わりにcollections.dequeを使用して、より高速な O(1) append() 操作を取得できますが、これはマイナーな最適化です。

# Prime Factorization by trial division

from math import ceil,sqrt
from collections import deque

# Global list of primes (strictly we should use a class variable not a global)
#primes = deque()
primes = []

def is_prime(n):
    """Test whether n is divisible by any prime known so far"""
    global primes
    for p in primes:
         if n%p == 0:
             return False #  n was divisible by p
    return True # either n is prime, or divisible by some p larger than our list    
def generate_primes(a):
    """Generate sieved list of primes (up to sqrt(a)) as we go"""
    global primes
    primes_upper_limit = int(sqrt(a))
    # We get huge speedup by using xrange() instead of range(), so we have to seed the list with 2
    primes.append(2)
    print "Generating sieved list of primes up to", primes_upper_limit, "...",
    # Consider prime candidates 2,3,5,7... in increasing increments of 2
    #for number in [2] + range(3,primes_upper_limit+2,2):
    for number in xrange(3,primes_upper_limit+2,2):
        if is_prime(number): # use global 'primes'
            #print "Found new prime", number
            primes.append(number) # Found a new prime larger than our list
    print "done"    
def find_largest_prime_factor(x, debug=False):
    """Find all prime factors of x, and return the largest."""
    global primes
    # First we need the list of all primes <= sqrt(x)    
    generate_primes(x)
    to_factor = x # running value of the remaining quantity we need to factor
    largest_prime_factor = None
    for p in primes:
        if debug: print "Testing divisibility by", p
        if to_factor%p != 0:
            continue
        if debug: print "...yes it is"
        largest_prime_factor = p
        # Divide out all factors of p in x (may have multiplicity)
        while to_factor%p == 0:
            to_factor /= p
        # Stop when all factors have been found
        if to_factor==1:
            break
    else:
        print "Tested all primes up to sqrt(a), remaining factor must be a single prime > sqrt(a) :", to_factor
    print "\nLargest prime factor of x is", largest_prime_factor
    return largest_prime_factor

Answer 2

Project Euler #3 のように 12 桁しかない数の場合、手の込んだ整数因数分解法は必要なく、中間結果をディスクに保存する必要もありません。このアルゴリズムを使用して、n の因数を見つけます。

1. f = 2 に設定します。
2. n = 1 の場合、停止します。
3. f * f > n の場合、n を出力して停止します。
4. n を f で割り、商 q と剰余 r の両方を保持します。
5. r = 0 の場合、q を出力し、n を q で割り、ステップ 2 に進みます。
6. そうでない場合は、f を 1 増やして、手順 3 に進みます。

これは、残りの補因子が素数であることを示す平方根に到達するまで、すべての整数で除算を試行するだけです。各因子は、見つかったとおりに出力されます。

Answer 3

pytablesは、膨大な量のデータを処理および保存するのに優れています。ただし、最初にsmciの回答にコメントを実装して、保存する必要がある数値の量を最小限に抑えます。