how can i reserve space for a two dimensional vector??

[vagelis]

the question is how can i reserve space for a two dimensional vector
i am afraid that all the slowness is caused from the fact that the vector resizes its capacity

[taylorc8]

http://www.cplusplus.com/reference/stl/vector/reserve/

[vagelis]

i use this code with vectors

int main()
{

	

vector<vector<double>> P(2,vector<double>(2));
P[0][0]=1;
P[0][1]=0.5;
P[1][0]=0.5;
P[1][1]=1;


vector<int> A;
A.push_back(1);
A.push_back(4);


clock_t t1,t2;
t1=clock();
int Mem_in_size=0;
vector<vector<int>> Memory;
Memory.reserve(5000);
//for(int i=0;i<1000;i++) Memory.reserve(5);
for(int i=0;i<1000;i++)
{
	arrive(Memory,A,P,Mem_in_size );
	//print(Memory,Mem_in_size);
}
t2=clock();
double dif = (double)(t2-t1)/CLOCKS_PER_SEC ;
cout<<"dif "<<dif;

cout<<"epistrofi";
cin>>P[0][0];
}


ostream & print(const vector<vector<int> > & v,const int Mem_in_size)
{
    for (int i=0; i<Mem_in_size; i++)
    {
        for (int j=0; j<5; j++)
            cout << v[i][j] << ' ';

        cout << endl;
    }

    return cout;
}

void arrive(vector<vector<int>> &Mem_in,vector<int> A,vector<vector<double>> P,int &Mem_in_size )
{
		int M=2;
		for (int i=0;i<M;i++)
	{  
		for (int k=0;k<A[i];k++)
		{
							
Mem_in_size=Mem_in_size+1;
								
vector<int> voithima;
								voithima.push_back(find_Column_Max(Mem_in,0,Mem_in_size-1)+1);

								voithima.push_back(i+1);
								voithima.push_back(1);
								change_row_elements2(voithima,3,M+2,P[i]);
				
				
				Mem_in.push_back(voithima);
				
		}
		
	}
	int asxeto;
//cin>>asxeto;

}
int find_Column_Max(vector<vector<int>> diplospinakas,int column,const int Mem_in_size)
{
	
	if(Mem_in_size==0) return 0;
	int max=diplospinakas[0][column];
	for(int i=0;i<Mem_in_size;i++)
		{
			if(diplospinakas[i][column]>max) max=diplospinakas[i][column];
		}
	//cout<<max<<endl;
return max;
}

void change_row_elements2(vector<int> &diplospinakas,int first_column,int last_column,vector<double> P)
{
	int Pcolumn=0;
	for(int j=first_column;j<=last_column;j++)
	{
		diplospinakas.push_back(get_resultof_probability(P[Pcolumn]));
		Pcolumn++;
	}
}

void change_row_elements(vector<vector<int>> &diplospinakas,int row,int first_column,int last_column,vector<double> P)
{
	int Pcolumn=0;
	for(int j=first_column;j<=last_column;j++)
	{
		diplospinakas[row][j]=get_resultof_probability(P[Pcolumn]);
		Pcolumn++;
	}
}

int get_resultof_probability(double prob)
{
	double anumber_0_1=(rand()%1000)/1000.0;
	//cout<<"anumber_0_1"<<" "<<anumber_0_1<<" "<<prob<<endl;
	if(anumber_0_1<prob)
	{
		//cout<<1<<endl;
		return 1;
	}
	else
	{
		//cout<<0<<endl;		
		return 0;
	}
}

focus in arrive and main





which in comparison with simple arrays is very very slower
the comparison is 0.5 seconds and 30 minutes

