我有一棵包含 125,000 个节点(最多 2 个子节点)的树。我正在尝试确定每个节点的子节点(直接和间接)的数量。因为树是一个 DAG，但是每个子节点的链接数量是无限的，所以许多节点实际上将所有其他节点作为子节点。树的总复杂度，仅供引用，如果不使用内存表示，则超过 10^30。这意味着，即使存储一个指向每个子节点的简单指针(并内存输出)也会产生 15.625GB 的数据 block ，甚至忽略哈希表、内存分配器和其他开销。
虽然这是所需的输出，但它花费的时间有点太长且内存太多。我只有一个工作站，性能一般但不是顶级(i7 930、6GB 内存)。
有什么方法可以内存或以其他方式缓存表，以便在合理的时间段内仍然可以访问数据(我可能会对数据进行数十万次访问)？我考虑过延迟评估查询，但我担心访问它们需要多长时间。
此外，我对哪些节点是子节点并不特别感兴趣，但我确实需要知道它们的数量——这基本上是一回事我相信，因为我不能把同一个 child 数两次。
编辑:树是不可变的。我要做的就是读取 child 的数量。
最佳答案
如果你想遍历一个有向无环图而不想遍历一个节点两次(比如对每个节点计数一次)，你可以给每个节点添加一个mutable bool 值来表示你是否已经遍历了之前的节点。您可以通过标记节点、查看节点并递归遍历节点未标记的子节点来查看节点的所有后代。
关于c++ - 建立许多哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10875250/