我使用的是python2.7
在我编写的两个Eratosthenes erat()和erat2()的Sieve实现中,erat2()的好处是,在第二次运行erat2()时,它会以相对较少的时间给出结果。你知道吗
def erat2(num, isprime = [2]):
if num > len(isprime) + 2:
last_original = len(isprime) + 2
isprime += [num for num in xrange(last_original ,num + 1)]
for i in xrange(2,num + 1):
if isprime[i-2]:
if i <= last_original:
j = last_original//i + 1
else:
j = 2
temp = j * i
while temp <= num:
isprime[temp-2] = 0
j += 1
temp = j * i
return filter(lambda x: x != 0, isprime[:num - 1])
def erat(num):
isprime = [num for num in xrange(2,num + 1)]
for i in xrange(2,num + 1):
if isprime[i-2]:
j = 2
temp = j * i
while temp <= num:
isprime[temp-2] = 0
j += 1
temp = j * i
return filter(lambda x: x != 0, isprime)
import time
def t():
num = 100000000
i = 10
while i < num:
s = time.time()
erat2(i)
x = time.time() - s
print "%10d %10f" %(i,x),
s = time.time()
erat(i)
y = time.time() - s
print " %10f" %(y)
i *= 10
为了证明在第二次运行代码时,结果会快得多,这里给出了一些时间分析。第一列是测试输入。第二列是erat2()的计时,第三列是erat()的计时。很明显,在第二次运行中时间减少了7倍。你知道吗
>>> t()
10 0.000000 0.000000
100 0.000000 0.000000
1000 0.000000 0.000000
10000 0.010000 0.010000
100000 0.100000 0.110000
1000000 1.231000 1.410000
10000000 13.605000 15.081000
>>> t()
10 0.000000 0.000000
100 0.000000 0.000000
1000 0.000000 0.000000
10000 0.000000 0.020000
100000 0.020000 0.140000
1000000 0.170000 1.550000
10000000 1.770000 15.752000
我面临的问题是,在这个测试输入之后,内存使用率会急剧上升。你知道吗
编辑:
我发现对函数erat()和erat2()都进行了一些优化,以提高速度。将lambda函数从
lambda x: x != 0
至
lambda x: x
结果相同,但速度稍快。num=10000000时快一秒。你知道吗
编辑2:
使用了vartec和btilly的建议。将erat()改进为erat3()。下面是改进的实现和时间检查。还发现在xrange函数中放置表达式会导致性能损失。添加变量以提高性能。你知道吗
def erat3(num):
''' Improves Sieve of eratosthenes '''
#REQUIRES MATH MODULE
if num < 2:
return []
isprime = [num for num in xrange(3,num + 1,2)]
#temp2's expression placed in xrange function => performance-loss
temp2 = int(math.sqrt(num)) + 1
for i in xrange(3, temp2 ,2):
if isprime[(i-3)/2]:
j = 3
temp = j * i
while temp <= num:
isprime[(temp-3)/2] = 0
j += 2
temp = j * i
return [2] + filter(lambda x: x, isprime)
erat()和erat3()的计时
>>> t()
10 0.000000 0.000000
100 0.000000 0.000000
1000 0.000000 0.000000
10000 0.010000 0.010000
100000 0.110000 0.040000
1000000 1.241000 0.530000
10000000 14.131000 6.111000
在内存和性能之间进行折衷是很常见的。哪个对你更重要取决于你的申请。你知道吗
在本例中,我建议通过使用位向量(请参见https://pypi.python.org/pypi/BitVector了解详细信息)来减轻这种负担,以便您创建的数据结构更加紧凑。你知道吗
同样在这种情况下,特殊的大小写2和仅存储奇数位将使性能加倍,内存减半,代价是代码复杂度略高。这可能是值得的。你知道吗
可以对isprime数组使用单个位。Python并没有提供一种真正快速的方法来操作位,但是一种简单的方法是使用long。你知道吗
用这个来检查一个数字是否已经过筛选
下面是如何在对第二个函数进行最小更改的情况下应用它
在局部变量中存储
(1 << num)
可能是值得的,这样可以避免反复构建它。正如@btilly所指出的,只需做一点额外的工作,就可以通过跟踪奇数来节省一半的空间。你知道吗相关问题 更多 >
编程相关推荐