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 に動的に割り当てる必要があるとは思わなかったという設計上の決定でした。