素数を見つけるためのアルゴリズム(sieve of Eratosthenes
)を構築しましたが、多くのメモリを消費します。現在のところ、私のコードは、時間を監視するためにデコレータを使用しています。私のプログラムで消費されるメモリを評価するために、同様のデコレータを用意してください。デコレータでプログラムが消費するメモリを監視する方法
import math
import time
def time_usage(func):
def wrapper(*args, **kwargs):
beg_ts = time.time()
result = func(*args, **kwargs)
end_ts = time.time()
print("[INFO] elapsed time: %f" % (end_ts - beg_ts))
return result
return wrapper
@time_usage
def find_prime(n):
is_composite = [False for _ in range(n + 1)]
# Cross out multiples of 2
for i in range(4, n, 2):
is_composite[i] = True
# Cross out multiples of primes found so far
next_prime = 3
stop_at = math.sqrt(n)
while next_prime < stop_at:
# Cross out multiples of this prime
for i in range(next_prime * 2, n, next_prime):
is_composite[i] = True
# Move the next prime, skipping the even number
next_prime += 2
while next_prime <= n and is_composite[next_prime]:
next_prime += 2
# Copy the primes into a list
primes = []
for i in range(2, n):
if not is_composite[i]:
primes.append(i)
return primes
if __name__ == '__main__':
print(find_prime(100000))
第三者のライブラリを使用してメモリ使用量をプロファイルすることをお勧めします。私はmemory_profiler
を使っていましたが、良いデコレータ実装を提供していますが、time_usage
デコレータとメモリプロファイルの両方を使用することはできません。
ここでは、@profile
が実際にtime_usage
というメモリのプロファイリングを行っていることがわかります。
import math
import time
from memory_profiler import profile
def time_usage(func):
def wrapper(*args, **kwargs):
beg_ts = time.time()
result = func(*args, **kwargs)
end_ts = time.time()
print("[INFO] elapsed time: %f" % (end_ts - beg_ts))
return result
return wrapper
@profile
@time_usage
def find_prime(n):
is_composite = [False for _ in range(n + 1)]
# Cross out multiples of 2
for i in range(4, n, 2):
is_composite[i] = True
# Cross out multiples of primes found so far
next_prime = 3
stop_at = math.sqrt(n)
while next_prime < stop_at:
# Cross out multiples of this prime
for i in range(next_prime * 2, n, next_prime):
is_composite[i] = True
# Move the next prime, skipping the even number
next_prime += 2
while next_prime <= n and is_composite[next_prime]:
next_prime += 2
# Copy the primes into a list
primes = []
for i in range(2, n):
if not is_composite[i]:
primes.append(i)
return primes
if __name__ == '__main__':
print(find_prime(100000))
このプロデュース:
ライン#メモリ使用量増分ライン内容
7 27.4 MiB 0.0 MiB def wrapper(*args, **kwargs): 8 27.4 MiB 0.0 MiB beg_ts = time.time() 9 28.3 MiB 0.9 MiB result = func(*args, **kwargs) 10 28.3 MiB 0.0 MiB end_ts = time.time() 11 28.3 MiB 0.0 MiB print("[INFO] elapsed time: %f" % (end_ts - beg_ts)) 12 28.3 MiB 0.0 MiB return result
[2、3、5、7、11、13、17、19、23、29 、31、37、41、43、47、53、59、61、 67,71,73,79,79,89,97,101,103,107,109,113,127,131,137, 。 ..、99989、99991]
自分のプライムシーブを書くことは良い練習ですが、[Nの下のすべての素数をリストする最速の方法](http://stackoverflow.com/q/2068372/4014959)でコードを調べることに興味があります。そのページはかなり古く、Python 2にはたくさんのコードがありますが、まだIMHOの価値はあります。 Robert William Hanksのスクリプトは非常に優れており、Python 3に変換するのは非常に簡単です。 –
ありがとうございます、このオプションについては確かに調査しますが、この質問ではメモリと時間の両方を簡単に監視することに興味がありますさまざまなアルゴリズムの実装をベンチマークすることができ、異なる実行時間の実際の影響を見ることができます。例えば、このコードは 'O(N log(log N))'を持ちますが、数値が大きすぎると不当な量のメモリを使います。 – Michael
。私のコメントはあなたのプロファイリングの質問には触れていませんでした。私はあなたが他の主要なふるい分けの戦略をチェックしたいと思っていただけです。 :)と、そのノートで、あまりにも多くのRAMを消費せずに大量を処理するには、[この1年前に書いた]セグメント化されたふるいが便利です(http://stackoverflow.com/a/26440674/4014959) 。そして本当に大きな単一数字の素数性をテストするには、[Miller-Rabinアルゴリズム](http://math.stackexchange.com/a/1638487/207316)を見てください。 –