最近我一直在了解“用Python的方式”来处理列表、字典、集合等。为此,我修改了一个计算前N
个质数的函数,我们称之为“纯字典版”:
def findprimeuptoG(x):
n_primes = {}
for i in range(2, x):
if i not in n_primes.values():
n_primes[i]=i
for k, v in n_primes.items():
if i > v:
n_primes[k] += k
return sorted(n_primes)
这个函数的工作原理如下:
在字典中维护质数列表和这些质数的整数倍列表
这些倍数应该大于或等于某个整数i
如果一个数字不存在于现有质数的整数倍列表中,则它必须是一个质数,并被添加到质数列表中
从
2
(最小的质数)开始,逐步增加i,直到x
返回质数列表
如果有人能够友好地让我知道是否可以更清晰地编写此代码,请评论,我会很乐意阅读。
现在的问题是:这个函数的第一个版本不太干净,更像C语言风格:
def findprimeupto(x):
primes = []
n_primes = []
for i in range(2, x):
if i not in n_primes:
primes.append(i)
n_primes.append(i)
for j in range(len(primes)):
if i > n_primes[j]:
n_primes[j] += primes[j]
return primes
但是当我使用pypy
编译器运行时,这个第一个版本绝对是最快的:
python3:
Primes up to: 100000
Algo: Clean version , primes: 9592, time: 102.74523687362671
Algo: Dict, Set , primes: 9592, time: 58.230621337890625
Algo: **FirstVersion** , primes: 9592, time: 59.945680379867554
Algo: List of List[1] , primes: 9592, time: 71.41077852249146
Algo: List of MutableNum , primes: 9592, time: 292.3777365684509
Algo: **Pure Dict** , primes: 9592, time: 56.381882667541504
pypy (版本2.3.1):
Primes up to: 100000
Algo: Clean version , primes: 9592, time: 29.3849189281
Algo: Dict, Set , primes: 9592, time: 85.8557658195
Algo: **FirstVersion** , primes: 9592, time: 1.11557507515
Algo: List of List , primes: 9592, time: 42.2394959927
Algo: List of MutableNum , primes: 9592, time: 38.764893055
Algo: **Pure Dict** , primes: 9592, time: 110.416568995
我知道'Pure Dict'版本的性能下降是由于我在循环中没有使用迭代器,尽管'FirstVersion'获得了惊人的速度提升。
由于我们的大部分代码可能最终会在生产中编译,因此我们应该以更类似C的方式而不是Python风格来编写代码吗?
编辑:
为了消除是否应该使用列表而不是字典的任何困惑,我提交了这个函数的另一个版本,我称之为'Clean版本'。这个版本没有直接访问列表的第N个元素,而是以我认为最符合Python风格的方式对列表进行迭代(顺便说一下,这个版本和同一代码的Lisp版本最相似:)
def findprimeuptoB(x):
primes = []
n_primes = []
for i in range(2, x):
if not (i in n_primes):
primes.append(i)
n_primes.append(i)
new_n_primes = []
for prime, n_prime in zip(primes, n_primes):
if i > n_prime:
new_n_primes.append(prime + n_prime)
else:
new_n_primes.append(n_prime)
n_primes = new_n_primes
return primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
。 - Two-Bit Alchemist