int main()
{

	double P[2][2]={{1,0.5},
	{0.5,1}};


int A[2]={1,1};
int Mem_in[50000][5];

int sizeofA=2;
int sizeof_Mem_in=0;

clock_t t1,t2;
t1=clock();

for(int i=0;i<10000;i++) 
{
arrive(Mem_in,A,P,sizeofA,sizeof_Mem_in );
//print(Mem_in,sizeof_Mem_in,5);
}
t2=clock();
double dif = (double)(t2-t1)/CLOCKS_PER_SEC ;
cout<<"dif "<<dif;
cout<<"epistrofi";
//print(Mem_in,5,5);*/
int a;
cin>>a;
}
ostream & print(const int  v[10000][5],int rows,int columns)
{
    for (int i=0; i<rows; i++)
    {
        for (int j=0; j<columns; j++)
            cout << v[i][j] << ' ';

        cout << endl;
    }

    return cout;
}
void arrive(int Mem_in[10000][5],const int *A,const double P[2][2],int sizeofA,int &sizeof_Mem_in )
{
	
	int M=sizeofA;
	
	for (int i=0;i<M;i++)
	{  
		for (int k=0;k<A[i];k++)
		{
				sizeof_Mem_in+=1;
				Mem_in[sizeof_Mem_in-1][0]=find_Column_Max(Mem_in,0,sizeof_Mem_in-1)+1;
				Mem_in[sizeof_Mem_in-1][1]=i+1;
				Mem_in[sizeof_Mem_in-1][2]=1;
				change_row_elements(Mem_in,sizeof_Mem_in-1,3,M+2,P[i]);
				//cout<<"ektiposi"<<Mem_in[i+k][0]<<Mem_in[i+k][1]<<Mem_in[i+k][2]<<Mem_in[i+k][3]<<Mem_in[i+k][4]<<endl;
				
		}
		
	}
	int asxeto;
}

int find_Column_Max(const int diplospinakas[10000][5],int column,const int sizeof_diplospinakas)
{
	if(sizeof_diplospinakas==0) return 0;
	int max=diplospinakas[0][column];
	for(int i=0;i<sizeof_diplospinakas;i++)
		{
			if(diplospinakas[i][column]>max) max=diplospinakas[i][column];
		}
	return max;
}


void change_row_elements(int diplospinakas[10000][5],int row,int first_column,int last_column,const double *P)
{
	int Pcolumn=0;
	for(int j=first_column;j<=last_column;j++)
	{
		diplospinakas[row][j]=get_resultof_probability(P[Pcolumn]);
		Pcolumn++;
	}
}

int get_resultof_probability(double prob)
{
	double anumber_0_1=(rand()%1000)/1000.0;
	if(anumber_0_1<prob)
	{
		//cout<<1<<endl;
		return 1;
	}
	else
	{
		//cout<<0<<endl;		
		return 0;
	}
}
}

focus in arrive and main

what am i doing wrong with vectors??

[ne555]

Too much magic numbers.

//int find_Column_Max(vector<vector<int>> diplospinakas,int column,const int Mem_in_size);
int find_Column_Max(const vector<vector<int> > &diplospinakas,int column,const int Mem_in_size);

You call that function a lot. And you copy a vector with 5000 elements in every call.
Because you don't change the vector inside the function, change the parameter to constant reference instead of copy

[taylorc8]

http://www.cplusplus.com/reference/algorithm/

Perhaps pass by reference whenever possible. 30 Minutes?? Are you sure it didn't just infinite loop?

which in comparison with simple arrays is very very slower
the comparison is 0.5 seconds and 30 minutes

What are you even trying to do? I don't want to decode your code, add some comments or at least tell us what you're trying to do so that we can help you.

[vagelis]

no it is not an infinite loop because i check the results with print in the console

the vector changes inside the function
in every loop it changes
all this is part of a bigger programm and i test it alone to see the difference in performance between simple arrays and vectors
and the difference is chaotic

i dont know why
i dont think you must understand whati it does
only if you see a wrong code style with vectors perhaps..

[vagelis]

and the question is how can i reserve capacity for a two dimenisonal vector??

vector<vector<int>> Memory;
Memory.reserve(5000);
for(int i=0;i<1000;i++) Memory.reserve(5);

is that correct??

[ne555]

Yes, but reserve doesn't change the size of the vector
Also: vector<vector<int> > Memory; Note the space.

find_Column_Max doesn't change the vector, pass it by reference

[vagelis]

thank you very much
the fact that i didnt passed by reference in find_Column_Max made all the slowness

i didnt understand why the space is needed???

[m4ster r0shi]

vagelis wrote:

i didnt understand why the space is needed???

If you use Visual C++ you don't need it.

[vagelis]

ok thanks!!
a difference between speed of the vector and array sill exist but it is much lower now

before it was 30 minutes the vectors and 1.5 seconds the array
and now it is 21 seconds and 1.5 seconds

[ne555]

./vector.bin
dif 0.46
./array.bin
dif 2.52

Edit: The test was biased, invalid results

[joeneldeasis]

USE THE FUNCTION auto_res_vect2d();

[Seraphimsan]

that function doesn't exist in the standard.

[jimc]

This probably doesn't do what you intended.

vector<vector<int>> Memory;                     // new empty vector size = 0; capacity = 0;
Memory.reserve(5000);                           // Memory.size() still equals 0; capacity >=5000
for(int i=0;i<1000;i++) Memory.reserve(5);      //  Call reserve 1000 times on the same vector
                                                // probably doesn't do anything; capacity already >5 

If you know how big the vectors need to be, then give them a size when you create them as you did for "P" or just use arrays; the ability to resize is the main reason to use vectors.
vector<vector<double>> P(2,vector<double>(2));

To resize/reserve space after creation:

vector<vector<int>> Memory;                     // new empty vector size = 0; capacity = 0;
Memory.resize(1000);                            // This must be resize, not reserve.  size = 1000,
                                                //  capacity >= 1000
for(int i=0;i<1000;i++)  Memory[i].reserve(5);  // Reserve enough memory for at least 5 elements
                                                // in each sub-vector.  elements must still be added
                                                // before use: Memory[i].push_back(element); 

You can not reserve space for vectors in the second dimension without actually creating those vectors first. Reserve just allocates uninitialized memory, so if you just call Memory.reserve(), you have not created any elements, therefore, you can not call any member functions of these elements, or access them in any way. You have to add them by push_back, insert, or resize first.

void arrive(vector<vector<int>> &Mem_in,vector<int> A,vector<vector<double>> P,int &Mem_in_size )

In the above code, you are still passing the smaller vectors "A" and "P" by value rather than reference. Do you need a local copy of them?


I would not expect as big of a performance difference between vector and array. If you are not compiling with optimization (release mode, or whatever it is on your compiler), then this will slow vector down significantly. This is because each access with subscripting will be a function call for vector when in-lining is not enabled.

For portability, you should still have the extra space for nested template parameters: vector<vector<int> >. It may not be required for all current compilers, but it was for some due to the possibility of it being ambiguous.

[vagelis]

i dont know in the real problem how big the vectors will be
i only do a test here to compare the speed of array and vector in a part of the programm with an input that i choose

you are correct about the reserve..
but when i do this

vector<vector<int>> Memory;
Memory.resize(5050);
for(int i=0;i<5050;i++) Memory[i].reserve(6);

or this

vector<vector<int>> Memory;
Memory.reserve(5050);
for(int i=0;i<5050;i++) Memory[i].reserve(6);

it throws me here..

int _debugger_hook_dummy;

#ifdef _M_IA64
#undef _CRT_DEBUGGER_HOOK
#define _CRT_DEBUGGER_HOOK __crt_debugger_hook
#endif  /* _M_IA64 */

__declspec(noinline)
void __cdecl _CRT_DEBUGGER_HOOK(int _Reserved)
{
    /* assign 0 to _debugger_hook_dummy so that the function is not folded in retail */
    (_Reserved);
    _debugger_hook_dummy = 0;
}

any idea??

[jimc]

int main () {

  vector<vector<int> > Memory; // g++ will not compile without the extra space
  Memory.resize(5050);
  for(int i=0;i<5050;i++) Memory[i].reserve(6);

  cout << "Memory size    : " <<  Memory.size() << "\tCapacity: " <<  Memory.capacity() << endl;
  cout << "Memory[10] size: " <<  Memory[10].size() <<  "\tCapacity: "<< Memory[10].capacity() << endl;

}

The above code works fine on my mac using g++ without any options, and produces the following output:

Memory size    : 5050	Capacity: 5050
Memory[10] size: 0	Capacity: 6

Although, it actually worked using reserve instead of resize also. That probably isn't guaranteed to work though, since you would be calling a function on an object that has not been constructed. May fail due to the object not being constructed, or may fail with out of range exception.

I have little experience working on windows, but doing a quick google search for the function _CRT_DEBUGGER_HOOK reports some forum results. It looks like this may have to do with linking with some sources compiled in release (optimized) mode and some compiled in debug mode. If you have changed any of those settings recently, then that may be the issue.

http://stackoverflow.com/questions/280477/crt-debugger-hook-throws-exception

If you know how big your vectors need to be at run time, then you should prefer to use resize over reserve for both dimensions. Reserve is mostly useful for when you are adding to a vector with push_back, or other such functions to avoid reallocations. Although, you may have to track the sizes independently in some cases.

[vagelis]

ok i had the problem in my code about that..

but still vectors seem to be much slower..
i have to live live with that..
thank you a lot about the answers..