我需要在对称矩阵上执行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中显然不是这样的。
发布于 2019-02-11 11:33:10
可以将np.diag(A).sum()替换为np.trace(A);这不会创建临时Nx1数组。
发布于 2019-02-11 11:44:48
将我的2美分添加到其他答案和评论中,您可能会对1000x1000对称矩阵的以下时间性能感兴趣。如您所见,sum_diag方法在这种情况下略胜一筹。
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)发布于 2019-02-11 12:28:28
在纯numpy中,内存最少的最快方法是对整件事情进行求和,并减去对角线。
就失败而言,这可能是一种浪费,但请注意,相对于实现而言,理论上的节省仅仅是一个因素2。如果这对您有任何意义,那么您一开始就不应该使用numpy。
此外,numpy从根本上处理可作为跨栏视图寻址的内存块。如果您可以在三角形上得到一个单一的跨栏视图,它可能会导致一个高效的numpy实现。但是你不能(把证据留给读者),所以你可以安全地忘记任何真正的非常规解决方案,而不是调用一个优化的C例程来解决你的问题。我所知道的不存在。
但是,即使是“优化”的C循环在实践中也可能被A.sum()所激怒。如果A是连续的,则该和有可能分派一个最大缓存优化和SIMD优化的代码路径。很可能,A.sum()在一个基准测试中,自己写的任何虚幻的东西都会被彻底摧毁。
https://stackoverflow.com/questions/54629601
复制相似问题