- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在使用 scipy-0.17 进行简单的稀疏矩阵求幂 a**16
。 (注意,不是元素乘法)。但是,在我的机器上(运行 Debian 稳定版和 Ubuntu LTS),这比使用 for 循环或做一些像 a*a*a*a*a*a*a*a*a*a 这样的傻事要慢十倍*a*a*a*a*a*a
。这没有意义,所以我假设我做错了什么,但是什么?
import scipy.sparse
from time import time
a=scipy.sparse.rand(2049,2049,.002)
print ("Trying exponentiation (a**16)")
t=time()
x=a**16
print (repr(x))
print ("Exponentiation took %f seconds\n" % (time()-t))
print ("Trying expansion (a*a*a*...*a*a)")
t=time()
y=a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
print (repr(y))
print ("Expansion took %f seconds\n" % (time()-t))
print ("Trying a for loop (z=z*a)")
t=time()
z=scipy.sparse.eye(2049)
for i in range(16):
z=z*a
print (repr(z))
print ("Looping took %f seconds\n" % (time()-t))
# Sanity check, all approximately the same answer, right?
assert (abs(x-z)>=1e-9).nnz==0
assert (abs(x-y)>=1e-9).nnz==0
最佳答案
@hpaulj 关于非零数的评论很重要。当您计算 a
的更高次幂时,非零元素的数量增加。对于稀疏矩阵,计算矩阵的时间产品随着非零元素的数量增加。
用于计算 a**16
的算法实际上是:
a2 = a*a
a4 = a2*a2
a8 = a4*a4
a16 = a8*a8
现在看看这些矩阵中非零元素的数量对于 a = sparse.rand(2049, 2049, 0.002)
:
matrix nnz fraction nnz
a 8396 0.0020
a2 34325 0.0082
a4 521593 0.1240
a8 4029741 0.9598
在最后一个产品中,a16 = a8*a8
,因子为 96% 非零。计算使用稀疏矩阵乘法的乘积慢。最后一步占用了 97% 的时间来计算 a**16
。
另一方面,当您计算a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
时,稀疏矩阵乘法执行 15 次,但一次每个产品中的因素总是有一小部分 (0.002)的非零值,因此每个产品都可以合理地执行高效。
这表明可能存在计算乘积的最佳策略,平衡乘法次数与因子的稀疏性。例如,计算 a2 = a*a; a16 = a2*a2*a2*a2*a2*a2*a2*a2
比 a16 = a*a*a*a*a*a*a*a*a*a*a 快*a*a*a*a*a
:
In [232]: %timeit a2 = a*a; a4 = a2*a2; a8 = a4*a4; a16 = a8*a8
14.4 s ± 199 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [233]: %timeit a16 = a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
1.77 s ± 4.78 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [234]: %timeit a2 = a*a; a16 = a2*a2*a2*a2*a2*a2*a2*a2
1.42 s ± 3.16 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
或者,由于您知道最终结果将是密集的,因此从一开始或在密集矩阵乘法比稀疏矩阵乘法更有效的某个中间步骤切换到标准 numpy 数组。
关于python - Scipy 稀疏矩阵求幂 : a**16 is slower than a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44622047/
我在服务器上 checkout 了一个 git 存储库。该存储库过去在根目录下包含所有相关文件,但我必须进行一些更改,现在我有两个文件夹,src 和 dist,我想跟踪这两个文件夹. 我遇到的问题是,
我很难弄清楚 VkDescriptorSetLayoutBinding::binding 的任何用例,这是结构: struct VkDescriptorSetLayoutBinding { u
Python中能否有效获取稀疏向量的范数? 我尝试了以下方法: from scipy import sparse from numpy.linalg import norm vector1 = spa
我正在尝试找出为什么这段代码不对数组进行排序... 任意向量。 x = array([[3, 2, 4, 5, 7, 4, 3, 4, 3, 3, 1, 4, 6, 3, 2, 4, 3, 2]])
有谁知道如何压缩(编码)稀疏 vector ?稀疏 vector 表示有许多“0”的 1xN 矩阵。 例如 10000000000001110000000000000000100000000 上面是稀
我使用稀疏高斯过程进行 Rasmussen 回归。[http://www.tsc.uc3m.es/~miguel/downloads.php][1] 预测平均值的语法是: [~, mu_1, ~, ~
我在朴素贝叶斯分类器中使用 Mahout API。其中一个功能是 SparseVectorsFromSequenceFiles虽然我已经尝试过旧的谷歌搜索,但我仍然不明白什么是稀疏 vector 。最
我正在尝试将JavaScript稀疏数组映射到C#表示形式。 建议这样做的方法是什么? 它正在考虑使用一个字典,该字典包含在原始数组中包含值的原始词列表。 还有其他想法吗? 谢谢! 最佳答案 注意 针
如果我想求解一个完整上三角系统,我可以调用linsolve(A,b,'UT')。然而,这目前不支持稀疏矩阵。我该如何克服这个问题? 最佳答案 UT 和 LT 系统是最容易解决的系统之一。读一读on t
我有一个带有 MultiIndex 的 Pandas DataFrame。 MultiIndex 的值在 (0,0) 到 (1000,1000) 范围内,该列有两个字段 p 和 q. 但是,DataF
我目前正在实现一个小型有限元模拟。使用 Python/Numpy,我正在寻找一种有效的方法来创建全局刚度矩阵: 1)我认为应该使用coo_matrix()从较小的单元刚度矩阵创建稀疏矩阵。但是,我可以
a , b是 1D numpy ndarray与整数数据类型具有相同的大小。 C是一个 2D scipy.sparse.lil_matrix . 如果索引[a, b]包含重复索引,C[a, b] +=
我有一个大的、连通的、稀疏的邻接表形式的图。我想找到两个尽可能远的顶点,即 diameter of the graph以及实现它的两个顶点。 对于不同的应用程序,我对无向和有向情况下的这个问题都很感兴
上下文:我将 Eigen 用于人工神经网络,其中典型维度为每层约 1000 个节点。所以大部分操作是将大小为 ~(1000,1000) 的矩阵 M 与大小为 1000 的 vector 或一批 B v
我有一些大小合适的矩阵 (2000*2000),我希望在矩阵的元素中有符号表达式 - 即 .9**b + .8**b + .7**b ... 是一个元素的例子。矩阵非常稀疏。 我通过添加中间计算来创建
在 R 或 C++ 中是否有一种快速填充(稀疏)矩阵的方法: A, B, 0, 0, 0 C, A, B, 0, 0 0, C, A, B, 0 0, 0, C, A, B 0, 0, 0, C, A
我有一个大的稀疏 numpy/scipy 矩阵,其中每一行对应于高维空间中的一个点。我想进行以下类型的查询: 给定一个点P(矩阵中的一行)和一个距离epsilon,找到与epsilon距离最大的所有点
假设我有一个 scipy.sparse.csr_matrix 代表下面的值 [[0 0 1 2 0 3 0 4] [1 0 0 2 0 3 4 0]] 我想就地计算非零值的累积和,这会将数组更改为:
我了解如何在 Git 中配置稀疏 checkout ,但我想知道是否可以消除前导目录。例如,假设我有一个 Git 存储库,其文件夹结构如下: 文件夹1/foo 文件夹2/foo/bar/stuff 文
根据 this thread , Git 中的排除 sparse-checkout feature应该实现。是吗? 假设我有以下结构: papers/ papers/... presentations
我是一名优秀的程序员,十分优秀!