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

Question

我已经"成功"实施了一个非重组三叉树来定价某些固定收益衍生品.(如下图所示 - 但有三个分支没有重新连接)

不幸的是,事实证明我可以使用的节点数量受可用内存的严重限制.如果我构建一个具有20个时间步长的树,则会产生3 ^ 19个节点(因此1,1亿个节点)

保存每个时间步的节点,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

我们这里遇到的是一个经典问题，即预先进行大量处理......然后将所有内容存储到内存中以供稍后处理。

虽然很简单，但如果条件足够严酷（比如有十亿个条目），它就会耗尽所有内存。

现在，OP并没有真正指定树的意图是什么或者它将如何使用......但我建议不要一次性构建它......根据需要构建它。

惰性评估yield

与其一次性完成所有事情并必须存储它……只在您真正需要时才执行可能是理想的选择。查看这篇文章以获取更多信息和使用示例yield。

如果你需要多次遍历树，这不会很好地工作......但它仍然可以让你比现在有更深的深度。