Python 编程算法级优化（python做优化算法）
大家好，我是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 算法优化性能对照表
优化技巧 | 时间复杂度变化 | 内存开销变化 | 典型加速比 |
查表法 | O(1) → O(1) | 增加查询表空间 | 100x |
动态规划 | O(2) → O(n^2) | 增加O(n)空间 | 10^6x |
位运算 | O(n) → O(n) | 减少50-90% | 5x |
向量化 | O(n) → O(n/k) | 基本不变 | 100x |
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秒
优化要求：
- 使用SIMD/位运算/查表法优化
- 支持3x3/5x5等不同核尺寸
- 处理时间缩短到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 算法优化检查表
优化策略自查
- 是否存在重复计算？→ 记忆化/动态规划
- 能否用位运算替代算术运算？
- 是否可以利用空间换时间？
- 是否启用向量化操作？
性能验证步骤
- 使用timeit对比优化前后速度
- 使用memory_profiler检查内存变化
- 验证算法正确性（单元测试）
- 分析最坏/平均时间复杂度
将陆续更新 Python 编程相关的学习资料！
作者：ICodeWR
标签：#编程# #在头条记录我的2025# #python# #Python#