c# - 构建非重组三叉树时如何避免 C# 中的 System.OutOfMemoryException

Question

我“成功地”实现了一个非重组三叉树来为某些固定 yield 衍生品定价。 (如下图所示 - 但三个分支没有重新连接)

不幸的是，我可以使用的节点数量受到可用内存的严重限制。如果我构建一棵具有 20 个时间步的树，这将产生 3^19 个节点(因此有 11 亿个节点)

每个时间步的节点保存在List<Node>中这些数组存储在 Dictionary<double,List<Node>> 中

每个节点都通过 new Node(...) 实例化.我还通过 new Class() 实例化了每个列表和字典。也许这是我错误的根源。

还有 System.OutOfMemoryException不是因为 Dictionary/List-Object 太大(通常是这种情况)而抛出，而是因为我似乎有太多节点 - 过了一会儿 new Node(...)无法分配任何进一步的内存。我认为最终 2GB 的最大 List-Capacity 也会发挥作用 - 看看 List 如何随着每个时间步长呈指数级增长。

也许我的数据结构太浪费或不适合手头的任务。

一个可能的解决方案是将树保存到文本文件中，从而完全避免内存问题。然而，这需要一个巨大的解决方法。

编辑: 添加更多背景。我需要树来为依赖于路径的产品定价。这意味着不幸的是我将不得不访问所有节点。更重要的是，在树建成后，我从树叶开始，及时倒退以确定价格。我也已经只生成了我需要的节点。

编辑2: 我已经给出了一些主题，并且还考虑了各种响应。难道我只需要将相应的树级别序列化到硬盘驱动器。所以基本上-我创建一个时间步长(List<Node>)将其写入磁盘等。稍后当我从叶子开始时-我只需要以相反的顺序加载它。

Answer 1

您基本上有两种选择。仅评估您关心的分支(Andrew 的 yield )并且不存储结果或构建您的树并将其保存到磁盘并在其顶部实现自定义集合接口(interface)以访问正确的部分磁盘。在这种情况下，您仍将在进程内存中保留最少量的数据，并依靠操作系统进行适当的磁盘缓存以加快访问速度。如果您开始使用大型数据集，第二个选项是您工具带中的一个很好的工具，因此您应该在编写这个时考虑到重用。