首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在最小内存的上三角元素上以最快速的方式对上三角元素求和

问在最小内存的上三角元素上以最快速的方式对上三角元素求和
EN

Stack Overflow用户
提问于 2019-02-11 11:28:57
回答 4查看 2.3K关注 0票数 3

我需要在对称矩阵上执行i<j类的求和。这相当于对角排除的矩阵上三角形元素上的和。

给定A一个对称的N x N数组,最简单的解决方案是np.triu(A,1).sum(),但是我想知道是否存在更快、需要更少内存的方法。看起来(A.sum() - np.diag(A).sum())/2在大型数组上速度更快,但是如何避免从np.diag创建甚至是N x 1数组?双重嵌套的for循环不需要额外的内存,但在Python中显然不是这样的。

EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2019-02-11 11:33:10

可以将np.diag(A).sum()替换为np.trace(A);这不会创建临时Nx1数组。

票数 3
EN

Stack Overflow用户

发布于 2019-02-11 11:44:48

将我的2美分添加到其他答案和评论中,您可能会对1000x1000对称矩阵的以下时间性能感兴趣。如您所见,sum_diag方法在这种情况下略胜一筹。

代码语言:javascript
复制
import numpy as np

N = 1000
a = np.random.randint(-2000,2000,size=(N,N))
A = (a + a.T)/2

def sum_triu(A):
    return np.triu(A,1).sum()

def sum_diag(A):
    return (A.sum() - np.diag(A).sum())/2

def sum_trace(A):
    return (A.sum() - np.trace(A))/2

%timeit sum_triu(A)
# 3.65 ms ± 406 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit sum_diag(A)
# 663 µs ± 88.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit sum_trace(A)
# 732 µs ± 120 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
票数 3
EN

Stack Overflow用户

发布于 2019-02-11 12:28:28

在纯numpy中,内存最少的最快方法是对整件事情进行求和,并减去对角线。

就失败而言,这可能是一种浪费,但请注意,相对于实现而言,理论上的节省仅仅是一个因素2。如果这对您有任何意义,那么您一开始就不应该使用numpy。

此外,numpy从根本上处理可作为跨栏视图寻址的内存块。如果您可以在三角形上得到一个单一的跨栏视图,它可能会导致一个高效的numpy实现。但是你不能(把证据留给读者),所以你可以安全地忘记任何真正的非常规解决方案,而不是调用一个优化的C例程来解决你的问题。我所知道的不存在。

但是,即使是“优化”的C循环在实践中也可能被A.sum()所激怒。如果A是连续的,则该和有可能分派一个最大缓存优化和SIMD优化的代码路径。很可能,A.sum()在一个基准测试中,自己写的任何虚幻的东西都会被彻底摧毁。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54629601

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档