My speller seems to be working a-okay, but the dictionary load time is about 0.08 seconds slower than the staff implementation, and i wondered if that had something to do with an overlarge trie structure.

Valgrind suggests:

==9416== HEAP SUMMARY:
==9416== in use at exit: 0 bytes in 0 blocks
==9416== total heap usage: 367,084 allocs, 367,084 frees, 82,227,504 bytes allocated
==9416== All heap blocks were freed -- no leaks are possible
==9416== For counts of detected and suppressed errors, rerun with: -v
==9416== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

so is err 80 million bytes a little large for a 143091 word dictionary....?




On a 64 bit system, your trie node is probably 27*8 (27 pointers) plus 1*8 (1 boolean), in total 224 bytes (on a 32 bit system, it would be half of that). You have about 2-3 nodes per entry on average (because many words have common word stems, they share those nodes), which sounds plausible.

So, at least in my view, this seems ok.


If your node size is in the neighborhood of 224 bytes (27 pointers and a bool), then 367,084 nodes requires around 82 million bytes.

The word count is not as significant as the letter count in the trie structure. There are roughly 1.3 million letters in the large dictionary.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .