Return to Answer

suppose we are to implement speller 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 copies 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.

suppose we are to implement speller 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.

suppose we are to implement speller 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 copies 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.

so assuming there was a maximum size specified for our dictionary

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?

in practice, probably looking up a word in a trie would be slightly faster, in the worst case, as the time complexity for that operation would be O(m), where m is the length of the word we're looking for.

looking up a word using binary search would require determining first where the word we're looking for is in the dictionary. this is probably a O(m log n) operation, in the worst case, as we would have to compare the words to see whether we should go left or right or that they match. no, we don't necessarily have to compare all characters of both words every time, but think the worst case.

looking up a word using a hash-table being faster than an array or a trie, totally depends on how the hash-table is implemented, but I think it's possible.

for example, if we have a hash function that is good enough so that we end up with one or two words in each bucket, we may end up with a O(1) in average case when loading and checking, but in the worst case, an array probably wins.

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

I think using an array is efficient enough in terms of memory space, perhaps more efficient than hash-tables and tries, for the implementations that I can think of as you probably wouldn't have to store a character more than the ones already in your dictionary.

suppose we are to implement speller 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 copies 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.

suppose we are to implement speller 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 copies 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.

suppose we are to implement speller 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 copies 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.

so assuming there was a maximum size specified for our dictionary

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?

in practice, probably looking up a word in a trie would be slightly faster, in the worst case, as the time complexity for that operation would be O(m), where m is the length of the word we're looking for.

looking up a word using binary search would require determining first where the word we're looking for is in the dictionary. this is probably a O(m log n) operation, in the worst case, as we would have to compare the words to see whether we should go left or right or that they match. no, we don't necessarily have to compare all characters of both words every time, but think the worst case.

looking up a word using a hash-table being faster than an array or a trie, totally depends on how the hash-table is implemented, but I think it's possible.

for example, if we have a hash function that is good enough so that we end up with one or two words in each bucket, we may end up with a O(1) in average case when loading and checking, but in the worst case, an array probably wins.

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

I think using an array is efficient enough in terms of memory space, perhaps more efficient than hash-tables and tries, for the implementations that I can think of as you probably wouldn't have to store a character more than the ones already in your dictionary.