当前位置: 首页 > news >正文

Leetcode 311 Sparse Matrix Multiplication 稀疏矩阵相乘

Problem

Given two sparse matrices A and B, return the result of AB.

You may assume that A’s column number is equal to B’s row number.

Example:

A = [[ 1, 0, 0],[-1, 0, 3]
]B = [[ 7, 0, 0 ],[ 0, 0, 0 ],[ 0, 0, 1 ]
]|  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 || 0 0 1 |

Solution

  • Transform B into defaultdict(dict)
from collections import defaultdictdef multiply(A, B):# 预处理矩阵B的非零元素:建立行号到{列号: 值}的映射b_nonzero = defaultdict(dict)for k in range(len(B)):           # 遍历B的每一行for j in range(len(B[0])):    # 遍历该行的每一列if B[k][j] != 0:b_nonzero[k][j] = B[k][j]m = len(A)n = len(B[0]) if B else 0result = [[0] * n for _ in range(m)]for i in range(m):for k in range(len(A[i])):a_val = A[i][k]if a_val != 0:if k in b_nonzero:for j, b_val in b_nonzero[k].items():result[i][j] += a_val * b_valreturn resultA = [[ 1, 0, 0],[-1, 0, 3]
]
B = [[ 7, 0, 0 ],[ 0, 0, 0 ],[ 0, 0, 1 ]
]
print(multiply(A,B))

GPU Solution,来自DeepSeek的总结

根据2025年最新研究进展,GPU处理稀疏矩阵乘法(SpMM/SparseGEMM)的主流算子可分为以下四个技术方向,均已在工业界和学术界得到广泛应用:

一、基于压缩格式的专用算子

  1. CSR(Compressed Sparse Row)格式优化型
    以NVIDIA cuSPARSE库的csrmm2为基础,通过合并行缓存(CRC)和共享内存优化,实现非零元素的连续访问。典型代表如GE-SpMM算子,通过将稀疏数据加载到共享内存,消除全局内存的随机访问开销,在GNN场景中相比cuSPARSE提升1.41倍性能。

  2. 块压缩混合型
    DeepSeek提出的DeepGEMM支持MoE稀疏结构,采用即时编译(JIT)和Hopper TMA技术,在FP8精度下实现1350+ TFLOPS的算力,尤其擅长处理分组或掩码式稀疏乘法。该算子通过将稀疏块与密集块分离计算,在小矩阵场景加速比达2.7倍。

二、异构协同计算架构

  1. CPU-GPU联合计算型
    apspgemm框架通过自适应面板分割和NUMA感知调度,将大规模稀疏矩阵分解为规则面板分配给CPU和GPU协同计算。采用异步流水线技术重叠数据传输与计算,在十亿级边规模的社交网络图中实现7.21倍性能提升。其核心创新在于亲和度规则驱动的负载均衡算法。

  2. 量化稀疏混合型
    清华团队KTransformers框架集成Marlin量化算子和llamafile稀疏算子,通过计算强度分析动态分配任务:将高计算强度MLA算子放在GPU,低强度稀疏路由放在CPU。这种异构划分使4090单卡可运行671B参数模型,推理速度达286 tokens/s。

三、硬件指令级优化

  1. 原子操作增强型
    SpGEMM-Upper算法通过两阶段内存预分配策略,结合GPU原子操作实现行压缩并行化。在代数多重网格(AMG)计算中,相比传统方法减少38%的全局内存访问,压缩阶段采用Warp级协同写入优化。

  2. 稀疏脉动阵列型
    密歇根大学改造TPU架构提出Sparse-TPU,支持矩阵分块压缩和条件执行。通过跳过全零块的计算,在Hopper架构上实现稀疏矩阵16倍加速,能耗降低4-19倍。其核心是扩展了传统脉动阵列对稀疏数据的适应性。

四、算法-硬件协同设计

  1. 哈夫曼调度型
    MIT与NVIDIA联合提出的SpArch架构,通过哈夫曼编码动态调度非零块的计算顺序,结合行预取器实现输入复用。实验显示该方案将部分积矩阵数量减少58%,DRAM访问量降低2.8倍。

  2. 即时编译优化型
    DeepGEMM的JIT编译器能根据稀疏模式自动生成最优内核代码,仅需300行核心逻辑即可超越专家手工调优性能。该技术特别适用于动态稀疏模式(如MoE模型中的专家路由)。


