algorithm - 使用缓存计算树结构中的总和

Question

我需要知道什么类型的算法可以借助缓存机制有效地计算树结构中的和。

我想解决的问题很简单:有两种类型的节点:文件夹 (F) 和文件 (L) ...看起来像一个文件系统:) ...

可以在树结构中创建和移动文件夹和文件。文件大小不断变化。

现在我想要一个返回节点内容大小的函数 size(node)。

示例:

F1
 - L1 : 10
 - L2 : 33
F2 
 - F21
    - F211
         - L3 : 2
         - L4 : 8
    - F212
         - F2121
               - L5 : 18
         - F2122
               - L6 : 21
               - L7 : 3            

size(node) gives:

size(F1):43
size(F2):52
size(F21):52
size(F211):10
size(F212):42
size(L5):18
...

已知的解决方案是递归累加 :) ...

size(node) 
  int res=0;
  if(node is File)
    return sizeOfFile(node)
  else
    for each child of node
      res += size(child)
    end 
  end
  return res
end

我问自己是否可以在这里使用某种类型的缓存。我需要搜索的算法的名称和类型是什么？

Answer 1

您可以做一件事。您可以在访问节点并存储它时计算成本。把它想象成手机或电脑上的存储空间。这里有一个例子会更好。

我这里没有给出任何节点的成本。假设您访问节点号 4。您通过将 6 和 7 的成本相加来计算成本并将其存储在数据库中。在数据库上，这可以存储为 directory path -- cost 。现在假设您要计算 2 的成本。您不需要访问 4，因为您已经预先计算了成本。您只需计算 5 的成本即可。因此，我们将 5 和 2 的成本存储在数据库中。下次如果您想知道 4 或 5 的大小，您可以从数据库中获取它。

我假设这是一个文件结构。因此，您将需要更频繁地访问目录。您访问的次数越多，存储的尺寸就越多。计算成本越容易。最后，如果您更改文件或移动它们，只需计算该节点的成本即可。

我认为这里的优势在于您不需要在每次访问节点时都计算成本。随着时间的流逝，您将使用一种可以使您的大小计算速度更快的存储。

希望这是有道理的。