本文旨在解决在 Python 中搜索满足特定条件的素数组合时遇到的性能瓶颈问题。通过利用 Numba 库的即时编译功能，大幅提升代码执行效率，从而在合理时间内找到符合要求的素数组合。文章将详细介绍如何使用 Numba 优化素数判定、组合生成等关键步骤，并提供完整的代码示例和性能分析。
问题描述我们需要在一个素数列表中，寻找满足以下条件的五个素数 (p1, p2, p3, p4, p5) 的组合：
- p1 < p2 < p3 < p4 < p5
- 任意两个素数组合 (例如 p1 和 p2) 形成的两位数 (p1p2 和 p2p1) 也必须是素数。
- 这五个素数的和必须大于 100,000，并且是满足以上条件的最小和。
直接使用 Python 实现这个搜索算法可能会非常缓慢，因为涉及大量的素数判定和组合生成。因此，我们需要寻找一种优化方法来提高代码的执行效率。
解决方案：利用 Numba 进行优化Numba 是一个 Python 的即时 (JIT) 编译器，它可以将 Python 代码编译成机器码，从而显著提高代码的执行速度。Numba 特别擅长优化数值计算密集型的代码，非常适合解决我们遇到的素数搜索问题。
以下是使用 Numba 优化后的代码示例：
PIA
全面的AI聚合平台，一站式访问所有顶级AI模型
226
查看详情
import numpy as np
from numba import njit, prange
@njit
def prime(a):
"""
判断一个数是否为素数.
"""
if a < 2:
return False
for x in range(2, int(a**0.5) + 1):
if a % x == 0:
return False
return True
@njit
def str_to_int(s):
"""
将字符串转换为整数.
"""
final_index, result = len(s) - 1, 0
for i, v in enumerate(s):
result += (ord(v) - 48) * (10 ** (final_index - i))
return result
@njit
def generate_primes(n):
"""
生成小于等于 n 的所有素数.
"""
out = []
for i in range(3, n + 1):
if prime(i):
out.append(i)
return out
@njit(parallel=True)
def get_comb(n=100_000):
# generate all primes < n
primes = generate_primes(n)
n_primes = len(primes)
# generate all valid combinations of primes
combs = np.zeros((n_primes, n_primes), dtype=np.uint8)
for i in prange(n_primes):
for j in prange(i + 1, n_primes):
p1, p2 = primes[i], primes[j]
c1 = str_to_int(f"{p1}{p2}")
c2 = str_to_int(f"{p2}{p1}")
if not prime(c1) or not prime(c2):
continue
combs[i, j] = 1
all_combs = []
for i_p1 in prange(0, n_primes):
for i_p2 in prange(i_p1 + 1, n_primes):
if combs[i_p1, i_p2] == 0:
continue
for i_p3 in prange(i_p2 + 1, n_primes):
if combs[i_p1, i_p3] == 0:
continue
if combs[i_p2, i_p3] == 0:
continue
for i_p4 in prange(i_p3 + 1, n_primes):
if combs[i_p1, i_p4] == 0:
continue
if combs[i_p2, i_p4] == 0:
continue
if combs[i_p3, i_p4] == 0:
continue
for i_p5 in prange(i_p4 + 1, n_primes):
if combs[i_p1, i_p5] == 0:
continue
if combs[i_p2, i_p5] == 0:
continue
if combs[i_p3, i_p5] == 0:
continue
if combs[i_p4, i_p5] == 0:
continue
p1, p2, p3, p4, p5 = (
primes[i_p1],
primes[i_p2],
primes[i_p3],
primes[i_p4],
primes[i_p5],
)
ccomb = np.array([p1, p2, p3, p4, p5], dtype=np.int64)
if np.sum(ccomb) < n:
continue
all_combs.append(ccomb)
print(ccomb)
break
return all_combs
all_combs = np.array(get_comb())
print()
print("Minimal combination:")
print(all_combs[np.sum(all_combs, axis=1).argmin()]) 代码解释：
- @njit 装饰器: 这个装饰器告诉 Numba 将被装饰的函数编译成机器码。
- prime(a) 函数: 判断一个数是否为素数。
- str_to_int(s) 函数: 将字符串转换为整数。这个函数是为了将两个素数拼接成一个整数。
- generate_primes(n) 函数: 生成小于等于 n 的所有素数。
-
get_comb(n) 函数: 这个函数是核心，它生成所有满足条件的素数组合。
- 首先，生成小于 n 的所有素数。
- 然后，生成一个二维数组 combs，用于存储任意两个素数组合是否满足 "组合后也是素数" 的条件。
- 最后，使用嵌套循环遍历所有可能的素数组合，并检查它们是否满足所有条件。
- @njit(parallel=True) 启用并行计算，进一步加速代码执行。prange 是 Numba 提供的并行循环。
- Numba 装饰器: 使用 @njit 装饰器可以显著提高代码的执行速度。
- 数据类型: 使用 numpy.uint8 和 numpy.int64 等指定数据类型，可以帮助 Numba 更好地优化代码。
- 并行计算: 使用 @njit(parallel=True) 和 prange 可以利用多核 CPU 并行执行代码。
- 避免 Python 对象: 尽量避免在 Numba 编译的函数中使用 Python 对象，因为这会降低代码的执行速度。例如，使用 numpy 数组代替 Python 列表。
使用 Numba 优化后的代码，执行速度得到了显著提升。在我的测试环境中 (AMD 5700X)，原始代码可能需要几个小时才能完成计算，而使用 Numba 优化后的代码只需要 1 分钟 20 秒左右。
注意事项- Numba 并非适用于所有 Python 代码。它最适合优化数值计算密集型的代码。
- 在使用 Numba 时，需要注意数据类型和 Python 对象的使用，以确保代码能够被有效地优化。
- 在实际应用中，可以根据具体情况调整 Numba 的优化选项，以获得最佳的性能。
通过使用 Numba 库，我们可以显著提高 Python 代码的执行速度，从而解决在素数搜索等问题中遇到的性能瓶颈。本文提供了一个完整的代码示例和性能分析，希望能够帮助读者更好地理解和应用 Numba 优化技术。
以上就是使用 Numba 优化 Python 嵌套列表搜索：寻找满足特定条件的素数组合的详细内容，更多请关注知识资源分享宝库其它相关文章！
相关标签： python app amd Python numpy 数据类型 字符串 循环 对象 算法 低代码 大家都在看： Python怎么获取CPU核心数_os与multiprocessing获取CPU核心数 python人马兽系列 python人马兽系列的主要内容 Python怎么创建虚拟环境_Python虚拟环境创建与管理教程 python如何计算列表的长度_python使用len()函数获取列表长度 python怎么判断一个变量的类型_python变量类型判断方法
发表评论:
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。