Performance of the std::map during a search

Hi,

I am writing code that is using std::map and having a bit of an issue
with its performance.

It appears that the std::map is significantly slower searching for an
element then a sequential search in a vector.

Has anyone run into this before?

re: Performance of the std::map during a search

mveygman@gmail.com wrote:The elements in a map are sorted on insertion, what are you attempting
to do?

--
Ian Collins.

re: Performance of the std::map during a search

Hi,


<mveygman@gmail.comwrote in message
news:1f4f63f2-3359-44a2-a8d4-ad6a35776931@c4g2000hsg.googlegroups.com...Do you use map.find ? Otherwise post some code.

e.g.

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
map<string, stringDict;
Dict[ "boek" ] = "book";
Dict[ "winkel" ] = "shop";

map<string,string>::iterator Found = Dict.find( "boek" );
if( Found != Dict.end() )
{

cout << Found->first << " translates to " << Found->second << " (or
vice versa) " << endl;

}
else
{
cout << "No such word" << endl;
}
return 0;
}





Regards, Ron AF Greve

http://www.InformationSuperHighway.eu

re: Performance of the std::map during a search

On 2007-12-22 00:57, mveygman@gmail.com wrote:For small collections that might be true, but for larger sets map should
be faster (if used correctly), unless perhaps if the vector is sorted
and you use a binary search.

--
Erik Wikström

re: Performance of the std::map during a search

On Dec 22, 8:46 am, Erik Wikström <Erik-wikst...@telia.comwrote:
Operating key word being "should".

The assumption that I went in with was that this was the case and
worst case scenario would be that serial search of the vector and
serial search of the map would be on par for time. They are not even
close.

Regards,

Mikhail

re: Performance of the std::map during a search

On Dec 21, 8:07 pm, "Ron AF Greve" <ron@localhostwrote:

Here is the test code:

#include <map>
#include <vector>
#include <iostream>
#include <ostream>
#include <sys/time.h /* gettimeofday */

unsigned long get_current_time()
{
struct timeval tv;
long usec;
gettimeofday (&tv, NULL);
usec = tv.tv_sec * 1000000;
usec += tv.tv_usec;
return usec;
}

int main(int argc, char **argv)
{
std::map< unsigned int, unsigned int test_map;
std::vector< unsigned int test_vector;

std::cout << "Setting up the test" << std::endl;

for (unsigned int i=0; i < 1000000; ++i)
{
test_map[i]=i;
test_vector.push_back(i);
}
std::random_shuffle(test_vector.begin(), test_vector.end());

time_t seed = time(NULL);

srand(seed);
unsigned long vec_start = get_current_time();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::vector< unsigned int >::const_iterator end_itr =
test_vector.end();
std::vector< unsigned int >::const_iterator itr =
test_vector.begin();
for( ; itr == end_itr ; ++itr )
{
if( *itr == value_to_find )
{
break;
}
}
}
unsigned long vec_end = get_current_time();

srand(seed);
unsigned long map_start = get_current_time();
for(unsigned int i=0; i < 500000; ++i)
{
unsigned int value_to_find = rand() % 1000000;
std::map< unsigned int, unsigned int >::iterator itr =
test_map.find(value_to_find);
}
unsigned long map_end = get_current_time();

std::cout << "Vec Test took " << (vec_end - vec_start) << "
microseconds. Map test took " << (map_end - map_start) << "
microseconds." << std::endl;
}

re: Performance of the std::map during a search

<mveygman@gmail.comwrote in message
news:d2e7c7db-4636-4e17-8c30-dd4aa5f41b9b@s19g2000prg.googlegroups.com.......Since itr == end_itr is always false, the loop always exists immediatly, so you
don't search the vector at all.
This should be itr != end.
If I change this, the vector version takes a lot more time .

re: Performance of the std::map during a search

On Dec 24, 11:44 am, "Hans Bos" <hans....@xelion.nlwrote:
That would explain everyting. :)))

re: Performance of the std::map during a search

On 2007-12-24 17:04, mveygman@gmail.com wrote:Searching a map is O(log n) while a sequential search of a map is O(n),
which means that when the number of elements is large a map should be
faster. Exactly how many elements you need to have before the map is
faster depends on a lot of things but I would guess that with 1000
elements the map is almost always faster on a modern PC. On the other
hand if the vector is sorted then it might be faster searching the
vector using lower_bound() which is also O(log n), but most other
operations will still be faster on the map.

--
Erik Wikström