我有一棵包含 125,000 个节点的树（最多 2 个子节点）。我正在尝试确定每个节点的子节点数（直接和间接）。因为树是一个 DAG ，但到每个子节点的链接数量是无限的，所以许多节点实际上会将所有其他节点都作为子节点。树的总复杂度，仅供参考，如果没有记忆，则超过 10^30。这意味着，即使存储一个指向每个子节点的简单指针（并记忆输出）也会产生 15.625GB 的数据块，甚至忽略哈希表、内存分配器和其他开销。
虽然这是所需的输出，但要实现它需要一点时间和太多内存。我只有一个工作站，具有公平但不是顶级的电源（i7 930、6GB RAM）。
有什么方法可以记忆或以其他方式缓存表，以便在合理的时间内仍然可以访问数据（我可能会对数据进行数十万次访问）？我考虑过懒惰地评估查询，但我担心访问它们需要多长时间。
此外，我对哪些节点是子节点并不特别感兴趣，但我确实需要知道它们的数量——这基本上与我相信的相同，因为我不能将同一个子节点数两次。
编辑：树是不可变的。我要做的就是阅读孩子的数量。
如果您想遍历直接无环图而不遍历节点两次（例如对每个节点计数一次），您可以mutable向每个节点添加一个布尔值，指示您之前是否遍历过该节点。您可以通过标记节点、查看节点并递归遍历节点的未标记子节点来查看节点的所有后代。
看起来您已经找到了答案，但只是为了踢球，DAG 的传递闭包可能对其他思考此类问题的人有用。
Timothy Chan在 2005 年发表了一篇论文，脚注是关于有效计算 DAG 的传递闭包。引用论文：
...对于计算未加权有向图的传递闭包的更简单问题，Yuster 和 Zwick 在最近的一篇论文中要求使用 O(mn) 时间算法，但需要 O(mn/log n + n 2 ) 时间限制实际上很容易上 RAM 这个词。2
...
2证明：假设图是无环的，因为我们可以在线性时间内预先计算强连通分量并收缩每个分量。我们想在每个顶点 u 可达的所有顶点上找到集合S u。对于逆拓扑顺序的每个顶点u，我们可以通过对从u入射的所有顶点v取S v的并集 来计算S u。通过将集合表示为 (n/log n) 字向量并使用按位或运算，可以在 O(n/log n) 时间内执行这些 O(m) 集合并集操作中的每一个。
显然还有一点需要弄清楚——你需要预先计算“强连接组件”并且必须能够以相反的拓扑顺序访问节点——但是他描述的有效地进行重复联合的过程听起来很合理计算 DAG 中给定节点的子节点数的方法。
我会在节点本身中缓存节点的后代数量。由于节点是不可变的，因此您可以计算并缓存后代计数，而不必担心缓存的值会变得陈旧。
给定节点的后代数是 1 加上其每个子节点（直接子代，而不是间接后代）的后代数之和。由于每个孩子都缓存了其后代的计数，因此这是一个非常快速的计算。
试图打破一些算法？:naughty: 最简单的方法是使用 n/nlogn( work in general ) n ( reference in general ) 情况，在这种情况下，您将存储对该表的键引用，并在需要特定映射哈希堆栈时查找。因此，例如，n根节点有n1和n2子节点，n1子节点没有被处理，而是被引用并保存在磁盘上的某个位置，但是n1根节点（这与n1子节点基本相同，但没有特权be counted ) 将被进一步处理并具有 n11 和 n12 子节点，然后 n11 根节点将被映射为对该树的引用，依此类推。因此，例如，您将只有 125,000 个引用键和指向其他引用键的指针，如果需要任何您想要的东西，您的 PC 将真正处理，
这可以通过 mapreduce 方法来完成，因为部分问题是大型数据集。这是一种非常不同的方法，因为它是在文本文件和集群领域而不是 C++ 领域，但它至少会随着机器数量而扩展，而不会过多地影响完成时间。
该方法将从表示每个有向边的键：值对开始，并建立从每个节点下降的节点集，直到每个节点都标记为完成。从两个子节点收集时，使用子集的交集，分别维护不完整节点集。这应该像每个深度级别需要 2 个地图和收集，但显然随着您上升图表而减少工作量。
它显然需要更多的计算工作，但它可以利用现有的 hadoop 等系统来轻松扩展。
我想这个答案有两个层次：a）考虑多通道方法，b）考虑使用 hadoop 等人来分配工作。