the vectors seem to run very slow

vagelis (106)
how can i run in release mode in visual studio??
Last edited on
m4ster r0shi (2201)
vagelis wrote:
how can i run in release mode??

http://msdn.microsoft.com/en-us/library/wx0123s5.aspx

vagelis wrote:
second question is how can i turn off checked iterators

By default, checked iterators are disabled in release mode.

vagelis wrote:
i run a c++ program with visual studio but it is slow
i use vector and i wonder if that is the problem

What do you mean when you say 'slow' ? Could we see some code?
vagelis (106)
when i say it is slow it is slower than matlab the same function.i expect c++ to be faster than matlab
i wonder if it is due to vectors or if i used arrays the speed would not be much better??
here is a part of the code
i run the code for many many times and one function calls others and again so if it is a little slow for one run for many many times all the programm will be slow
if you can help..



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
vector<vector<vector<int>>> maxweight(const vector<vector<int>> &CombNK,const vector<vector<int>> &Q,const vector<vector<double>> &P )
{

vector<vector<vector<int>>> return_value;
int N=Q[0].size();

int M=Q.size();

int n=CombNK[0].size();

int C=CombNK.size();

int comb1,i1,i2;
vector<int> comb2;
double weight1,weight2;
double maxweight1,maxweight2;
vector<vector<double>> G1;
vector<vector<int>> Qmax(M,vector<int>(N));
int Xmax;
double Ymax;
Ymax=-1;



for (int i=0;i<C;i++)
{
   
    vector<int> current_combination;
	current_combination=CombNK[i];
	
    switch(n)
	{
	case 1:
           
            maxweight1=-1;
            G1=connectivity( current_combination,M,i+1,P);
           
			for (int q1=0;q1<N;q1++)
			{
               G1(q1,N+1),'Q(i,q1)',Q(i,q1),'G1(q1,N+1)*Q(i,q1)',G1(q1,N+1)*Q(i,q1)
                weight1=0;
				for(int k=0;k<N;k++)  weight1=weight1+G1[q1][k]*(Q[i][q1]-Q[i][k]);
				weight1=weight1+G1[q1][N]*Q[i][q1];
				if (weight1<0) weight1=0;
				
                if(weight1>maxweight1)
				{
                    
                    maxweight1=weight1;
                    comb1=q1;
				}
			}
			
            if(maxweight1>Ymax)
			{
               
                 Xmax=i+1;
                 Ymax=maxweight1;
               				for(int i=0;i<M;i++)
				{
					for(int j=0;j<N;j++)
					{
						Qmax[i][j]=0;
					}
				}
				
                Qmax[i][comb1]=1;
        
			}
			break;
           
	case 2:
             maxweight2=-1;
            
            i1=CombNK[i][0];
            i2=CombNK[i][1];
			
            for (int q1=0;q1<N;q1++)
			{
                for (int q2=0;q2<N;q2++)
				{
                    
					vector<vector<double>> G1=connectivity( current_combination,M,q2+1,P );
					vector<vector<double>> G2=connectivity( circshift_1_dexia(current_combination),M,q1+1,P );
					
					double weight2_1=0;
					
					for(int k=0;k<N;k++)  weight2_1=weight2_1+G1[q1][k]*(Q[i1-1][q1]-Q[i1-1][k]);
					weight2_1=weight2_1+G1[q1][N]*Q[i1-1][q1];
					if(weight2_1<0) weight2_1=0;

					double weight2_2=0;
					for(int k=0;k<N;k++)  weight2_2=weight2_2+G1[q2][k]*(Q[i2-1][q2]-Q[i2-1][k]);
					weight2_2=weight2_2+G1[q2][N]*Q[i2-1][q2];
					if(weight2_2<0) weight2_2=0;

					weight2=weight2_1+weight2_2;

					
					if(weight2>maxweight2)
					{
                        
						comb2.clear();
                        maxweight2=weight2;
                        comb2.push_back(q1);
						comb2.push_back(q2);
            					}
				}
			}
			
            if(maxweight2>Ymax)
			{
                
                 Xmax=i+1;
                 Ymax=maxweight2;
				
				for(int i=0;i<M;i++)
				{
					for(int j=0;j<N;j++)
					{
						Qmax[i][j]=0;
					}
				}
				i1=CombNK[i][0];
                i2=CombNK[i][1];
				Qmax[i1-1][comb2[0]]=1;
                Qmax[i2-1][comb2[1]]=1;
							}
			break;

	default:
	cout<<"error:n is larger than 4!!!";
}
	
}
return_value.push_back(vector<vector<int>>());
return_value[0].push_back(vector<int>());
return_value[0][0].push_back(Xmax);
return_value.push_back(vector<vector<int>>());
return_value[1].push_back(vector<int>());
return_value[1][0].push_back(Ymax);
return_value.push_back(Qmax);

return return_value;
}
Last edited on
vagelis (106)
and another part to have a better view

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
vector<vector<double>> connectivity(const vector<int> &current_combination,int M,int queue2,const vector<vector<double>> &P )
{


int N=pow(3.0,(M-1));


vector<vector<double>> Gout;
vector<int>::iterator iter;
int state1;
vector<int> state2;
switch(current_combination.size())
{
case 0:
	{ //pathological case we use to output the probability matrix
		Gout=P;		
		break;
	}
case 1:
       {
		
		vector<vector<double>> zeros(N,vector<double>(N));
		Gout=zeros;
		for(int i=0;i<N;i++) Gout[i].push_back(1);	
		break;
	   }
case 2:
	{    
	
		vector<vector<double>> zeros(N,vector<double>(N+1));
		Gout=zeros;
        
       state2=dec2tri(queue2-1);
	         
        
		
		for(int i=0;i<M-state2.size();i++)
		{
			iter=state2.begin();
			state2.insert(iter,0);
		}
		
			// state2
       
		double p_good;
		double p_bad;
		int pos_good;
		int pos_bad;
		double p_fail;
		double p_transmit;
		switch(state1)
		{
		case 0:
			{    
			
				p_transmit=P[current_combination[1]-1][current_combination[0]-1];
              

		        for(int i=0;i<N;i++) Gout[i][N]=p_transmit;
				//Gout
              
                p_fail=1-p_transmit;
				for (int i=0;i<N;i++)
				{
                    
					for(int i=0;i<M-statei.size()-1;i++) 
					{
						iter=statei.begin();
						statei.insert(iter,0);
					}	
					
                    vector<int> index_vector;
					for(int i=0;i<M;i++) index_vector.push_back(i+1);
					
					iter=index_vector.begin();
                    index_vector.erase(iter+current_combination[0]-1);
					
					
                    int neigh_state_i;
					for(int i=0;i<index_vector.size();i++)
					{
						
						if(index_vector[i]==current_combination[1]) 
						{
							neigh_state_i=statei[i]; 
						}
					}
					
                   	switch(neigh_state_i)
					{
					case 0:
						{

							
                            p_good=P[current_combination[0]-1][current_combination[1]-1];
                           
                            p_bad=1-p_good;

                            
							for(int i=0;i<index_vector.size();i++)
							{
								if(index_vector[i]==current_combination[1]) 
								{
									statei[i]=1;
								}
							}

                         
                            pos_good=tri2dec(statei);
							
							for(int i=0;i<index_vector.size();i++)
							{
								if(index_vector[i]==current_combination[1]) 
								{
									statei[i]=2;
								}
							}
							
                           
                            pos_bad=tri2dec(statei);
							
                            Gout[i][pos_good]=p_good*p_fail;
                          
                            Gout[i][pos_bad]=p_bad*p_fail;
							break;
                            
						}
					case 1:
						{
							
						   Gout[i][i]=p_fail;
							break;
                          
						}
					case 2:
                           
						{
                            Gout[i][i]=p_fail;
							break;
                          
						}
					default:
                            cout<<"there must be an error in neigh_state_i";
					}
				}
				break;
				}
		case 1:
			{
				
              
				for(int i=0;i<N;i++) Gout[i][N]=1;
				break;
              
			}
		case 2:
			{    
			
                for (int i=0;i<N;i++)
				{
                    
                    vector<int> statei=dec2tri(i);
                   
					for(int i=0;i<M-statei.size()-1;i++) 
					{
						iter=statei.begin();
						statei.insert(iter,0);
						
                    
					}
					
					vector<int> index_vector;
					for(int i=0;i<M;i++) index_vector.push_back(i+1);
                    
					iter=index_vector.begin();
                    index_vector.erase(iter+current_combination[0]-1);
                   
                    int neigh_state_i;
					for(int i=0;i<index_vector.size();i++)
					{
						if(index_vector[i]==current_combination[1]) 
						{
							neigh_state_i=statei[i];
						}
					}
                    
                    if(neigh_state_i==0)
					{
						
                        p_good=P[current_combination[0]-1][current_combination[1]-1];
                        
                        p_bad=1-p_good;
                       
                        for(int i=0;i<index_vector.size();i++)
						{
							if(index_vector[i]==current_combination[1]) 
							{
								statei[i]=1;
							}
						}
                        
                        pos_good=tri2dec(statei);
                       
                        for(int i=0;i<index_vector.size();i++)
						{
							if(index_vector[i]==current_combination[1]) 
							{
								statei[i]=2;
							}
						}
                        
                        pos_bad=tri2dec(statei);
                        
                       
                        Gout[i][pos_good]=p_good;
                       
                        Gout[i][pos_bad]=p_bad;
					}
                       
                    else
					{                    
						
                        Gout[i][i]=1;
                        
					}
					
				}
				break;
			}
		default:
                cout<<"there must be an error with ternary state decoding";
}

break;
}
default:
	cout<<"we havent implemented higher combinations yet so we dont know how to build the connectivity graph";
}

return Gout;

}
m4ster r0shi (2201)
Hmmm...

