Hi,
I have to use write a program in which the dictionary should be used to check whether one string is a valid word in it. Is there any dictionary library I could use? If not, how could I construct a dictionary for query?
Thanks!
+2
A:
If you have the list of words in a file, you could load them up in a std:map and use the find method on that.
Moron
2010-02-05 23:12:43
A std::set or std::tr1::unordered_set would suffice.
Manuel
2010-02-06 07:01:52
+5
A:
struct Dictionary {
Dictionary() {
// load _words, here's one possible implementation:
std::ifstream input ("/usr/share/dict/words");
for (std::string line; getline(input, line);) {
_words.insert(line);
}
}
bool contains(std::string const& word) const { return _words.count(word); }
std::set<std::string> _words;
};
Roger Pate
2010-02-05 23:14:24
If you have a modern C++ compiler or access to Boost then it'll be faster to use std::tr1::unordered_set than std::set.
Manuel
2010-02-06 07:01:01
@Manuel: Not necessarily, but even if it was, there's no reason to believe it would matter for him. And there's a benefit to keeping the automatically-sorted std::set, because you can use lower/upper_bound. Beware of premature optimization and claims of "faster" without 1) requirements or 2) speed tests.
Roger Pate
2010-02-06 14:51:13
@Roger: I've made some tests to support my claims. For a dictionary with 58000 words, looking up a single word takes, on average 0.6 microseconds with tr1::unordered_set and 0.8 microseconds with std::set. Here is the code in case you're interested: http://pastie.org/812479 . So yes, I guess there's not a big difference after all.
Manuel
2010-02-06 16:41:39
@Manuel: Good effort on real tests (though use http://codepad.org/ so you can save pastes permanently). Remember that O(1) and O(log N) are in different categories, but the first has a high constant which means the second can be nearly the same (log10 58,000 is only 5, for example). This is especially true with strings, since you have to look at the whole string to hash, and then you get to think about branch prediction (the hashing stalls lookup) and myriad other factors. Big-O notation is about categories, not about actual speed.
Roger Pate
2010-02-06 20:41:51
A related presentation I recently found (http://www.infoq.com/presentations/click-crash-course-modern-hardware) ends with "Performance analysis is not an armchair game."
Roger Pate
2010-02-06 20:43:31