optimization - 在不使用额外内存的情况下反转嵌套循环的顺序

Question

我不确定这是数学（代数）问题还是编程问题。

我有一个嵌套循环（在着色器程序中），它做这样的事情（L 和 B 是只读的）：

for each L in (L1, L2)
  Q=L
  for each B in (B1, B2, B3)
    Q *= B
  result += Q

所以这个循环的结果是：

result += L1*B1*B2*B3 + L2*B1*B2*B3

这是正确的结果，但是 B 的访问速度很慢，而 L 的访问速度很快。因此，在内部循环中迭代 B 比在内部循环中迭代 L 慢得多（我在上面读取了每个 B两次，每个 L 一次）。

如果我们天真地反转内/外循环，

for each B in (B1, B2, B3)
  Q=B
  for each L in (L1, L2)
    Q *= L
  result += Q

当然这个结果变成

result += B1*L1*L2 + B2*L1*L2 + B3*L1*L2

我在这里读过每个 B 一次，但这个结果是错误的。我需要形式的产品L1*B1*B2*B3。我知道我可以创建一个数组Q[2]并执行以下操作：

对于每个 L
  Q[i] = L _i // 存入数组

然后迭代B：

for each B in (B1, B2, B3)
  for i = 1..2
    Q[i] *= B

result += Q[i]

这使

result += Q[1]*B1*B2*B3 + Q[2]*B1*B2*B3

这是正确的，但是如果L很大（确实如此），它会“有点*”浪费内存。我想知道我是否可以在没有中间L[]数组的情况下以代数方式做到这一点。

_{* 双关语意}

score 2 · Accepted Answer

一种没有嵌套循环的方式：

result = 0
for each L in (L1, L2)
  result += L
for each B in (B1, B2, B3)
  result *= B

因为

L1*B1*B2*B3 + L2*B1*B2*B3

减少到

B1*B2*B3*(L1+L2)

score 0 · Accepted Answer

0

我可能把问题弄错了，但不L1*B1*B2*B3 + L2*B1*B2*B3等于(L1+L2)*B1*B2*B3？

于 2012-08-31T18:09:28.360 回答

2 回答 2