I guess it would be slightly faster if you used plain pointers instead of nested vectors,
but I don't think this is the main problem here.

vagelis wrote:
...one function calls others and again...

Are there recursive calls too?
(a function that calls itself or a function that calls a second function that calls the first function again... etc...)

My guess is that the algorithm you use (or the way you implement the algorithm you use) could be better. Something else that could help is passing the return values of your functions as arguments by reference instead of returning them. What I mean is,

do something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
using namespace std;

void foo(int & n) {n=5;}

int main()
{
    int n;
    foo(n);

    cout << n << endl;

    cin.get();
    return 0;
}

instead of something like this:

1
2
3
4
5
6
7
8
9
10
11
12
 
#include <iostream>
using namespace std;

int foo() {return 5;}

int main()
{
    cout << foo() << endl;

    cin.get();
    return 0;
}

It could save you some time if there are many function calls.

Some other things I noticed in your code:

-> If you already know the size of a vector, prefer populating it using resize and operator[], instead of pushing back elements.

-> If while preparing a vector for use you need to insert or erase elements to/from the beginning of the vector and you need to do this several times, maybe using a list at first and then copying it to a vector could be faster. Remember, the fast things you can do with a vector are element access and inserting/removing elements to/from the end of the vector.

By the way, I'm curious... How did you implement your combinations finding function? Maybe that's what's slowing you down. In case you are too bored to google and copy-paste a couple of lines, I'll give you
something I found here -> http://www.codeproject.com/KB/recipes/CombC.aspx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
#include <iostream>
#include <vector>
using namespace std;

