tags:

views:

202

answers:

8

I am a complete novice in C++. I am trying to read a file and build a lookup table (more like a hashtable just to check the existence of a string value). The file has about 300 thousand entries that I will use to build a lookup table. And after this, I will be performing some 1 million lookups on this. What is the most efficient way of doing this? Is it the map (google's first result) or is there a better structure for this purpose?

+4  A: 

Based on the scenario, you probably also want to look at Tries

Ravi Gummadi
+1 Just in case this bubbles up to the top, it's worth quickly mentioned hashmaps as well, so there's one good answer that includes this essential advice.
Tony
+1. With 300 thousand entries, it's probably worth it to change the complexity from the number of elements to the length of them.
David Rodríguez - dribeas
+1  A: 

Try: http://en.wikipedia.org/wiki/Unordered_map_%28C%2B%2B%29

In general hash tables are good, but if you want "the most efficient way" you'll have to provide more details.

Sheldon L. Cooper
We've been waiting for 0x for so darn long it's not even 0x anymore :p They must be using hexidecimal!
Mark
+2  A: 

map has log(n) lookups, but you can achieve O(1) with a hash table, as you suggested. It looks like STL implements one, called hash_map.

Mark
hash_map is not part of the standardized STL. I know GCC-c++ provides an implementation within the std namespace, and Visual C++ provides one in the stdext namespace, but implementations are not guaranteed to have that container.
birryree
@kuropenguin: *Is* there a standardized hash table implementation (yet)? If not, I think we have to make do with what we can find.
Mark
@Mark: Do you mean to say that hash_table is part of STL now? I am getting an include error saying that the file was not found.
Legend
@Mark: hash tables were left out of the current C++ standard, I think mostly due to the committee not wanting people to worry about hashing functions. However, in C++0x TR1, <unordered_map> will be provided, which is a hash table. You can use <unordered_map> if you are using VC++ 2008/2010, but I am not sure who else provides an implementation. I just wanted to point out there is no standardized hash table in STL, just in case the asker is just using some other compiler and starts wondering why stuff we're talking about isn't available. :)
birryree
@Legend: if you are using g++, #include <ext/hash_map> will get you hash_map. If you are using visual c++, #include <hash_map> should take care of it, but if you are using Visual C++ 2008 or 2010, I would look into using #include <unordered_map>
birryree
@Legend: I don't know.. my google searches suggests it is apart of STL, but it's not standardized, so I'm guessing it's buried in some "unofficial" part of the library, which may vary. looks you can download it here http://www.sgi.com/tech/stl/download.html if you don't already have it... or listen to kuropenguin and find `unordered_map`... or grab google's sparshhash... any half-decent hash table/map implementation should suffice
Mark
@Mark: FYI / it is bundled with some vendors' (SGI, MS, GCC) nominally "STL" library, but it is definitely not specified in the current C++ Standard document.
Tony
@Mark: Different vendors came up with different hash map extensions for the STL. Therefore, when a hash map was added by the TR1 in 2003, it was named `unordered_map`. As all of TR1, it lives in the `std::tr1::` namespaces, if your vendor supports TR1. (If not, there's an implementation of TR1 available from [boost](http://www.boost.org).) Also, `unordered_map` will be part of the upcoming C++ standard (expected next year) and will then reside in `std::` proper. Some vendors already support this. I would advice against the non-standard, non-portable `hash_map`, which will likely get abandoned.
sbi
@sbi: Fair enough. They're actually going to release 0x finally?! It's a miracle :)
Mark
@Mark: No, actually they're going to release _C++1x_. Hopefully. `:)`
sbi
@sbi: No, it'll just be 0B; they didn't tell you it was in hex?
Mark
@Mark: I think I heard that joke first ~2006, but already then I insisted that for this to fly it should be C++0xB.
sbi
@sbi: Really? And here I thought I made it up, because I'm just so darn creative!
Mark
+1  A: 

C++ std::map is not a hash table, but you could use it for a lookup table if you wanted.

Its performance characteristics as guaranteed by the C++ standard are:

  • O(log n) for searching for an element
  • O(log n) for inserting a new element
  • O(log n) for removing an element

There will definitely be memory overhead because the std::map is generally implemented with trees (and quite possibly a red-black tree), and pointers will be kept for each node in the map.

For better performance characteristics, you might want to look into Google's Sparsehash

birryree
Nice find! If it's from Google, you know it's gotta be efficient ;)
Mark
+1  A: 

If you want to check just the existance of a string value set is suffiecient as you don't have any key-value pairs. See here for documentation.

Naveen
`std::set`, like `std::map`, has O(log n) lookup time. A `hash_set` gives O(1) lookup time, but it's not in the standard yet.
dan04
I was thinking that too, but the only look-up method I see is `find()` and that's an `O(log n)` operation. http://www.cplusplus.com/reference/stl/set/find/
Mark
@Mark: Yes, it is `O(log n)`, but all the hash* containers are not part of the standard, so I don't think any better alternative exists as part of standard C++. If OP can use the extensions provided by compiler then certainly hash_set will be better IMO.
Naveen
A: 

If your biggest concern is look up time (and it sounds like it is) strongly consider a hashmap. The amortized look up time is O(1) which is notably better than a regular map at O(log n).

JoshD
+4  A: 

What you need is TRIE data structure. The dictionary is implemented widely using this data structure. Moreover it has O(n) lookup time where n is the length of the string and occupies less space. Trie has the abilities to quickly search for, insert, and delete entries.

Prabhu Jayaraman
It's difficult here to say which of a `unordered_set` or Trie will be best. The Trie should be more compact, for sure, but it involves more dereferences (one at each letter). I suppose it'll depend strongly on the search pattern too: Trie favor ordered searches (or nearly ordered) as do binary trees, because the nodes are still hot in the cache.
Matthieu M.
A: 

If you have a very good hash function (no collision on your dataset) and you just need to check if entry exists or not, you try a bitset (say from http://bmagic.sourceforge.net/)

i believe it can reduce memory requirements and it's very fast.

ury