在Python中进行多处理以查找素数

Question

在Python 3中，我有这个任务，我需要使用multiprocessing在区间[a,b]中找到素数。

让我们以区间[0,30]为例，使用3个进程，我有三个区间[ai,bi]:[0.10],[10,20],[20,30]

下面是我的代码:

import multiprocessing
import time
def isprime(num):
if num > 1:
for i in range(2, num):
if (num % i) != 0:
pass
else:
return num
if __name__ == "__main__":
pool = multiprocessing.Pool(3)
start_time = time.perf_counter()
result = pool.map(isprime, range(0,30))
finish_time = time.perf_counter()
print(f"Program finished in {finish_time-start_time} seconds")
print(result)

这是期望的输出:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

这是我得到的:

[None, None, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

Answer 1

你有三个问题:

1. 您的isprime函数将隐式返回None参数<= 1，但否则将始终执行for语句的else子句并返回传递的参数。
2. 假设isprime将返回传递的参数，如果它是素数或None，如果它不是，那么你需要过滤掉isprime的None返回值。
3. 你并没有像你所说的那样把间隔分成范围来解决这个问题。我会在代码后面的注释中解决这个问题。

import multiprocessing
import time
def isprime(num):
if num < 2:
return None
for i in range(2, num):
if (num % i) == 0:
return None
else:
return num
if __name__ == "__main__":
pool = multiprocessing.Pool(3)
start_time = time.perf_counter()
result = list(filter(lambda x: x is not None, pool.map(isprime, range(0,30))))
finish_time = time.perf_counter()
print(f"Program finished in {finish_time-start_time} seconds")
print(result)

打印:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

一般评论

你的isprime函数可以大大改进(做一个更好的实现谷歌)。例如:

def isprime(num):
from math import sqrt, floor
if num < 2: return None
if num == 2: return num
if num % 2 == 0: return None
for d in range(3, floor(sqrt(num)) + 1, 2):
if num % d == 0: return None
return num

但是正如你所看到的，随着参数n的增加，主循环需要更多的迭代来证明传递的参数是素数。

您可以处理此问题的方法是实现某种版本的Sieve of Eraosthenes算法，该算法可以有效地生成一系列素数，然后您将传递给该函数一个范围的数字，筛函数将返回在该范围内找到的所有素数。当然，您会将初始range(0, 30)分解为3个子范围的列表，即[range(0, 10), range(10, 20), range(20, 30)]，这将传递给您的map方法。

但是即使是标准的Sieve算法也必须从2开始生成素数，所以即使你传递参数range(10, 20)给它，函数也必须重复传递参数range(0, 10)时所做的工作。

因此，使用对isprime方法的多次调用对于查找一系列素数是没有效率的，但是Sieve算法从多处理实现中没有获得任何好处(多处理实际上会损害性能)。解决此问题的最佳方法是使用非多处理筛。