我有以下数据:
A = [a0 a1 a2 a3 a4 a5 …. a24]B = [b0 b1 b2 b3 b4 b5 …. b24]然后,我想要乘以如下:
C = A * B’= [a0b0 a1b1 a2b2 … a24b24]这显然……
你可以添加另一个数组D来标记A中已更改/未更改的值。每次检查此数组以决定是否进行新的乘法运算。
在...上 的 非常前5 强> 数据集可以节省多达50次乘法。但在那之后它是一条平坦的乘法之路。因为对于前5个集合之后的每个集合,您需要乘以新的数据集。
我假设所有数组都初始化为零。 考虑到整体的乘法量,我不认为那50个被保存是有用的。
但是我仍然会给你一个关于如何保存这些50的提示,也许你可以找到它的延伸?
第一个数据集到达:乘以第一个数据集 a 设置每个数据 b 。保存 的 所有 强> 在 a ,只复制 a[0] 至 a[4] 至 c 。 的 这里有25次乘法 强> 。
a
b
a[0]
a[4]
c
第二个数据集到达:仅乘以 a[0] 至 a[4] (拥有新数据) b[0] 至 b[4] RESP。保存 a[0] 至 a[4] ,复制到 a[0->9] 至 c 。 的 这里有5次乘法 强>
b[0]
b[4]
a[0->9]
到达第3个数据集:乘以 a[0] 至 a[9] 同 b[0] 至 b[9] 这个时候复制到相应的 a[0->14] 至 c 。 的 这里有10次乘法 强>
a[9]
b[9]
a[0->14]
第4个数据集:乘以 a[0] 至 a[14] 与相应的 b 复制相应的 a[0->19] 至 c 。 的 这里有15次乘法 强> 。
a[14]
a[0->19]
第5组数据:多了 a[0] 至 a[19] 与相应的 b 复制相应的 a[0->24] 至 c 。 的 这里有20次乘法 强> 。
a[19]
a[0->24]
总保存多重: 的 50 强> 乘法。
第6组数据:通常的数据乘法。 的 每个25 强> 。这是因为对于数组中的每个集合 a 有一个新的数据集可用,所以乘法是不可避免的。
有没有快速的方法来利用数据通过A转移而不是全新的事实?
即使你所做的只是转移并向A添加新元素,C中的产品通常都会有所不同,因为其中一个操作数通常会在每次迭代后发生变化。如果您有关于A或B元素结构的方式的其他信息,您可以使用该结构来减少乘法的数量。除非考虑到这些结构因素,否则每个循环都需要计算所有25个产品。
理想情况下,我希望最小化乘法运算的数量(可能需要更多的加法/减法/累加)。
理论上,通过移位和添加数组元素来模拟乘法,可以将乘法次数减少到0。实际上,这将比硬件乘法慢,所以你最好只使用任何可用的基于硬件的乘法,除非你没有提到一些额外的相关约束。