4

我正在尝试在 C++ 中进行尝试，现在我的基本数据结构看起来像..

struct node{
    int count; no of times this node has been visited.
    struct node* child[ALPHABET_SIZE]; // Let ALPHABET_SIZE be 26
}

当字符串大小变大时，会浪费大量分配的内存。就像我们插入"he" 我们的树一样

root---->h--->e
    |--->e

我们看到在根目录中只有2/26th分配的内存被使用。怎么提高 ？？.

4

3 回答 3

2

一些非常基本的建议：

  1. 如果您的分支因子预计较低，请考虑为孩子使用数组以外的东西。例如，您可以有一个字母到 node* 对的数组，并对它们进行线性或二进制搜索（如果它们是有序的）。您还可以使用某种地图。
  2. 如果您不期望数百万/十亿的计数，您也可以使用较小的整数大小进行计数。
  3. 您可以从基于 arena 的分配器（即对象池）中获取节点，而不是动态分配节点，从而避免通常添加到在堆上分配的对象的堆分配开销。
于 2013-08-08T20:53:03.793 回答
0

不是为每个节点创建一个固定大小的数组，而是创建一个包含 1 个元素的数组并在插入子节点时调整它的大小（用大小 + 1 的新数组替换它）。插入会更慢，因此您可以测试和更改调整大小算法（size+1 或 size*2 或 size + size/2），以便在太慢时分配更少。

于 2013-08-13T09:44:39.857 回答
0

使用邻接表。

我们可以创建一个节点列表，而不是一棵树。一个节点将是字典，每个都有“当前值”（字母表）和“下一个状态”（子节点的索引列表）。我们可以在节点中添加其他必需的属性。

在您的情况下：列表将是 -

[{"value":"", "next_state":[1 ]}, {"value":"h", "next_state":[2]}, {"value":"e", "next_state":[ ]}]

现在说，我们添加“他的”。该列表将更新为：

[{"value":"", "next_state": [1 ]}, {"value": "h", "next_state": [2 , 3]}, {"value":"e", "next_state" :[ ]}, {"value":"i", "next_state":[4]}, {"value":"s", "next_state":[ ]},]

请注意，next_state索引 1 中的节点。我们有两个子节点——“e”和“i”。

它非常高效且易于实施。但是，trie 操作会慢很多。

于 2018-09-28T12:19:25.323 回答