arrays - 如何分解二维数组算法？

Question

我有一个算法，它接受一个 2D 数组大小(in_x,in_y)并吐出另一个 2D 数组 size (out_x, out_y)。

out_x <= in_xout_y < in_y这意味着在宏大意义上正在发生一些积累。该算法本身是按照一些物理方程分阶段完成的简单移位累加，其中中间结果存储在 3D 数组中。

我想确定哪些元素in对out.

一个类似的方程式 out[i,j] = sum_{m,n} in[m,n]告诉我m,n每个i,j.

MRE

对于 2D array 的输入Input=ones ((8,16))，我记录了所有发生的计算：

Iteration=0: State.shape=(8, 4, 16)
Iteration=0: State[:,0,:] = Input
Iteration=0: iter=1 State[:,1, 1:] = State[:,0,1:] + Input[:,:-1]
Iteration=0: iter=2 State[:,2, 2:] = State[:,1,2:] + Input[:,:-2]
Iteration=1: new State.shape=(4, 4, 16) old State.shape=(8, 4, 16)
Iteration=1: iter=0 new.State[0, 0, 16:16] = old.State[0, 0, 16:16]
Iteration=1: iter=0 new.State[0, 0, 0:16] = old.State[0, 0, 0:16] + old.State[1, 0, 0:16]
Iteration=1: iter=1 new.State[0, 1, 15:16] = old.State[0, 0, 15:16]
Iteration=1: iter=1 new.State[0, 1, 0:15] = old.State[0, 0, 0:15] + old.State[1, 0, 1:16]
Iteration=1: iter=2 new.State[0, 2, 15:16] = old.State[0, 0, 15:16]
Iteration=1: iter=2 new.State[0, 2, 0:15] = old.State[0, 0, 0:15] + old.State[1, 1, 1:16]
Iteration=1: iter=0 new.State[1, 0, 16:16] = old.State[2, 0, 16:16]
Iteration=1: iter=0 new.State[1, 0, 0:16] = old.State[2, 0, 0:16] + old.State[3, 0, 0:16]
Iteration=1: iter=1 new.State[1, 1, 15:16] = old.State[2, 0, 15:16]
Iteration=1: iter=1 new.State[1, 1, 0:15] = old.State[2, 0, 0:15] + old.State[3, 0, 1:16]
Iteration=1: iter=2 new.State[1, 2, 15:16] = old.State[2, 0, 15:16]
Iteration=1: iter=2 new.State[1, 2, 0:15] = old.State[2, 0, 0:15] + old.State[3, 1, 1:16]
Iteration=1: iter=0 new.State[2, 0, 16:16] = old.State[4, 0, 16:16]
Iteration=1: iter=0 new.State[2, 0, 0:16] = old.State[4, 0, 0:16] + old.State[5, 0, 0:16]
Iteration=1: iter=1 new.State[2, 1, 15:16] = old.State[4, 0, 15:16]
Iteration=1: iter=1 new.State[2, 1, 0:15] = old.State[4, 0, 0:15] + old.State[5, 0, 1:16]
Iteration=1: iter=2 new.State[2, 2, 15:16] = old.State[4, 0, 15:16]
Iteration=1: iter=2 new.State[2, 2, 0:15] = old.State[4, 0, 0:15] + old.State[5, 1, 1:16]
Iteration=1: iter=0 new.State[3, 0, 16:16] = old.State[6, 0, 16:16]
Iteration=1: iter=0 new.State[3, 0, 0:16] = old.State[6, 0, 0:16] + old.State[7, 0, 0:16]
Iteration=1: iter=1 new.State[3, 1, 15:16] = old.State[6, 0, 15:16]
Iteration=1: iter=1 new.State[3, 1, 0:15] = old.State[6, 0, 0:15] + old.State[7, 0, 1:16]
Iteration=1: iter=2 new.State[3, 2, 15:16] = old.State[6, 0, 15:16]
Iteration=1: iter=2 new.State[3, 2, 0:15] = old.State[6, 0, 0:15] + old.State[7, 1, 1:16]
Iteration=1: iter=3 new.State[3, 3, 14:16] = old.State[6, 1, 14:16]
Iteration=1: iter=3 new.State[3, 3, 0:14] = old.State[6, 1, 0:14] + old.State[7, 1, 2:16]
Iteration=2: new State.shape=(2, 5, 16) old State.shape=(4, 4, 16)
Iteration=2: iter=0 new.State[0, 0, 16:16] = old.State[0, 0, 16:16]
Iteration=2: iter=0 new.State[0, 0, 0:16] = old.State[0, 0, 0:16] + old.State[1, 0, 0:16]
Iteration=2: iter=1 new.State[0, 1, 15:16] = old.State[0, 0, 15:16]
Iteration=2: iter=1 new.State[0, 1, 0:15] = old.State[0, 0, 0:15] + old.State[1, 0, 1:16]
Iteration=2: iter=2 new.State[0, 2, 15:16] = old.State[0, 1, 15:16]
Iteration=2: iter=2 new.State[0, 2, 0:15] = old.State[0, 1, 0:15] + old.State[1, 1, 1:16]
Iteration=2: iter=3 new.State[0, 3, 14:16] = old.State[0, 1, 14:16]
Iteration=2: iter=3 new.State[0, 3, 0:14] = old.State[0, 1, 0:14] + old.State[1, 1, 2:16]
Iteration=2: iter=4 new.State[0, 4, 14:16] = old.State[0, 1, 14:16]
Iteration=2: iter=4 new.State[0, 4, 0:14] = old.State[0, 1, 0:14] + old.State[1, 2, 2:16]
Iteration=2: iter=0 new.State[1, 0, 16:16] = old.State[2, 0, 16:16]
Iteration=2: iter=0 new.State[1, 0, 0:16] = old.State[2, 0, 0:16] + old.State[3, 0, 0:16]
Iteration=2: iter=1 new.State[1, 1, 15:16] = old.State[2, 0, 15:16]
Iteration=2: iter=1 new.State[1, 1, 0:15] = old.State[2, 0, 0:15] + old.State[3, 0, 1:16]
Iteration=2: iter=2 new.State[1, 2, 15:16] = old.State[2, 1, 15:16]
Iteration=2: iter=2 new.State[1, 2, 0:15] = old.State[2, 1, 0:15] + old.State[3, 1, 1:16]
Iteration=2: iter=3 new.State[1, 3, 14:16] = old.State[2, 1, 14:16]
Iteration=2: iter=3 new.State[1, 3, 0:14] = old.State[2, 1, 0:14] + old.State[3, 1, 2:16]
Iteration=2: iter=4 new.State[1, 4, 14:16] = old.State[2, 1, 14:16]
Iteration=2: iter=4 new.State[1, 4, 0:14] = old.State[2, 1, 0:14] + old.State[3, 2, 2:16]
Iteration=3: new State.shape=(1, 8, 16) old State.shape=(2, 5, 16)
Iteration=3: iter=0 new.State[0, 0, 16:16] = old.State[0, 0, 16:16]
Iteration=3: iter=0 new.State[0, 0, 0:16] = old.State[0, 0, 0:16] + old.State[1, 0, 0:16]
Iteration=3: iter=1 new.State[0, 1, 16:16] = old.State[0, 0, 16:16]
Iteration=3: iter=1 new.State[0, 1, 0:16] = old.State[0, 0, 0:16] + old.State[1, 1, 0:16]
Iteration=3: iter=2 new.State[0, 2, 15:16] = old.State[0, 1, 15:16]
Iteration=3: iter=2 new.State[0, 2, 0:15] = old.State[0, 1, 0:15] + old.State[1, 1, 1:16]
Iteration=3: iter=3 new.State[0, 3, 15:16] = old.State[0, 1, 15:16]
Iteration=3: iter=3 new.State[0, 3, 0:15] = old.State[0, 1, 0:15] + old.State[1, 2, 1:16]
Iteration=3: iter=4 new.State[0, 4, 14:16] = old.State[0, 2, 14:16]
Iteration=3: iter=4 new.State[0, 4, 0:14] = old.State[0, 2, 0:14] + old.State[1, 2, 2:16]
Iteration=3: iter=5 new.State[0, 5, 14:16] = old.State[0, 2, 14:16]
Iteration=3: iter=5 new.State[0, 5, 0:14] = old.State[0, 2, 0:14] + old.State[1, 3, 2:16]
Iteration=3: iter=6 new.State[0, 6, 13:16] = old.State[0, 2, 13:16]
Iteration=3: iter=6 new.State[0, 6, 0:13] = old.State[0, 2, 0:13] + old.State[1, 3, 3:16]
Iteration=3: iter=7 new.State[0, 7, 13:16] = old.State[0, 3, 13:16]
Iteration=3: iter=7 new.State[0, 7, 0:13] = old.State[0, 3, 0:13] + old.State[1, 4, 3:16]

Final output=
[[8. 8. 8. 8. 8. 8. 8. 8.]
 [8. 8. 8. 8. 8. 8. 8. 8.]
 [8. 8. 8. 8. 8. 8. 8. 8.]
 [8. 8. 8. 8. 8. 8. 8. 8.]
 [8. 8. 8. 8. 8. 8. 8. 8.]
 [8. 8. 8. 8. 8. 8. 8. 8.]
 [8. 8. 8. 8. 8. 8. 8. 8.]
 [9. 9. 9. 9. 9. 9. 9. 9.]]

请注意，最后一个State shape=(1, 8, 16)，只需要前 8 列。

尝试 1

我尝试搜索计算图，但我找到的所有资源都用于深度学习。我可以使用执行 autograd 的张量，但我想询问社区是否有专门的工具来执行此操作。

最终目标

我想加快操作。一种方法是使用类似numbaJIT 编译代码的方法，但这不可避免地会考虑分支和中间 3D 数组。

我最终会使用这组方程式来编写内在代码（仅包含加载/存储/累积）。

标签： arraysalgorithmcomputation