2

I just completed using a trie, but I'm curious about other methods.

How effective would it have been to load the dictionary into an array and then use a binary search function to locate words from the text file? Wouldn't binary search run faster in some cases?

Also, if memory was a concern, wouldn't an array would be a better choice?

Thanks for any responses!

Improve this question

2 Answers 2

Reset to default
2

suppose we are to implement using an array instead of a hash-table or a trie.

a main problem that we have is that we don't know the number of words in the dictionary in advance (yes, we know the number of words in the given dictionary per the specs, but our program should allow loading custom dictionaries).

as a result, we would have to dynamically go through the headache of dynamically allocating memory for our array.

but what's bad about that? aren't we dynamically allocating memory for our hash-table or trie anyway?

well, yes, but every time we are inserting a new word/character in our dictionary, we are just allocating memory for this word/character, forgetting about the ones we already inserted before, while in case of an array, we would have to keep track of the current number of elements in our array and use realloc to reallocate, in our case, a bigger block of memory when, for example, half of the capacity of our array is reached.

problem with realloc is that, after managing to allocate a new block of memory, it may copy all the contents from the original block into the new block so that the contents remain unchanged and all of this is of course costing in terms of time and memory space.

so why not set a maximum size for our array?

technically, while it may work for some cases, I wouldn't consider it a correct solution as there is no where in the specs that specifies a maximum size for our dictionary.

Improve this answer
2
  • So do you mean calling realloc wastes time? Because surely it would be easier to call realloc a few times to allocate exponentially increasing buffers to store the data structure (like how GetString is implemented in the cs50 library) than to call malloc every time a new child is generated in the case of a trie ?
    – Bobbybobbobbo
    Commented Jul 12, 2016 at 21:37
  • yes, calling realloc may be time consuming as it may have to copy all the data from the old block to the new block, as mentioned.
    – kzidane
    Commented Jul 12, 2016 at 22:32
0

I've implemented using binary search - it only slightly faster than trie implementation (with binary search load/unload are faster - dictionary already sorted, but search is slower).

Improve this answer

You must log in to answer this question.

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