性能对比与选型建议

算子类型适用场景峰值性能代表方案
CSR格式优化中小规模规则稀疏200-400 GFLOPSGE-SpMM
异构协同计算十亿级超大规模稀疏5.6 TFLOPSapspgemm
量化稀疏混合千亿参数MoE模型推理286 tokens/sKTransformers
硬件指令级优化科学计算/AMG求解器16x加速比Sparse-TPU

当前工业界主流选择是结合量化稀疏混合型与异构协同计算,如DeepSeek-R1和GPT-4o等大模型均采用类似KTransformers的架构。学术界则更关注基于新型压缩格式和硬件指令的深度优化,如apspgemm框架已被集成到AMGX数学库中。

相关文章:

Leetcode 311 Sparse Matrix Multiplication 稀疏矩阵相乘

Problem Given two sparse matrices A and B, return the result of AB. You may assume that A’s column number is equal to B’s row number. Example: A [[ 1, 0, 0],[-1, 0, 3] ]B [[ 7, 0, 0 ],[ 0, 0, 0 ],[ 0, 0, 1 ] ]| 1 0 0 | | 7 0 0 | | 7 0 0 | AB …...

mysql和sqlite关于data数据的识别问题

<input type"date" name"birthday" value""> # 表单传入的日期 birthday request.form.get(birthday) # 获取日期 birthday Column(birthday, Date, comment出生日期, nullableTrue) # 数据库的数据字段模型 birthday_str request…...

2024 天梯赛——工业园区建设题解

思路 将点 i i i 视为固定点&#xff0c; 点 j j j 视为灵活点&#xff0c;其中 s i 1 s_{i} 1 si​1&#xff0c; s j 0 s_{j} 0 sj​0。维护四个队列&#xff0c;其中 q 0 q_{0} q0​ 和 q 1 q_{1} q1​ 分别维护还没有被选用的固定点 和 灵活点&#xff0c; Q 0 Q…...

亚马逊AI新功能上线:5大亮点解锁精准消费预测

在人工智能技术不断重塑跨境电商生态之际&#xff0c;全球电商巨头亚马逊&#xff08;Amazon&#xff09;再次迈出关键一步。近日&#xff0c;亚马逊正式对其卖家中心推出一系列基于AI的新功能&#xff0c;聚焦于消费数据预测、用户行为洞察、库存智能管理与个性化营销服务等方…...

opus+ffmpeg+c++实现录音

说明&#xff1a; opusffmpegc实现录音 效果图&#xff1a; step1:C:\Users\wangrusheng\source\repos\WindowsProject1\WindowsProject1\WindowsProject1.cpp // WindowsProject1.cpp : 定义应用程序的入口点。 //#include "framework.h" #include "Windows…...

ComfyUI的本地私有化部署使用Stable Diffusion文生图

什么是ComfyUI &#xff1f; ComfyUI是一个基于节点流程的Stable Diffusion操作界面。以下是关于它的详细介绍&#xff1a; 特点与优势 高度可定制&#xff1a;提供丰富的节点类型&#xff0c;涵盖文本处理、图像处理、模型推理等功能。用户可根据需求自由组合节点&#xff0…...

【学习笔记17】Windows环境下安装RabbitMQ

一. 下载RabbitMQ&#xff08; 需要按照 Erlang/OTP 环境的版本依赖来下载&#xff09; (1) 先去 RabbitMQ 官网&#xff0c;查看 RabbitMQ 需要的 Erlang 支持&#xff1a;https://www.rabbitmq.com/ 进入官网&#xff0c;在 Docs -> Install and Upgrade -> Erlang V…...

【LeetCode 热题100】55:跳跃游戏(详细解析)(Go语言版)

&#x1f680; LeetCode 热题 55&#xff1a;跳跃游戏&#xff08;Jump Game&#xff09;完整解析 &#x1f4cc; 题目描述 给定一个非负整数数组 nums&#xff0c;你最初位于数组的第一个下标。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一…...

