本文旨在解决在 Python 中搜索满足特定条件的素数组合时遇到的性能瓶颈问题。通过利用 Numba 库的即时编译功能，大幅提升代码执行效率，从而在合理时间内找到符合要求的素数组合。文章将详细介绍如何使用 Numba 优化素数判定、组合生成等关键步骤，并提供完整的代码示例和性能分析。
问题描述
我们需要在一个素数列表中，寻找满足以下条件的五个素数 (p1, p2, p3, p4, p5) 的组合：
p1 任意两个素数组合 (例如 p1 和 p2) 形成的两位数 (p1p2 和 p2p1) 也必须是素数。这五个素数的和必须大于 100,000，并且是满足以上条件的最小和。
直接使用 Python 实现这个搜索算法可能会非常缓慢，因为涉及大量的素数判定和组合生成。因此，我们需要寻找一种优化方法来提高代码的执行效率。
解决方案：利用 Numba 进行优化
Numba 是一个 Python 的即时 (JIT) 编译器，它可以将 Python 代码编译成机器码，从而显著提高代码的执行速度。Numba 特别擅长优化数值计算密集型的代码，非常适合解决我们遇到的素数搜索问题。
立即学习“Python免费学习笔记（深入）”；
以下是使用 Numba 优化后的代码示例：
import numpy as npfrom numba import njit, prange@njitdef 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@njitdef 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@njitdef 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_combsall_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 嵌套列表搜索：寻找满足特定条件的素数组合的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1370648.html
微信扫一扫 
支付宝扫一扫 