// Recursive template function
template <class RanIt, class Func>
void recursive_combination(RanIt nbegin, RanIt nend, int n_column,
    RanIt rbegin, RanIt rend, int r_column,int loop, Func func)
{
  int r_size=rend-rbegin;

  int localloop=loop;
  int local_n_column=n_column;

  //A different combination is out
  if(r_column>(r_size-1))
  {
    func(rbegin,rend);
    return;
  }
  //===========================

  for(int i=0;i<=loop;++i)
  {
    RanIt it1=rbegin;
    for(int cnt=0;cnt<r_column;++cnt)
    {
      ++it1;
    }
    RanIt it2=nbegin;
    for(int cnt2=0;cnt2<n_column+i;++cnt2)
    {
      ++it2;
    }

    *it1=*it2;

    ++local_n_column;

    recursive_combination(nbegin,nend,local_n_column,
      rbegin,rend,r_column+1,localloop,func);

    --localloop;
  }
}

typedef vector<int>::iterator vii;

void display(vii begin,vii end)
{
  for (vii it=begin;it!=end;++it)
      cout<<*it;
  cout<<endl;
}

int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  vector<int> cb;
  cb.push_back (1);
  cb.push_back (2);
  cb.push_back (3);
  cb.push_back (4);

  recursive_combination(ca.begin (),ca.end(),0,
                  cb.begin(),cb.end(),0,6-4,display);
  cout<<"Complete!"<<endl;
  return 0;
}

Last edited on
jimc (62)

You appear to be copying vectors around a lot. For example:
1
2
 
  vector<int> current_combination;
  current_combination=CombNK[i];