OpenCV轮廓检测全面解析:从基础到高级应用

一、概述 轮廓检测是计算机视觉中的基础技术&#xff0c;用于识别和提取图像中物体的边界。与边缘检测不同&#xff0c;轮廓检测更关注将边缘像素连接成有意义的整体&#xff0c;形成封闭的边界。 轮廓检测的核心价值 - 物体识别&#xff1a;通过轮廓可以识别图像中的独立物体…...

微服务入门:Spring Boot 初学者指南

大家好&#xff0c;这里是架构资源栈&#xff01;点击上方关注&#xff0c;添加“星标”&#xff0c;一起学习大厂前沿架构&#xff01; 微服务因其灵活性、可扩展性和易于维护性而成为现代软件架构的重要组成部分。在本博客中&#xff0c;我们将探讨如何使用 Spring Boot 构建…...

Windows环境下开发pyspark程序

Windows环境下开发pyspark程序 一、环境准备 1.1. Anaconda/Miniconda&#xff08;Python环境&#xff09; 如果不怕包的版本管理混乱&#xff0c;可以直接使用已有的Python环境。 需要安装anaconda/miniconda&#xff08;python3.8版本以上&#xff09;&#xff1a;Anaconda…...

嵌入式学习笔记——大小端及跳转到绝对地址

大小端以及跳转到绝对地址 0x100000 嵌入式编程中的大小端详解一、大端模式与小端模式二、判断当前系统是大端还是小端方法一&#xff1a;指针强制类型转换方法二&#xff1a;使用联合体&#xff08;union&#xff09; 三、结构体位段和大小端的影响四、大小端影响内存的 memc…...

eprime相嵌模式实验设计

一、含义与模型结构 该模式的实验设计至少 由两个存储不同实验材料及 属性的List和一个核心实验 过程CEP组成。子list1和 list2相嵌在父List中&#xff0c;CEP 可以调用List中的材料&#xff0c;也 可以调用list1和list2中的材 料。 二、相嵌模式的应用 应用于解决“多重随…...

编译uboot的Makefile编写

make ARCHarm CROSS_COMPILEarm-linux-gnueabihf- distcleanmake ARCHarm CROSS_COMPILEarm-linux-gnueabihf- mx6ull_14x14_ddr512_emmc_defconfigmake V1 ARCHarm CROSS_COMPILEarm-linux-gnueabihf- -j12 这三条命令中 ARCHarm 设置目标为 arm 架构&#xff0c; CROSS_COMP…...

Go语言常用算法实现

以下是Go语言中常用的算法实现&#xff0c;涵盖排序、搜索、数据结构操作等核心算法。 一、排序算法 1. 快速排序 func QuickSort(arr []int) []int {if len(arr) < 1 {return arr}pivot : arr[0]var left, right []intfor i : 1; i < len(arr); i {if arr[i] < pi…...

Windows上使用NSSM注册定时服务

适用和不适用场景 适用场景 持续运行 的脚本或程序&#xff08;如 Laravel 的 schedule:run 每分钟检查任务&#xff09;后台常驻 的任务或服务&#xff08;如监听服务、实时同步&#xff09; 不适用场景 低频次任务&#xff08;如每日/每周备份&#xff09; NSSM 常驻内存…...

【Gorm】模型定义

