C++

Forum

 
Optimizing using lower_bound (not working!)

brgms (4)
Well, i was trying to optimize this piece of code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
list<Nhood>::iterator bd;
    for (bd = bd_nhood.begin();bd!=bd_nhood.end();++bd)
    {
	f=true;
	for(k=0;(k<G_QI_DIMENSION && f);++k)
	{
           if (g.min[k] != (*bd).min[k]) f=false;
           if (g.max[k] != (*bd).max[k]) f=false;
        }

        if (f==true)
	{
	   (*bd).tuples.push_back(*it3);
	   (*it3)->nhood=&(*bd);
	   break;
	}
    }
    if (f==false)
    {
       g.tuples.push_back(*it3);
       bd_nhood.push_front(g);
       (*it3)->nhood=&bd_nhood.front();
    }


which is called about 200000 times in my program.
bd_nhood also has a size of 200000.

so i though having bd_nhood sorted beforehand, and then using lower_bound to check if there was already an object with the same array values.
if true, modify that object, otherwise create a new one at that iterator's position.
so i made the folowing changes:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
    list<Nhood>::iterator bd;
    bd=lower_bound(bd_nhood.begin(),bd_nhood.end(),g);
    if (g==(*bd))
    {
	(*bd).tuples.push_back(*it3);
	(*it3)->nhood=&(*bd);
    }
    else
    {
       g.tuples.push_back(*it3);
       bd_nhood.insert(bd,g);
       (*it3)->nhood=&(*bd);
    }


note that i overloaded the == operator with

1
2
3
4
5
6
7
8
9
10
11
 
bool Nhood::operator==(const Nhood &n2)
	{
		bool f=true;

		for(int k=0;(k<G_QI_DIMENSION && f);++k)
		{
			if (min[k] != n2.min[k]) f=false;
			if (max[k] != n2.max[k]) f=false;
		}
		return f;
	}



However, whilst before my code took like 500 seconds to complete, using the lower_bound implementation is taking about 800 seconds! shouldn't it be better this way? thank you in advance
Topic archived. No new replies allowed.