Just a quickie I'm not sure about.
If I did a linear search (t'is linear, right?) like this:
How does that compare to the std::find() function? Or is it (std::find()) implementation specific?Code:/* GetItemByName */ Item* ItemManager::GetItemByName( const std::string& name ) const { std::list<Item*>::const_iterator it = items.begin(); for ( ; it != items.end(); it++ ) { Item* i = (*it); if ( i->name == name ) return i; } return 0; // Doesn't exist }
Last edited by cboard_member; 06-21-2006 at 01:07 PM.
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
linear not difference
Kuphryn
What?
EDIT: I mean, explain. Evidence.
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
I'm not sure how it compares. I'm sure performance wise, find() will be faster. However, list implements a linear (or sequential) search too.
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
Actually nevermind, I did some profiling.
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
And what did you find? They should be roughly the same, although the fact that you are storing pointers might make it more difficult to use find(). I would prefer the algorithm, though, if you can use it.
std::find exists for a reason. For starters it's shorter, and less likely to have a bug than hand-rolled code.
Though if you ever find yourself coding a linear search, then there is a very very good chance that you're not using the best container for the job.
I assume std:: list is implemented as doubly linked list and I think that your search and find algorithm will have same performace (both will be linear- O(N)),.
Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem
They were both roughly the same after getting past some difficulties as Daved said. I'm pretty sure I'm using the wrong container: it took about 4 seconds to find the 9999th item (or was it 99999th. Can't remember).
Which would be more appropriate (in case I don't get around to reading it up today)?
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
Maybe it is better to use map/multimap container when inserting elements. Searching will be logarithmic since internally map is a Balanced Binary Tree. So if search/find operation is often use I suggest multimap container.
Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem
Multimap it is. First, I've got to learn how to use it.
To arms!
Or google.
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
http://www.sgi.com/tech/stl/
It also tells you for most things what the O(n) complexity of the various things are.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Thankies.
Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.
- Mike McShaffry
If you are doing all your insertions at once in the beginning, and then searching afterwards, then a vector would probably be even better than a map/multimap/set/multiset. Fill the vector with all your data, then sort it, then use binary_search, lower_bound, and/or upper_bound to find what you are looking for. This will be even better than the map solutions because those keep the data sorted as you are inserting which is a bit slower than sorting it once at the end. In addition, the vector uses less memory overhead than the map solutions.
Another option is the unordered_map/unordered_multimap that will be part of the next standard. You can find an implementation from boost if your library doesn't have one. They're basically hashed maps, which have even faster lookups than the regular map or binary_search.
You should put the call to items.end() outside the for loop for best results, i.e.
Code:std::list<Item*>::const_iterator it = items.begin(); std::list<Item*>::const_iterator end = items.end(); for ( ; it != end; it++ ) { }
The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.
