[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

[Salem_c]

http://www.sgi.com/t...stl/Vector.html
Use the reserve() method.

[vagelis]

i want for two dimensional vector the reserve..

i use this code with vectors
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()
{

	

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;
	}
}

and this code with arrays

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;
	}
}
}

[Salem_c]

> void arrive(vector<vector<int>> &Mem_in,vector<int> A,vector<vector<double>> P,int &Mem_in_size )
Perhaps you should pass ALL your vectors (in every function) by reference instead.

Pass by value is going to entail making a hell of a lot of short-term copies.

If you've no intention to modify the input vector, then make it a const reference instead.

[vagelis]

yes i did that and i have a lo of improvement
thank you my friend
now the time that the vector do is 21 seconds
before it was 30 minutes..

but still arrays are much faster
with 1 second approximately

[Salem_c]

> ...
> Mem_in.push_back(voithima);
But you're still using push_back() and making copies of vectors in your arrive function.

If you know how many elements you're going to push, then resize() the vector accordingly, and use the [] method to access it (like the array code).

push_back is SAFER, but it is also SLOWER.

Most of the time, this isn't a problem. The safer code is worth the trade-off.
But in extreme cases, you can consider alternative approaches.

[janotte]

vagelis, on 27 December 2010 - 06:03 PM, said:

but still arrays are much faster

If used correctly that should not be the case
Vectors are good at:
- Accessing individual elements by their position index (constant time).
- Iterating over the elements in any order (linear time).
- Add and remove elements from its end (constant amortized time).

Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accomodate for extra storage space for future growth).
http://www.cplusplus...nce/stl/vector/

Perhaps you should be considering one of the other STL containers?
http://www.cplusplus.../reference/stl/

[baavgai]

I looked at this for probably a little too long. It's clear you really need the concept of a row of data, rather than a 2D array. This is usually the case. Also, your test seems stacked, with different sizes in the cases.

First thing we need is a base line to start from. I took you code an squished it into a single method with hard coded parameters.

const int sizeOfA = 2;
const int sizeOfRow = 5;
const int a[sizeOfA]={1,1};
const double p[2][2]={{1,0.5},{0.5,1}};
const int sizeof_Mem_in_max = 20000;
int Mem_in[sizeof_Mem_in_max][sizeOfRow], sizeof_Mem_in=0;
for (int loop=0; loop<testSize; loop++) {
	for (int i=0; i<sizeOfA; i++) {
		for (int k=0; k<a[i]; k++) {
			Mem_in[sizeof_Mem_in][0]=sizeof_Mem_in+1;
			Mem_in[sizeof_Mem_in][1]=i+1;
			Mem_in[sizeof_Mem_in][2]=1;
			for (int Pcolumn=0, j=3; j<=sizeOfA+2; j++, Pcolumn++) {
				double prob = p[i][Pcolumn];
				Mem_in[sizeof_Mem_in][j] = ((rand()%1000)/1000.0)<prob?1:0;
			}
			sizeof_Mem_in++;
		}
	}
}

Now, I want to figure out what a row is. Nearest I can come up with is:

const int ProbSize = 2;
struct Row {
	int index, aIndex, n;
	int probs[ProbSize];
};

We have the A and P mess. Really, they should be together, something like:

struct APItem {
	int a;
	double ps[ProbSize];
};
APItem items[] = { {1,{1,0.5}}, {1,{0.5,1} } };

Then, perhaps, a rows collection:

struct Rows {
	virtual int getSize() const = 0;
	virtual Row getRow(int) const = 0;
	virtual void addRow(int apIndex) = 0;
	
	APItem *apItems;
	const int apItemsSize;
	
	Rows(APItem *items, int size);
	~Rows();
	virtual void addRows();
	virtual void addRows(const int testSize);
};

Now we're cooking. You may implement rows as an array or a vector vector, or whatever. If you really wanted to be pedantic about it, you could also have a collection of APItem, but it didn't seem required.

Of course, we've isolated out row as it's own structure, so now we're dealing with standard list of objects, which makes things much easier.

So, here's some test code:

#include <iostream>
#include <cstdlib>
#include <vector>
#include <sys/time.h>

using namespace std;

struct StopWatch {
	struct timeval startTime;
	
	StopWatch() { reset(); }
	void reset() { gettimeofday(&startTime, NULL); }
	double elapsed() const {
		struct timeval endTime, elapsedTime;
		gettimeofday(&endTime, NULL);
		elapsedTime.tv_sec = endTime.tv_sec - startTime.tv_sec;
		elapsedTime.tv_usec = endTime.tv_usec - startTime.tv_usec;
		double real_time = elapsedTime.tv_sec;
		real_time += (elapsedTime.tv_usec / 1000000.0);
		return real_time;
	}
	void print(ostream &out) const { out << "Elapsed time: " << elapsed() << " seconds" << endl; }
};
ostream &operator<<(ostream &out, const StopWatch &sw) { sw.print(out); return out; }


const int ProbSize = 2;

struct Row {
	int index, aIndex, n;
	int probs[ProbSize];
	Row(int idx, int a, double *ps);
	Row() {}
};
ostream &operator<<(ostream &out, const Row &row);

struct APItem {
	int a;
	double ps[ProbSize];
};

struct Rows {
	virtual int getSize() const = 0;
	virtual Row getRow(int) const = 0;
	virtual void addRow(int apIndex) = 0;
	
	APItem *apItems;
	const int apItemsSize;
	
	Rows(APItem *items, int size);
	~Rows();
	virtual void addRows();
	virtual void addRows(const int testSize);
};

