利用 Python 3 线程池快速判断完数

0

Loading

Python3 的多线程实现,真的要比 C/C++、Java 什么的方便多了……
虽然在不久的将来,我的代码只有上帝能够看懂(雾)

这里用到的是线程池,任务和线程的分配问题交给线程池去管理,比单纯的 threading 多线程还要方便不少。

在 Python 3.2 之后的官方库中,提供了线程池和进程池模块,可以直接导入:

from concurrent.futures import ThreadPoolExecutor, as_completed
import time

顺便还导入了 time 模块(as_completed 后面再说)。

完数的判断逻辑其实很简单,只要一个自然数的真因子(即除了自身以外的约数)的和,恰好等于它本身,这个数就是完全数。因此我们需要将一个自然数拆分,分别判断它是否是真因子。可以利用多线程来加速计算的地方也正是这里。

先来看整除判断函数:

# 整除判断函数,也是需要多线程执行的部分
def factor(a):
if n % int(a) == 0:
buffer.append(a)

若能整除,则追加该数字到缓冲区列表中。很简单,逻辑也很清晰。

 

接下来在主线程读取键盘输入、创建必要的列表:

n = int(input("Input N:")) # 从键盘读入需要判断的数字
p = int(input("Input P:")) # 从键盘读入最大线程数量
start = time.time() # 获取程序开始执行的时间
buffer = [] # 创建缓冲区列表,用于存放可以整除的数字
task = [] # 创建任务列表,用于存放各个任务,便于之后判断各个线程的执行情况

上面的操作都完成之后,就可以提交任务到线程池了:

# 设定线程池的最大同时执行线程的数量,然后利用 for 循环将任务提交上去
with ThreadPoolExecutor(max_workers=p) as executor:
for i in range(2, n - 1):
task.append(executor.submit(factor(i)))
as_completed(task) # 等待所有线程执行完成
total = 1 # 存放数字的和,已初始化为 1 (任何自然数都可以被 1 整除)

这里的 as_completed() 函数非常重要,也非常好用。在参数中提供的线程全部执行完毕之前,它会阻塞,直到线程全部执行完成。这里直接用了它来阻塞主线程,等待上面提交到线程池中的子线程全部执行完毕后释放。

 

全部判断完成之后,留给主线程的工作就只有求和并判断输入的数字是否是完数了:

# 缓冲区所有元素求和
for q in buffer:
total += q
# 判断是否是完数
if int(total) == n:
print("True")
else:
print("False")
end = time.time() # 获取程序结束执行的时间
print("program finished in " + str((end - start)) + " seconds.")

可惜的是,Python 存在 GIL 锁,利用线程池的实现最多占用一个逻辑 CPU 核心,想用多线程实现多核并行计算在现在看来,只能是个梦想。

但是把 ThreadPoolExecutor 改成 ProcessPoolExecutor 就可以真正利用多核咯,因为这是进程池,当然代码也要再改改,只改这一处是不行的。