Re: Hash map to categorize users.
On Sep 13, 2:43 pm, LR <lr...@superlink.net> wrote:
Thats food for thought.
I wanted to avoid just having a map<string, string>
implementation as there would be several users per group,
but I guess a pointer to a vector of groups would be a nice
way around that.
Sorry, but why?
Did I misread your original request?
You have many users, each user is a member of a group, you
want to be able to look up a particular user to see what
groups they are a member of.
std::map<std::string,std::string> will work just fine for
that. Is there some other requirement or concern you have
that I'm missing or didn't understand?
As for numbers I would expect to have maybe 1000 in each of
the three groups, so I guess I would see benifits of a hash
Probably. Well, maybe. But 1000 doesn't really sound like a
very big number to me. In a Red Black tree (I think that many
std::maps are implemented with RBTs) I think that's going to
be at most 10 levels. It might not save you that much.
It could be up to 20 levels in an RB tree; the maximum depth is
2*(lg n). But still... A couple of thousand isn't all that
many. It's a borderline case: if the lookup was in a tight,
critical loop, then using a hash table could make a difference.
Otherwise, it's probably not worth it.
I guess another question is, how often are you going to have
to read that file? If the answer is 5000 times a day, then
look into speed problems (but not yet). If the answer is once
a month, then maybe not to worry.
Even for 5000 times a day, I wouldn't worry. That's only 3 or 4
times a second. You might want to have a look at
http://kanze.james.neuf.fr/code/Docs/html/Hashcode.html; it's a
summary of some measurements I made a while back. It's not
really very up to date, but just as an example, running on a
very old Sun Sparc (very slow compared to modern PC's), for a
table with over 15000 entries, std::map only required 4.22
microseconds per lookup. That's well over 200000 lookups per
second. This may be three times slower than the fastest hash
lookup, but it's still fast enough for most applications. (And
as I said, a modern PC will be even faster.)
James Kanze (GABI Software) email:email@example.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34