百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术资源 > 正文

Python 编程算法级优化

off999 2025-05-23 19:17 23 浏览 0 评论

大家好,我是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秒

优化要求

  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#


相关推荐

推荐一款Python的GUI可视化工具(python 可视化工具)

在Python基础语法学习完成后,进一步开发应用界面时,就需要涉及到GUI了,GUI全称是图形用户界面(GraphicalUserInterface,又称图形用户接口),采用图形方式显示的计算机操...

教你用Python绘制谷歌浏览器的3种图标

前两天在浏览matplotlib官方网站时,笔者无意中看到一个挺有意思的图片,就是用matplotlib制作的火狐浏览器的logo,也就是下面这个东东(网页地址是https://matplotlib....

小白学Python笔记:第二章 Python安装

Windows操作系统的python安装:Python提供Windows、Linux/UNIX、macOS及其他操作系统的安装包版本,结合自己的使用情况,此处仅记录windows操作系统的python...

Python程序开发之简单小程序实例(9)利用Canvas绘制图形和文字

Python程序开发之简单小程序实例(9)利用Canvas绘制图形和文字一、项目功能利用Tkinter组件中的Canvas绘制图形和文字。二、项目分析要在窗体中绘制图形和文字,需先导入Tkinter组...

一文吃透Python虚拟环境(python虚拟环境安装和配置)

摘要在Python开发中,虚拟环境是一种重要的工具,用于隔离不同项目的依赖关系和环境配置。本文将基于windows平台介绍四种常用的Python虚拟环境创建工具:venv、virtualenv、pip...

小白也可以玩的Python爬虫库,收藏一下

最近,微软开源了一个项目叫「playwright-python」,作为一个兴起项目,出现后受到了大家热烈的欢迎,那它到底是什么样的存在呢?今天为你介绍一下这个传说中的小白神器。Playwright是...

python环境安装+配置教程(python安装后怎么配置环境变量)

安装python双击以下软件:弹出一下窗口需选择一些特定的选项默认选项不需要更改,点击next勾选以上选项,点击install进度条安装完毕即可。到以下界面,证明安装成功。接下来安装库文件返回电脑桌面...

colorama,一个超好用的 Python 库!

大家好,今天为大家分享一个超好用的Python库-colorama。Github地址:https://github.com/tartley/coloramaPythoncolorama库是一...

python制作仪表盘图(python绘制仪表盘)

今天教大家用pyecharts画仪表盘仪表盘(Gauge)是一种拟物化的图表,刻度表示度量,指针表示维度,指针角度表示数值。仪表盘图表就像汽车的速度表一样,有一个圆形的表盘及相应的刻度,有一个指针...

总结90条写Python程序的建议(python写作)

  1.首先  建议1、理解Pythonic概念—-详见Python中的《Python之禅》  建议2、编写Pythonic代码  (1)避免不规范代码,比如只用大小写区分变量、使用容易...

[oeasy]python0137_相加运算_python之禅_import_this_显式转化

变量类型相加运算回忆上次内容上次讲了是从键盘输入变量input函数可以有提示字符串需要有具体的变量接收输入的字符串输入单个变量没有问题但是输入两个变量之后一相加就非常离谱添加图片注释,不超过1...

Python入门学习记录之一:变量(python中变量的规则)

写这个,主要是对自己学习python知识的一个总结,也是加深自己的印象。变量(英文:variable),也叫标识符。在python中,变量的命名规则有以下三点:>变量名只能包含字母、数字和下划线...

掌握Python的&quot;魔法&quot;:特殊方法与属性完全指南

在Python的世界里,以双下划线开头和结尾的"魔法成员"(如__init__、__str__)是面向对象编程的核心。它们赋予开发者定制类行为的超能力,让自定义对象像内置类型一样优雅工...

11个Python技巧 不Pythonic 实用大于纯粹

虽然Python有一套强大的设计哲学(体现在“Python之禅”中),但总有一些情况需要我们“打破规则”来解决特定问题。这触及了Python哲学中一个非常核心的理念:“实用主义胜于纯粹主义”...

Python 从入门到精通 第三课 诗意的Python之禅

导言:Python之禅,英文名是TheZenOfPython。最早由TimPeters在Python邮件列表中发表,它包含了影响Python编程语言设计的20条软件编写原则。它作为复活节彩蛋...

取消回复欢迎 发表评论: