如何有效地计算二维累积和 [英] How to compute 2D cumulative sum efficiently

问题描述

给定一个形状为 (m,n) 的二维数值数组 X，我想计算一个数组 Y相同的形状，其中 Y[i,j] 是 X[i_,j_] 对于 0<=i_<=i, 0<= 的累积和j_<=j.如果 X 描述的是二维概率分布，则 Y 可以被认为是二维累积分布函数 (CDF).

Given a two-dimensional numerical array X of shape (m,n), I would like to compute an array Y of the same shape, where Y[i,j] is the cumulative sum of X[i_,j_] for 0<=i_<=i, 0<=j_<=j. If X describes a 2D probability distribution, Y could be thought of as the 2D cumulative distribution function (CDF).

我显然可以在双 for 循环中计算 Y 的所有条目.然而，这个计算有一个递归方面，因为 Y[i,j] = X[i,j] + Y[i-1,j] + Y[i,j-1] - Y[i-1,j-1](负索引表示 0).

I can obviously compute all entries of Y in a double for loop. However, there is a recursive aspect to this computation, as Y[i,j] = X[i,j] + Y[i-1,j] + Y[i,j-1] - Y[i-1,j-1] (where negative indexing means 0).

我正在寻找2d Python cumsum"，我发现 NumPy 的 cumsum 只是将数组展平.

I was looking for "2d Python cumsum", and I've found that NumPy's cumsum merely flattens the array.

我的问题:

1. 是否有标准的 Python 函数可以有效地计算 Y?
2. 如果不是，上面的递归思想是最优的吗?

谢谢.

推荐答案

这里可以应用一种内核分裂的方法来非常有效地解决这个问题，只需两个np.cumsum:一个垂直，一个水平(或者相反，因为这是对称的).

A kernel splitting method can be applied here to solve this problem very efficiently with only two np.cumsum: one vertical and one horizontal (or the other way since this is symatric).

这是一个例子:

x = np.random.randint(0, 10, (4, 5))
print(x)
y = np.cumsum(np.cumsum(x, axis=0), axis=1)
print(y)

结果如下:

[[1 9 8 1 7]
 [0 6 8 2 3]
 [1 3 6 4 4]
 [0 8 1 2 9]]

[[ 1 10 18 19 26]
 [ 1 16 32 35 45]
 [ 2 20 42 49 63]
 [ 2 28 51 60 83]]

这篇关于如何有效地计算二维累积和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！