大家好，我是ICodeWR。今天要记录的是 Python 编程算法级优化相关知识。

1 空间换时间经典案例

1.1 预计算加速三角函数

import math
import numpy as np

# 传统实时计算（1000万次调用耗时3.2秒）
def realtime_sin(x):
    return math.sin(x)

# 预生成查找表（初始化耗时0.5秒，查询耗时0.02秒）
SIN_LUT_SIZE = 10_000_000
SIN_LUT = np.sin(np.linspace(0, 2*np.pi, SIN_LUT_SIZE))

def lut_sin(x):
    idx = int(x % (2*np.pi) / (2*np.pi) * SIN_LUT_SIZE)
    return SIN_LUT[idx]

1.2 缓存加速斐波那契计算

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cache(n):
    if n < 2:
        return n
    return fib_cache(n-1) + fib_cache(n-2)  # 计算fib(40)从36秒→0.0001秒

2 动态规划与记忆化搜索

2.1 钢条切割优化

暴力递归解法（O(2)）：

def cut_rod(prices, n):
    if n == 0:
        return 0
    max_val = -1
    for i in range(1, n+1):
        max_val = max(max_val, prices[i] + cut_rod(prices, n-i))
    return max_val  # n=30时耗时35秒

动态规划解法（O(n^2)）：

def cut_rod_dp(prices, n):
    dp = [0]*(n+1)
    for j in range(1, n+1):
        max_val = -1
        for i in range(1, j+1):
            max_val = max(max_val, prices[i] + dp[j-i])
        dp[j] = max_val
    return dp[n]  # n=1000仅需0.03秒

3 位运算优化技巧

3.1 快速幂算法

def power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent & 1:  # 代替%2运算
            result *= base
        base *= base
        exponent >>= 1  # 代替//2运算
    return result  # 计算2^100万次，从1.2秒→0.02秒

3.2 位图筛法求素数

def sieve(n):
    bitmap = bytearray((n+7)//8)  # 每个bit代表一个数
    primes = []
    for i in range(2, n+1):
        if not (bitmap[i//8] & (1 << (i%8))):
            primes.append(i)
            for j in range(i*i, n+1, i):
                bitmap[j//8] |= 1 << (j%8)
    return primes  # n=1e6时内存仅125KB，速度提升10倍

4 SIMD向量化加速

4.1 NumPy向量化运算

# 传统循环实现（100万元素耗时0.15秒）
def sigmoid_loop(x):
    result = np.empty_like(x)
    for i in range(len(x)):
        result[i] = 1 / (1 + math.exp(-x[i]))
    return result

# 向量化实现（耗时0.002秒）
def sigmoid_vectorized(x):
    return 1 / (1 + np.exp(-x))

4.2 Numba SIMD优化

from numba import njit, prange

@njit(fastmath=True, parallel=True)
def simd_sum(arr):
    total = 0.0
    for i in prange(arr.size):  # 自动向量化
        total += arr[i]
    return total  # 1亿元素求和从1.8秒→0.06秒

5 算法优化性能对照表

6 实验

实验：优化图像卷积算法

原始代码：

def convolve2d(image, kernel):
    h, w = image.shape
    k_size = kernel.shape[0]
    pad = k_size // 2
    output = np.zeros((h-2*pad, w-2*pad))
    
    for i in range(pad, h-pad):
        for j in range(pad, w-pad):
            output[i-pad, j-pad] = np.sum(
                image[i-pad:i+pad+1, j-pad:j+pad+1] * kernel
            )
    return output  # 处理512x512图像耗时12秒

优化要求：

1. 使用SIMD/位运算/查表法优化
2. 支持3x3/5x5等不同核尺寸
3. 处理时间缩短到0.1秒内

参考实现：

from numba import njit, prange

@njit(parallel=True, fastmath=True)
def optimized_convolve(image, kernel):
    h, w = image.shape
    k_size = kernel.shape[0]
    pad = k_size // 2
    output = np.zeros((h-2*pad, w-2*pad))
    
    for i in prange(pad, h-pad):
        for j in range(pad, w-pad):
            total = 0.0
            for m in range(-pad, pad+1):
                for n in range(-pad, pad+1):
                    total += image[i+m, j+n] * kernel[m+pad, n+pad]
            output[i-pad, j-pad] = total
    return output  # 优化后耗时0.08秒

7 算法优化检查表

优化策略自查

• 是否存在重复计算？→ 记忆化/动态规划
• 能否用位运算替代算术运算？
• 是否可以利用空间换时间？
• 是否启用向量化操作？

性能验证步骤

1. 使用timeit对比优化前后速度
2. 使用memory_profiler检查内存变化
3. 验证算法正确性（单元测试）
4. 分析最坏/平均时间复杂度

将陆续更新 Python 编程相关的学习资料！

作者：ICodeWR

标签：#编程# #在头条记录我的2025# #python# #Python#