c - 特里，C 代码。效率低？

Question

我看到有些人将这种结构用于 Trie 节点：

struct trie_node_st {
        int count;
        struct trie_node_st *next[TREE_WIDTH];
};

是低效率，因为我们并不总是需要TREE_WIDTH每个数组的长度。

还是我误解了什么？

Answer 1

这是 CPU/内存的权衡。通过预先分配它，您使用一定的最小内存量来存储这些指针 (TREE_WIDTH * sizeof (struct trie_node_st *)) 字节，稍后您将使用更少的 CPU，因为这是在编译时完成的（除非您使用 malloc( ））。但是，这几乎不是开销。即使你有很多指针，也没关系。可能的设计决策只是程序员不想在每次使用该结构时都动态分配指向 struct trie_node_st 的指针数组。