intro package mainimport ("gorm.io/gorm""gorm.io/driver/sqlite" // GORM 使用该驱动来连接和操作 SQLite 数据库。 )type Product struct {gorm.Model // 嵌入GORM 内置的模型结构&#xff0c;包含 ID、CreatedAt、UpdatedAt、DeletedAt 四个字段Cod…...

程序化广告行业(65/89):AdX/SSP系统深度剖析与实战要点

程序化广告行业&#xff08;65/89&#xff09;&#xff1a;AdX/SSP系统深度剖析与实战要点 大家好&#xff01;一直以来&#xff0c;我都对程序化广告领域充满热情&#xff0c;这个领域发展迅速且不断涌现新的技术和模式。之前我们探讨了程序化广告的一些基础内容&#xff0c;…...

算法刷题记录——LeetCode篇(2.7) [第161~170题](持续更新)

更新时间&#xff1a;2025-04-06 算法题解目录汇总&#xff1a;算法刷题记录——题解目录汇总技术博客总目录&#xff1a;计算机技术系列博客——目录页 优先整理热门100及面试150&#xff0c;不定期持续更新&#xff0c;欢迎关注&#xff01; 169. 多数元素 给定一个大小为…...

conda安装指定版本python环境

1. 创建指定 Python 版本的环境 使用以下命令创建环境&#xff0c;并将 <env_name> 替换为你的环境名称&#xff0c;<python_version> 替换为具体的 Python 版本&#xff08;如 3.8, 3.9 等&#xff09; conda create -n <env_name> python<python_vers…...

PH热榜 | 2025-04-05

1. Comp AI 标语&#xff1a;开源的 Vanta 和 Drata 替代方案 介绍&#xff1a;这款开源的 Drata 和 Vanta 替代方案&#xff0c;能够帮助你在几周内&#xff0c;轻松满足 SOC 2、ISO 27001 和 GDPR 等合规框架的要求&#xff0c;而不是像往常那样拖延数月。 产品网站&#…...

C++之红黑树

目录​​​​​​​ 一、红黑树的概念 1.1、红黑树的规则 1.2、红黑树如何确保最长路径不超过最短路径的二倍 1.3、红黑树的效率 二、红黑树的实现 2.1、红黑树的结构 2.2、红黑树的插入 2.2.1、红黑树插入一个值的大概过程 2.2.2、情况一&#xff1a;变色 2.2.3、情…...

各个语言对不同数据结构的叫法

一、基础数据结构对比 数组&#xff08;Array&#xff09;‌ C/C‌&#xff1a;固定大小数组&#xff08;int arr&#xff09;&#xff0c;动态数组通过vector&#xff08;C&#xff09;实现 ‌ Java‌&#xff1a;固定数组&#xff08;int[]&#xff09;&#xff0c;动态数组…...

蓝桥杯 web 水果拼盘 (css3)

做题步骤&#xff1a; 看结构&#xff1a;html 、css 、f12 分析: f12 查看元素&#xff0c;你会发现水果的高度刚好和拼盘的高度一样&#xff0c;每一种水果的盘子刚好把页面填满了&#xff0c;所以咱们就只要让元素竖着排列&#xff0c;加上是竖着&#xff0c;排不下的换行…...

算法专题(八):分治-归并排序

目录 一、排序数组 1.1 题目 2.2 思路 2.3 代码实现 二、LCR 170. 交易逆序对的总数 &#xff08;数组中的逆序对&#xff09; 2.1 题目 2.2 思路 方法一&#xff1a;快速统计出某个数前面有多少个数比它大 方法二&#xff1a;快速统计出某个数后面有多少个数比它小 …...

51单片机使用定时器实现LCD1602的时间显示(STC89C52RC)

本文前半部分直接给出实现&#xff08;注意进位问题是秒->分->小时&#xff0c;用 if 嵌套即可实现&#xff09;&#xff0c;后半部分讲解定时器和中断系统。 效果展示&#xff1a; LCD1602电路图&#xff1a; 项目结构&#xff1a; 代码实现&#xff1a; main.c #…...

微软2025年AI技术深度解析:从多模态大模型到企业级代理服务

微软2025年AI技术深度解析&#xff1a;从多模态大模型到企业级代理服务 一、微软AI技术全景概览 在2025年的AI领域&#xff0c;微软通过Azure AI Foundry、多模态大模型、企业级AI代理三大核心技术&#xff0c;构建了覆盖开发、部署、应用全流程的AI生态体系。根据最新财报数…...

24 设计模式总结

设计模式分类&#xff08;意图&#xff09; • 创建型模式&#xff1a;创建对象的机制&#xff0c;从所需要实例化的对象中解耦。 • 结构型模式&#xff1a;将对象或类组装到更大的结构中。 • 行为型模式&#xff1a;负责对象间的交互和分配职责。分类的目的是为了更抽象的了…...

【ARTS】2873.有序三元组中的最大值!

前言 仅做学习使用&#xff0c;侵删 什么是ARTS&#xff1f; 算法(Algorithm): 每周至少一道LeetCode算法题&#xff0c;加强编程训练和算法学习 阅读(Review)&#xff1a; 阅读并点评至少一篇英文技术文章&#xff0c;提高英文水平 技巧 (Tip)&#xff1a;学习至少一个技…...

Mysql进阶

目录 一.Mysql架构 1.连接层 2.服务层 3.引擎层 4.物理文件存储层 二.Mysql引擎 1.InnoDB 2.MyISAM 三.索引 1.什么是索引 2.为什么要有索引 3.索引的原理 4.索引优势 5.索引劣势 6.索引分类 主键索引 唯一索引 单值索引 组合索引&#xff08;复合索引&#…...

探秘JVM内部

在我们编写Java代码&#xff0c;点击运行后&#xff0c;会发生什么事呢&#xff1f; 首先&#xff0c;Java源代码会经过Java编译器将其编译成字节码&#xff0c;放在.class文件中 然后这些字节码文件就会被加载到jvm中&#xff0c;然后jvm会读取这些文件&#xff0c;调用相关…...

c语言学习12天

c语言的宏定义&#xff1a;宏定义单纯的文本替换不会检查语法是否合法 #include #pragma 以及开头的#都属于预处理指令 预处理指令&#xff1a;在gcc编译套件中的cpp预处理器对程序进行编译之前所做的一些动作&#xff0c;如#include预处理指令就是在程序编译之前有预处理器…...

公司内网部署离线deepseek本地模型实战

企业内部可能有些数据比较敏感&#xff0c;不能连接互联网。deepseek来提高工作效率&#xff0c;这个时候你可以利用ollama在内网本地部署来实现。 本式样是先在自己电脑上用虚拟机部署好&#xff0c;再用U盘把虚拟机文件复制到内网去。 一、使用VMware新建WIN2022虚拟机 &a…...

rocketmq中的延迟队列使用详解

RocketMQ的延迟队列通过预设的延迟等级实现消息的定时投递&#xff0c;适用于订单超时、定时通知等高并发场景。以下是其核心原理、使用方式及优化策略的详细解析&#xff1a; 一、实现原理 延迟等级机制 RocketMQ默认提供18个固定延迟等级&#xff08;1s、5s、10s、30s、1m、2…...

VB.NET Asp.Net Core模板WebAPI应用-宝塔面板Linux系统通过Docker部署

宝塔面板支持在Linux系统上部署Docker容器吗&#xff1f; 如何在宝塔面板上通过Docker部署VB.NET应用&#xff1f; Docker容器中的VB.NET Asp.Net Core WebAPI应用如何配置&#xff1f; 一,首先,创建一个ASP.NET Core测试项目 1.1 打开VS2019/2022,创建一个.NTE6 Core控制台应…...

4985 蜗牛

4985 蜗牛 ⭐️难度&#xff1a;中等 ⭐️考点&#xff1a;2023、省赛、动态规划 &#x1f4d6; &#x1f4da; import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc new Sc…...

springboot多模块工程打包部署运行

1、问题概述? 基于实际项目打包过程,各种配置面面俱到,已配置的可跳过。 本文以打包jar包为模板进行操作,部署方便。 在实际的开发中,项目的模块可能较多,如果都放在一个项目的目录中,势必会造成项目包中的文件冗余,难以管理,这个时候就需要使用多模块管理项目。 …...

吴恩达深度学习复盘(8)神经网络中激活函数的建模

激活函数的建模原理 到目前为止&#xff0c;在隐藏层等一直使用激活函数&#xff0c;最初通过逻辑回归建立新网络&#xff0c;组合多个逻辑回归单元。这表明激活函数在神经网络构建中一直存在&#xff0c;且最初的网络构建方式与逻辑回归相关。实际上&#xff0c;激活函数的种类…...

1-linux的基础知识

一.linux的文件系统结构 windows文件系统 微软windows系统将硬盘上的几个分区&#xff0c;用A: B: C: D:等符号标识。存取文件时一定要清楚放在那个磁盘的那个目录下。 linux文件系统 linux文件系统的组织模式犹如一颗倒置的树&#xff0c;这与windows文件系统有很大的差别…...

docker 常用命令

文章目录 一、帮助启动类命令启动docker停止docker重启docker查看docker状态开机自启查看docker概要信息 二、镜像命令列出本地主机上的镜像搜索镜像拉取镜像查看镜像所占空间删除镜像 三、容器命令新建运行容器交互式启动容器守护进程式启动容器列出当前所有的容器进入容器之后…...

使用docker搭建redis镜像时云服务器无法访问到国外的docker官网时如何解决

下载redis镜像 docker redis:版本号 此时截图中无法访问到国外的docker官网 解决方案&#xff1a; 通过更换镜像源来正常下载redis镜像 sudo mkdir -p /etc/docker sudo tee /etc/docker/daemon.json <<EOF {"registry-mirrors": ["https://docker.1…...

基于Python的人脸识别校园考勤系统

【Python】基于Python的人脸识别校园考勤系统 &#xff08;完整系统源码开发笔记详细部署教程&#xff09;✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 &#x1f31f; 该系统主要分为前端和后端两个部分&#xff0c;前端&#x1f440;负责人脸采集、人…...

微信小程序学习实录11:startLocationUpdateBackground:fail auth deny

startLocationUpdateBackground:fail auth deny 表明小程序在尝试开启后台位置更新时&#xff0c;用户授权被拒绝。以下是可能的原因及解决方法&#xff1a; 原因分析 缺少必要的用户授权&#xff1a; 使用 wx.startLocationUpdateBackground 接口需要用户授予 scope.userLo…...

DAPP实战篇:规划下我们的开发线路

前言 在DApp实战篇&#xff1a;先用前端起个项目一文中我们起了一个前端项目&#xff0c;在后续开发中笔者将带领大家一步步完成这个DAPP&#xff0c;为了方便后续讲解&#xff0c;本篇将完整说明后续我们要进行的开发和思路。 主打前端 实际上一个完整的DAPP是由前端和智能…...

docker配置redis容器时配置文件docker-compose.yml示例

1.配置数据节点&#xff08;主从节点&#xff09; version: 3.7 services:master:image: redis:5.0.9container_name: redis-masterrestart: alwayscommand: redis-server --appendonly yesports:- 6379:6379slave1:image: redis:5.0.9container_name: redis-slave1restart: a…...

清晰易懂的 Jenkins 安装与核心使用教程

Jenkins 是业界领先的开源自动化服务器&#xff0c;用于实现持续集成与持续交付&#xff08;CI/CD&#xff09;。本教程将覆盖 安装部署、核心功能配置、避坑指南&#xff0c;助你快速掌握企业级自动化流水线搭建&#xff01; 一、Jenkins 安装&#xff08;全平台指南&#xff…...

anomalib—2—输入图像大小调整

三个地方 第一&#xff1a;在定义model时&#xff0c;要在pre_processor里面去定义一个前处理&#xff0c;前处理就一个功能&#xff0c;定义图像的大小 pre_processor0 Patchcore.configure_pre_processor( image_size (128, 128)) model Patchcore( backbone"wide_r…...

小型园区组网图

1. 在小型园区中&#xff0c;S5735-L-V2通常部署在网络的接入层&#xff0c;S8700-4通常部署在网络的核心&#xff0c;出口路由器一般选用AR系列路由器。 2. 接入交换机与核心交换机通过Eth-Trunk组网保证可靠性。 3. 每个部门业务划分到一个VLAN中&#xff0c;部门间的业务在C…...

编程哲学——TCP可靠传输

TCP TCP可靠传输 TCP的可靠传输表现在 &#xff08;1&#xff09;建立连接时三次握手&#xff0c;四次挥手 有点像是这样对话&#xff1a; ”我们开始对话吧“ ”收到“ ”好的&#xff0c;我收到你收到了“ &#xff08;2&#xff09;数据传输时ACK应答和超时重传 ”我们去吃…...

2024华为OD机试真题-任务最优调度(C++/Java/Python)-E卷-200分

2024华为OD机试最新E卷题库-(D卷+E卷)-(JAVA、Python、C++) 目录 题目描述 输入描述 输出描述 用例1 考点 题目解析 代码 c++ java python 题目描述 给定一个正整数数组表示待系统执行的任务列表,数组的每一个元素代表一个任务,元素的值表示该任务的类型。请计算执…...