【知识】稀疏矩阵是否比密集矩阵更高效?

news/2024/2/29 3:31:22

转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn]

问题提出

        有些地方说,稀疏图比密集图的计算效率更高,真的吗?

原因猜想

        这里的效率高,应该是有前提的:当使用稀疏矩阵的存储格式(如CSR)时,计算效率更高。如果是普通的完整矩阵格式,实际上效率一样。

        稀疏矩阵的存储格式(如 COO、CSR 或 CSC)直接影响乘法的效率, 一些格式在某些类型的运算中更高效,因为它们可以更快地访问和处理非零元素。因此,当使用了稀疏矩阵存储格式时,如果矩阵非常稀疏(即大多数元素为零),那么使用稀疏矩阵进行矩阵乘法通常会更高效,因为可以跳过大量的零元素乘法操作。

代码验证

import numpy as np
from scipy.sparse import csr_matrix
import time
import matplotlib.pyplot as plt
from tqdm import tqdmdef measure_time(matrix_size=1000, density=0.1):# 创建密集矩阵dense_matrix = np.random.rand(matrix_size, matrix_size)# 创建普通的稀疏矩阵sparse_matrix = dense_matrix < densitysparse_matrix = sparse_matrix.astype(np.float64)# 将普通的稀疏矩阵转换为CSR格式csr_matrix_sparse = csr_matrix(sparse_matrix)# warmupfor _ in range(5):np.dot(sparse_matrix, sparse_matrix)# 对普通的稀疏矩阵进行矩阵乘法,并计时start_time = time.time()_ = np.dot(sparse_matrix, sparse_matrix)sparse_time = time.time() - start_time# warmupfor _ in range(5):np.dot(dense_matrix, dense_matrix)# 对密集矩阵进行矩阵乘法,并计时start_time = time.time()_ = np.dot(dense_matrix, dense_matrix)dense_time = time.time() - start_time# warmupfor _ in range(5):csr_matrix_sparse.dot(csr_matrix_sparse)# 对CSR格式的稀疏矩阵进行矩阵乘法,并计时start_time = time.time()_ = csr_matrix_sparse.dot(csr_matrix_sparse)csr_time = time.time() - start_timereturn sparse_time, dense_time, csr_time# 矩阵大小范围
sizes = np.arange(10, 1001, 10)
# 记录每种大小下的耗时
times_sparse = []
times_dense = []
times_csr = []
for size in tqdm(sizes):sparse_time, dense_time, csr_time = measure_time(matrix_size=size)times_sparse.append(sparse_time)times_dense.append(dense_time)times_csr.append(csr_time)
# 绘制结果
plt.figure(figsize=(10, 6))
plt.plot(sizes, times_sparse, label='sparse')
plt.plot(sizes, times_dense, label='dense')
plt.plot(sizes, times_csr, label='csr')
plt.xlabel('matrix size')
plt.ylabel('time (s)')
plt.title('matrix_size vs time')
plt.legend()
plt.show()# 稀疏度范围
density = np.arange(0, 1, 0.01)
# 记录每种大小下的耗时
times_sparse = []
times_dense = []
times_csr = []
for den in tqdm(density):sparse_time, dense_time, csr_time = measure_time(density=den)times_sparse.append(sparse_time)times_dense.append(dense_time)times_csr.append(csr_time)
# 绘制结果
plt.figure(figsize=(10, 6))
plt.plot(density, times_sparse, label='sparse')
plt.plot(density, times_dense, label='dense')
plt.plot(density, times_csr, label='csr')
plt.xlabel('density')
plt.ylabel('time (s)')
plt.title('density vs time')
plt.legend()
plt.show()

        从上图可以看出,随着矩阵大小的增大,三种形式的计算效率都在降低,但两种普通的完整矩阵形式的乘法,其效率的变化趋势是一致的。考虑到时间统计有波动,因此可以看成他俩实际上是一样的时间。

        注意,上图中CSR的计算效率低于其他两者,是因为密集度为0.1。当密集度设置为0.01时,CSR的计算效率就会更高了。

        从这个图可以看到,随着密集度的增加,CSR的效率逐渐变低,但普通的完整矩阵形式的乘法,其效率并没有发生变化。


https://www.xjx100.cn/news/3118778.html

相关文章

国内首个农业开源鸿蒙操作系统联合华为正式发布

2023年11月29日&#xff0c;在中国国际供应链促进博览会上&#xff0c;中信农业科技股份有限公司&#xff08;简称“中信农业”&#xff09;与深圳开鸿数字产业发展有限公司&#xff08;简称“深开鸿”&#xff09;以及华为技术有限公司&#xff08;简称“华为”&#xff09;联…

DeepStream系列之rtmpsink功能,rtsp转rtmp,opencv读取rtsp图像处理后推流rtmp

了解到一个更好的流媒体开源项目&#xff0c;是中国人写的&#xff0c;项目地址 https://github.com/ossrs/srs&#xff0c;有兴趣的可以尝试下&#xff0c;实时性更快 DeepStream系列之rtmpsink功能 实时性没要求&#xff0c;可以用下面的opencv opencv读取rtsp图像处理后推流…

Django回顾【三】

目录 一、模板层 1、介绍 2、了解 3、页面静态化 4、模版语法 5、内置过滤器 6、标签 for标签 if 标签 7、模板导入和继承 模板导入 模板继承 一、模板层 1、介绍 模板在浏览器中是运行不了的 ----》因为它有模板语法 ----》浏览器解析不了模板语法 必须在后端渲…

kubernetes七层负载Ingress搭建(K8S1.23.5)

首先附上K8S版本及Ingress版本对照 Ingress介绍 NotePort&#xff1a;该方式的缺点是会占用很多集群机器的端口&#xff0c;当集群服务变多时&#xff0c;这个缺点就愈发的明显(srevice变多&#xff0c;需要的端口就需要多) LoadBalancer&#xff1a;该方式的缺点是每个servi…

鸿蒙4.0开发笔记之ArkTS装饰器语法基础@Extend扩展组件样式与stateStyles多态样式(十一)

一、Extend扩展组件样式 1、作用 前文提到可以使用Styles用于样式的扩展&#xff0c;在Styles的基础上&#xff0c;ArkTS语法还提供了Extend&#xff0c;⽤于扩展原生组件样式&#xff0c;包括Text、Button等等。 2、定义语法 Extend(UIComponentName) function functionNam…

C# 模拟鼠标操作工具类

写在前面 用WinForm做RPA项目时经常需要模拟鼠标操作&#xff0c;通过调用Windows Api 可以实现控制鼠标的移动、点击以及滚轮滚动&#xff0c;做到跟人工一样的操作。 代码实现 public static class MouseKeyController{[DllImport("user32")]private static exte…

C++面试的一些总结day1:指针和引用的区别

文章目录 指针和引用的区别和作用定义区别作用 指针和引用的区别和作用 定义 指针&#xff1a;指针是一个变量&#xff0c;其值为指向对象的内存地址&#xff0c;而不是值本身。引用&#xff1a;可以理解为对象的别名&#xff0c;是另外一个变量的直接别名&#xff0c;用于创…

虚幻学习笔记7—蓝图接口

一、前言 蓝图接口就是可以在蓝图中实现的接口&#xff0c;有它方便的地方&#xff0c;可以很方便的调用到实现了接口的函数。 二、实现 2.1、创建一个蓝图接口 1&#xff09;可以添加多个函数。 2&#xff09;函数在蓝图接口中只能规定输入和输出参数。 只有输入参数的可以…