Menu
I am implementing a text-based version of Scrabble for a College project.
My dictionary is quite large, weighing in at around 400.000 words (std::string).
Searching for a valid word will suck, big time, in terms of efficiency if I go for a vector<string> ( O(n) ). Are there any good alternatives? Keep in mind, I'm enrolled in freshman year. Nothing TOO complex!
Thanks for your time!
Francisco
590
The std::deque container is most efficient when appending items to the front or back of a queue. Unlike std::vector , std::deque does not provide a mechanism to reserve a buffer.
vector will outperform list for almost every use case.
A Random Access Container is a Reversible Container whose iterator type is a Random Access Iterator. It provides amortized constant time access to arbitrary elements.
If you wanted to go for something that is in the standard library, you could use std::set with the word as the key. That would give you logarithmic search time.
Since your dictionary is presumably static (i.e. created once and not modified), you could also use a std::vector, sort it using std::sort, and then use std::binary_search on the sorted vector to find a word. This would also give logarithmic search time, and would possibly be more space efficient than a set.
If you want to implement your own data structure, a trie would be a good choice.
165
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
