如何在具有数百万个节点的树中引用子项 [英] How to refer to children in a tree with millions of nodes

问题描述

我正在尝试构建一棵树，其中每个节点都可以有未指定数量的子节点.这棵树实际上有超过一百万个节点.

I'm attempting to build a tree, where each node can have an unspecified amount of children nodes. The tree is to have over a million nodes in practice.

我已经设法构建了树，但是当我用几千个节点填充树时，由于堆已满，我遇到了内存错误.这样做的原因是因为我试图将每个节点的子节点存储在字典数据结构(或任何与此相关的数据结构)中.因此，在运行时我已经创建了数千个这样的数据结构，因为每个节点都可以有未指定数量的子节点，并且每个节点的子节点都将存储在该数据结构中.

I've managed to contruct the tree, however I'm experiencing memory errors due to a full heap when I fill the tree with a few thousand nodes. The reason for this is because I'm attempting to store each node's children in a Dictionary data structure (or any data structure for that matter). Thus, at run-time I've got thousands of such data structures being created since each node can have an unspecified amount of children, and each node's children are to be stored in this data structure.

还有其他方法吗?我不能简单地使用变量来存储子节点的引用，因为每个节点可能有未指定数量的子节点.因此，它不像一个二叉树，我可以有 2 个变量分别跟踪左孩子和右孩子.

Is there another way of doing this? I cannot simply use a variable to store a reference of the children, as there can be an unspecified amount of children for each node. THus, it is not like a binary tree where I could have 2 variables keeping track of the left child and right child respectively.

请不要对其他方法提出建议.我有自己的理由需要创建这棵树，但不幸的是我不能这样做.

Please no suggestions for another method of doing this. I've got my reasons for needing to create this tree, and unfortunately I cannot do otherwise.

谢谢！

推荐答案

您的节点中有多少是叶"节点?也许只有当您第一次有一个孩子时才创建数据结构来存储孩子，否则保留一个空引用.

How many of your nodes will be "leaf" nodes? Perhaps only create the data structure to store children when you first have a child, otherwise keeping a null reference.

除非您需要以地图形式查找子项，否则我会使用List(以适当的容量初始化)而不是为孩子们准备的>字典<,>.听起来您的要求可能比您解释的要多，这很难说.

Unless you need to look up the children as a map, I'd use a List<T> (initialized with an appropriate capacity) instead of a Dictionary<,> for the children. It sounds like you may have more requirements than you've explained though, which makes it hard to say.

我很惊讶您在仅使用几千个节点后就失败了 - 您应该能够在出现问题之前创建大量对象.

I'm surprised you're failing after only a few thousand nodes though - you should be able to create a pretty large number of objects before having problems.

我还建议，如果您认为最终会使用大量内存，请确保您使用的是 64 位计算机，并确保您的应用程序本身设置为 64 位.(这可能只是类库的一个瘦包装器，只要类库设置为 64 位或 AnyCPU 就可以了.)

I'd also suggest that if you think you'll end up using a lot of memory, make sure you're on a 64-bit machine and make sure your application itself is set to be 64-bit. (That may just be a thin wrapper over a class library, which is fine so long as the class library is set to be 64-bit or AnyCPU.)

这篇关于如何在具有数百万个节点的树中引用子项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！