I only want to point out some things that are perhaps of minor relevance here, I think, since I am pushing the limits. But it might still be valuable to know.
Using the STL here, and in the way you did, it very wasteful, both in terms of memory consumption as well as time. Take for instance the repeated assignments to curr_row
. Those are all copy operations. That means there is a lot of heap operations (allocation/freeing) going on there. You can optimise that by making curr_row
a pointer and just switch what it points to.
But, in fact, you can avoid curr_row
entirely - and with it the if-else
construct - if you chose to use an array of vectors and an index crow
to alternate between them:
vector <int> row[2] = {{1}, {}};
int crow = 0;
// loop through all the rows
for (int i = 1; i < (n_num + 1); i++) {
SetRow(row[crow], row[(crow+1)&1], i);
crow ^= 1;
...
}
To give you an idea of the difference, here is a valgrind
output for 1000
rows
==690== HEAP SUMMARY:
==690== in use at exit: 0 bytes in 0 blocks
==690== total heap usage: 1,025 allocs, 1,025 frees, 2,097,128 bytes allocated
Compared to using array of vectors
==694== HEAP SUMMARY:
==694== in use at exit: 0 bytes in 0 blocks
==694== total heap usage: 25 allocs, 25 frees, 91,128 bytes allocated
In a next step, you might ask yourself: "Do I really need the assets that the vector
class provides?"
As you see, you can calculate the total need of space in advance. Using direct array access is a lot faster than clearing and pushing into vectors. Plus, using arrays opens up the opportunity to reduce calculations exploiting the symmetry of the triangle.
After taking user input (and issues about that have already been raised), you can set yourself up like this:
int *buffer = new int[2 * n_num];
buffer[0] = 1;
buffer[n_num] = 1;
int crow = 0;
cout << "1" << endl;
This is a contiguous memory block, twice the size of the maximum size of columns you will need. (Rooming two rows of the triangle as before)
Of course, SetRow
needs to look a little different now:
void SetRow(int* buf, int crow, int row, int ncol) {
int b0 = ncol * ((crow+1)&1);
int b1 = ncol * crow;
int i = 1, lim = row/2 + 1;
for (; i < lim; i++) {
buf[b0 + i] = buf[b1 + i - 1] + buf[b1 + i];
buf[b0 + row - i] = buf[b0 + i];
}
buf[b0 + row] = 1;
}
the values b0
and b1
are simply pre-calculated offsets into the buffer, and lim
only runs up to half the triangle because assignment to the new row is done symmetrically from the left and the right towards the middle.
The first entry is skipped (it is always 1
) and the last is manually inserted.
Printing now needs an ordinary for-loop.
// loop through all the rows
for (int i = 1; i < (n_num + 1); i++) {
SetRow(buffer, crow, i, n_num);
crow ^= 1;
int b0 = crow * n_num;
for(int j = 0; j <= i; j++) {
cout << buffer[b0 + j] << ' ';
}
cout << endl;
}
And don't forget to delete[]
the buffer once you're finished.
Primitive timing using OS time
functionality for 30000
rows:
- vector based:
./pascal 25.37s user 0.12s system 95% cpu 26.678 total
- array based:
./pascal4 1.88s user 0.00s system 61% cpu 3.073 total
Heap summary (1000 rows):
==771== HEAP SUMMARY:
==771== in use at exit: 0 bytes in 0 blocks
==771== total heap usage: 4 allocs, 4 frees, 82,752 bytes allocated
These are values for my computer, of course, but the difference should be obvious.
As I said, I have been pushing the limits. I hardly think anyone would want to print out 30000 rows of the Pascal Triangle, but I wanted to make aware of the differences