This code declares a new vector and then copies the CombNK[i] vector into it. If you just want a different name for the CombNK[i] vector, rather than using it directly everywhere, use a reference.
 
 
  const vector<int>& current_combination = CombNK[i];

This does not copy the contents of the vector.

This looks like unnecessary copying also: 
1
2
3
 
  vector<vector<double>> zeros(N,vector<double>(N));
  Gout=zeros;
  for(int i=0;i<N;i++) Gout[i].push_back(1);

To eliminate the possible copying (the compiler can sometimes optimize out temporaries) you would need to declare and return Gout locally (possibly complicated), or use vector::swap to move the contents of zeros to Gout without copying, or use resize. vector::swap just swaps the 3 pointers contained in the vector; it does not copy the elements. 

1
2
3
 
  vector<vector<double>> zeros(N,vector<double>(N));
  Gout.swap(zeros);  // side effect; zeros gets previous contents of Gout before going out of scope
  for(int i=0;i<N;i++) Gout[i].push_back(1);


Resize:
1
2
3
4
 
  Gout.clear(); // empty the vector; size = 0
  Gout.resize(N,vector<double>(N));  // reinitialize with what would have been in zeros;
                                                        // avoids copy of zeros into Gout.
  for(int i=0;i<N;i++) Gout[i].push_back(1);


Using clear and resize is probably the cleanest way to do it. It would also be more efficient to not use push_back in this case, as it it is likely to trigger a reallocation which will copy all elements. You just resized it; many implementations will make it exactly that size. So, just make each vector in Gout size N+1, and then assign. By default, a vector will start out at size 0. If you push_back an element, it will make space for it, but it grows by doubling. So if you just use push_back, its size will be 1, then 2, 4, 8, 16, 32, 64, etc. Each reallocation will copy all elements into a new vector of the larger size. So if you have some idea how big they are, just call reserve() to reserve some space from the start and prevent reallocations when using push_back. Push_back is close to assignment if it does not trigger a resize. Reserve() and resize() are not the same. Hopefully you know this.
1
2
3
 
  Gout.clear(); // empty the vector; size = 0
  Gout.resize(N,vector<double>(N+1));  // allocate one extra space in each vector
  for(int i=0;i<N;i++) Gout[i][N] = 1;  // assignment instead of push_back 


1
2
 
  vector<vector<double>> G1=connectivity( current_combination,M,q2+1,P );
  vector<vector<double>> G2=connectivity( circshift_1_dexia(current_combination),M,q1+1,P );

This could also be copying vectors since connectivity returns a vector by value. In some cases, the compiler will optimize this out. To avoid this for sure though, you can pass the vector as non-const reference to connectivity rather than returning them. Your code seems a bit over complicated also. The return value of maxweight is a 3-dimensional vector returned by value (which may make a copy of it). You might want to just pass them as non-const references instead of returning them. Also, if you push_back a vector onto another vector, it will generally copy it also, so Qmax may get copied unnecessarily when you push it onto the return vector in addition to when it is returned by value.

It looks like you may be using insert or erase in the middle of a vector. This is really inefficient. Vectors are only efficient for insert or erase at the end, and it is best to call reserve() if you are going to push_back a lot of values. You may be able to re-write it using list if you don't really need random access; with list you lose the subscript operator, but you can still make linear passes through, and save iterators to elements, rather than subscripts.

With some compilers, it can be faster to use pre-increment, rather than post-increment. Prefer ++i to i++ unless you actually need to use the post-increment. They are not the same.

Anyway, vector is going to be horribly slow if you are not compiling with optimization on. With optimization, it is close to built-in arrays. Built-in arrays can be quite slow without optimization on also, but not as bad as vector.

Hopefully, I got all of my code examples right and they are helpful, but I am only up at 7:00am because I am sick and can't sleep, so test carefully if you copy/paste.
jimc (62)
For arrays, you have to know some dimensions at compile time. I haven't looked too closely, but you seem to require resizable arrays. There is little reason to write your own vector implementation with pointers to implement your own version of resizable arrays. Vectors can be very efficient when used properly.

There is an optimization possibility if you have a small number of sizes you need to support. Basically, you write the function (or class) as a template using arrays with the array sizes as template parameters. Template parameters are resolved at compile time. This will cause massive code bloat if you instantiate to many sizes since it will generate a different copy of your code for each size you instantiate. This also may require more knowledge of C++ than you currently have.
Topic archived. No new replies allowed.