Numba加速列表搜索与素数组合查找

下载万磁搜索绿色版

从现在开始，我们要努力学习啦！今天我给大家带来《Numba优化嵌套列表搜索与素数组合查找》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

本文旨在提供一种使用Numba优化Python嵌套列表搜索的方法，特别是在处理大量素数时。通过预计算有效的素数组合，并利用Numba的即时编译功能，可以显著提高搜索效率，从而在合理的时间内找到满足特定条件的最小素数集合。文章将详细介绍算法实现，并提供可执行的示例代码。

在处理大规模数据时，Python的循环和条件判断可能会成为性能瓶颈。对于嵌套列表搜索，尤其是在涉及到素数判断等计算密集型操作时，优化变得尤为重要。本文将介绍如何使用Numba库来加速这类搜索过程，以解决寻找满足特定条件的素数组合问题。

问题描述

我们需要在一个素数列表中找到满足以下条件的五个素数：

1. p1 < p2 < p3 < p4 < p5
2. 任意两个素数组合（如p1和p2组成的p1p2和p2p1）也必须是素数。
3. sum(p1..p5) 是满足上述条件的最小素数和，且大于 100,000。

解决方案：Numba加速

Numba是一个Python的即时(JIT)编译器，它可以将Python和NumPy代码转换为快速的机器码。通过使用Numba，我们可以显著提高代码的执行速度，尤其是在循环和数值计算方面。

以下是使用Numba优化的代码示例：

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):
    """
    生成满足条件的素数组合
    """
    # 生成所有小于n的素数
    primes = generate_primes(n)
    n_primes = len(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()])

代码解释

1. @njit 装饰器: 这个装饰器告诉Numba将函数编译为机器码，从而提高执行速度。
2. prime(a) 函数: 用于判断一个数是否为素数。
3. str_to_int(s) 函数: 用于将字符串转换为整数，用于拼接两个素数。
4. generate_primes(n) 函数: 用于生成小于n的所有素数。
5. get_comb(n) 函数:
   • 首先，生成小于 n 的所有素数。
   • 然后，创建一个二维数组 combs，用于存储所有有效的素数组合。如果 primes[i] 和 primes[j] 的组合满足条件（即 primes[i]primes[j] 和 primes[j]primes[i] 都是素数），则 combs[i, j] 设置为 1。
   • 最后，遍历所有可能的素数组合，找到满足条件的最小素数和。prange是range的并行版本，由Numba提供，可以利用多核CPU加速循环。

优化技巧

• 预计算有效组合: 通过预先计算所有有效的素数组合，可以避免在搜索过程中重复计算。
• 使用Numba: 使用Numba的JIT编译功能可以显著提高代码的执行速度。
• 并行计算: 使用prange可以利用多核CPU加速循环。

注意事项

• Numba对某些Python特性支持有限，因此在使用Numba时需要注意代码的兼容性。
• Numba的编译过程需要一定的时间，因此在首次运行Numba编译的函数时可能会有一定的延迟。

总结

通过使用Numba优化Python嵌套列表搜索，我们可以显著提高代码的执行速度，从而在合理的时间内找到满足特定条件的最小素数集合。这种优化方法可以应用于其他类似的搜索问题，例如在图形搜索、数据挖掘等领域。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Numba加速列表搜索与素数组合查找》文章吧，也可关注golang学习网公众号了解相关技术文章。