ostream &operator<<(ostream &out, const Rows &rows);


struct RowsArray : public Rows {
	Row *data;
	int size, maxSize;
	
	RowsArray(APItem *items, int asize, int capacity=30000) : Rows(items, asize), size(0), maxSize(capacity) {
		data = new Row[maxSize];
	}
	~RowsArray() { delete [] data; }
	int getSize() const { return size; }
	Row getRow(int i) const { return data[i]; }
	void addRow(int apIndex) {
		int index = size+1;
		data[size++] = Row(index, apIndex+1, apItems[apIndex].ps);
	}
};

struct RowsVec : public Rows {
	vector<Row> data;
	
	RowsVec(APItem *items, int asize, int capacity=30000) : Rows(items, asize) {
		data = vector<Row>(capacity);
	}
	int getSize() const { return data.size(); }
	Row getRow(int i) const { return data[i]; }
	void addRow(int apIndex) { data.push_back(Row(getSize()+1, apIndex+1, apItems[apIndex].ps)); }
};




void testFlat(const int testSize, bool showContents);

void testArray(const int testSize, bool showContents) {
	const int size = 2;
	APItem items[size] = { {1,{1,0.5}}, {1,{0.5,1} } };
	RowsArray rows(items, size);
	rows.addRows(testSize);
	if (showContents) { cout << rows << endl; }
}

void testVec(const int testSize, bool showContents) {
	const int size = 2;
	APItem items[size] = { {1,{1,0.5}}, {1,{0.5,1} } };
	RowsVec rows(items, size);
	rows.addRows(testSize);
	if (showContents) { cout << rows << endl; }
}

void testFunc(const int testSize, const char *name, void (*func)(const int, bool)) {
	cout << name << endl;
	StopWatch sw;
	func(testSize, false);
	cout << sw << endl;
}

void testAll(const int testSize) {
	cout << "test size: " << testSize << endl;
	testFunc(testSize, "testFlat", testFlat);
	testFunc(testSize, "testArray", testArray);
	testFunc(testSize, "testVec", testVec);
}

int main() {
	testAll(10000);
	return 0;
}

// base implementation


Row::Row(int idx, int a, double *ps) : index(idx), aIndex(a), n(1) {
	for (int i=0; i<ProbSize; i++) {
		double prob = ps[i];
		probs[i] = ((rand()%1000)/1000.0)<ps[i]?1:0;
	}
}


Rows::Rows(APItem *items, int size) : apItemsSize(size) {
	apItems = new APItem[apItemsSize];
	for(int i=0; i<apItemsSize; i++) {
		apItems[i] = items[i];
	}
}

Rows::~Rows() { delete [] apItems; }
	
void Rows::addRows() {
	for (int i=0; i<apItemsSize; i++) {
		for (int j=0; j<apItems[i].a; j++) {
			addRow(i);
		}
	}
}

void Rows::addRows(const int testSize) {
	for (int i=0; i<testSize; i++) {
		addRows();
	}
}

ostream &operator<<(ostream &out, const Row &row) { 
	out << "row(" << row.index << ' ' << row.aIndex << ' ' << row.n << " : ";
	for (int i=0; i<ProbSize; i++) { out << row.probs[i] << ' '; }
	out << ')';
	return out;
}

ostream &operator<<(ostream &out, const Rows &rows) { 
	int size = rows.getSize();
	for(int i=0; i<size; i++) {
		out << rows.getRow(i) << endl;
	}
	return out;
}


void testFlat(const int testSize, bool showContents) {
	const int sizeOfA = 2;
	const int sizeOfRow = 5;
	const int a[sizeOfA]={1,1};
	const double p[2][2]={{1,0.5},{0.5,1}};
	const int sizeof_Mem_in_max = 30000;
	int Mem_in[sizeof_Mem_in_max][sizeOfRow], sizeof_Mem_in=0;
	for (int loop=0; loop<testSize; loop++) {
		for (int i=0; i<sizeOfA; i++) {
			for (int k=0; k<a[i]; k++) {
				Mem_in[sizeof_Mem_in][0]=sizeof_Mem_in+1;
				Mem_in[sizeof_Mem_in][1]=i+1;
				Mem_in[sizeof_Mem_in][2]=1;
				for (int Pcolumn=0, j=3; j<=sizeOfA+2; j++, Pcolumn++) {
					double prob = p[i][Pcolumn];
					Mem_in[sizeof_Mem_in][j] = ((rand()%1000)/1000.0)<prob?1:0;
				}
				sizeof_Mem_in++;
			}
		}
	}
	if (showContents) {
		for (int i=0; i<sizeof_Mem_in; i++) {
			for (int j=0; j<sizeOfRow; j++) {
				cout << Mem_in[i][j] << ' ';
			}
			cout << endl;
		}
	}
}

Results:

test size: 10000
testFlat
Elapsed time: 0.008104 seconds

testArray
Elapsed time: 0.010638 seconds

testVec
Elapsed time: 0.021619 seconds

So, my vector is a wee bit slower. However, this is all allocation. There's something the vector can easily do that the current array implementations cannot: grow.

If I ask for 20000 on the code above, I'm seg faulting on testFlat and testArray. The testVec doesn't mind at all. Indeed, it will happily give me this:

test size: 1000000
testVec
Elapsed time: 0.545437 seconds

As the numbers get bigger, the vector proves itself. You'll have to do some allocation tricks for really big arrays and vector does those all already.

In any case, if you actually use OOP, you can isolate the storage mechanism behind a class. You can then change how that class implements storage and get a true picture of the impact of your design choices.