Memoization-based puzzle solution - sums in a triangle

I am trying to solve a problem at Codechef. As I am new to programming, I am not familiar with dynamic programming. However, I do know the basics of recursion and memoization. Hence I implemented a solution to the above mentioned problem. The problem with my solution is that it exceeds the time limit given. As far as I can guess, the problem seems to be with my memoization logic. Please help me optimize the code.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

typedef vector<int> vector1D ;
typedef vector<vector1D > vector2D ; // Two Dimensional vector

int rownum;
int noOfCalls = 0;
vector2D a;
vector2D cache; // The cache to implement memoization

int solve (int i, int j)
{

int t1,t2,total;
if( i > rownum-1 ) {
return 0;
}
else {
if (cache[i][j] != 0 && ( i < 50) && ( j < 50)) { //for small values use memoization
return cache[i][j];
}
t1 = solve(i+1,j);
t2 = solve(i+1,j+1);
total = max(t1,t2) + a[i][j];
cache[i][j] = total;//store in cache
}
}
int main(int argc, char *argv[])
{
int tries;
cin>>tries;
while(tries--) {
cin>>rownum;
int temp = rownum;
for ( int i = 0 ; i < rownum ; i++) {
a.push_back(vector1D(rownum,0));//initialize memory
}
for ( int j = 0; j < 10; j++) {
cache.push_back(vector1D(10,0));//initialize cache
}
for ( int i = 0; i < rownum; i++) {
for ( int j = 0 ; j <= i; j++) {
cin>>a[i][j];
}
}
cout<<solve(0,0)<<endl;//call the solving function
cache.clear();
}
return 0;
}
• your solution overall looks Ok. You should extend the memoization for all values. Max no of lines is <=100 and 100X100 vector is Ok to have.
– Rajendran T
Jan 25 '12 at 19:38

I hate your use of global variables.

int rownum;
int noOfCalls = 0;
vector2D a;
vector2D cache; // The cache to implement memoization

I suppose it is an attempt at better performance.

The test for j here is redundant:

if (cache[i][j] != 0 && ( i < 50) && ( j < 50))

If i is smaller than 50 then j can not be greater than 50. If i is greater than 50 then the test will fail and there is no need to test what the value of j is.

Bugs

for ( int i = 0 ; i < rownum ; i++) {
a.push_back(vector1D(rownum,0));//initialize memory
}

As you never clear a the size increases for every puzzle.
This can become quite expensive as a will continuously keep breaking its buffer and have to be re-allocated (copying all those internal arrays).

Speed

If you are solely going for speed then operator>> is about half the speed of scanf as it (operator>>) takes into account a lot of local stuff that is not done with scanf.

Your recursive algorithm is computing some spots multiple times.

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

// Number of times each spot is hit with recursion
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

As you can see some of the spots in the center bottom of the triangle are being hit many many times by recursion when you only want to hit each location once. Thus an iterative solution is probably better.

You are using a 2D array to represent the triangle which requires two de-references (which can be inefficient (but without measuring I am not convinced this is a major issue)). Rather than do that use a 1-D array given the number of rows n you can quickly compute the number of elements in the triangle as n*(n+1)/2 and thus re-size the array in one statement. Element access for a child of m is m+row(m)+0 and m+row(m)+1 (note the calculation of row(m) does not need to be done each time you can keep track of this as you increment m).

If your priority is performance with this, in addition to having a memoizing cache for up to the size of about the L1 cache - maybe 4K or so, I'd also get rid of the use of the vector of vector.

You're spending a disproportionate amount of time in your vectors' [] operator() functions which will cause an over-abundance of stack pushes and context switches - you're using that operator in at least four places in each pass through solve() - six when not cached already. You can see this if you profile your code. I'd keep it to a vector with dynamically allocated columns and use only pointer arithmetic so that all accesses are happening from the same stack frame in solve(). I'd pre-calculate base pointers in advance and use those as much as possible in the pointer calculations using the bitwise << sizeof(int) to traverse.

I would also stay local and convert your max(t1,t2) call to use a bit-twiddle trick so that total is now:

total = t1 ^ ((t1 ^ t2) & -(t1 < t2)) + *paij;

where *paij is the dereferenced arithmetically calc'ed pointer instead of a[i][j]. That should keep the pipeline full more often.

To get to the next level from there, I would probably move from recursion to an iterative approach if you're not married to recursion.

That should buy you some performance gain, although more could be done depending on your machine configuration.

Edit: Test for speed.

#include <iostream>
#include <algorithm>
#include <sys/time.h>

using namespace std;

inline int getmax( int a, int b ) { if ( a < b ) return b; else return a; }
int main()
{
time_t timev;
timeval t1, t2;
double elapsed_time;
const unsigned int RUNL = 1000000000;

int i = 0;
int j = 1;
int k = 1;
int total;

gettimeofday( &t1, NULL );
while ( i++ < RUNL )
{
total = j ^ ( ( j ^ k ) & -( j < k ) );
k ^= 1;
}
gettimeofday( &t2, NULL );
elapsed_time = ( t2.tv_sec - t1.tv_sec ) * 1000.0;
elapsed_time += ( t2.tv_usec - t1.tv_usec ) / 1000.0;
cout << "Elapsed time for the bitop was: " << elapsed_time << " ms\n" << endl;
i = 0;
k = 1;
gettimeofday( &t1, NULL );
while ( i++ < RUNL )
{
total = max( j, k ); k ^= 1;
}
gettimeofday( &t2, NULL );
elapsed_time = ( t2.tv_sec - t1.tv_sec ) * 1000.0;
elapsed_time += ( t2.tv_usec - t1.tv_usec ) / 1000.0;
cout << "Elapsed time for the stl call was: " << elapsed_time << " ms\n" << endl;
i = 0;
k = 1;
gettimeofday( &t1, NULL );
while ( i++ < RUNL )
{
total = getmax( j, k ); k ^= 1;
}
gettimeofday( &t2, NULL );
elapsed_time = ( t2.tv_sec - t1.tv_sec ) * 1000.0;
elapsed_time += ( t2.tv_usec - t1.tv_usec ) / 1000.0;
cout << "Elapsed time for the getmax call was: " << elapsed_time << " ms\n" << endl;

}

Edit (Edit) Fixed Speed Test:

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

using namespace std;
void printTime(int total, std::string const& name, timeval& t1, timeval& t2)
{
double elapsed_time;

elapsed_time = ( t2.tv_sec - t1.tv_sec ) * 1000.0;
elapsed_time += ( t2.tv_usec - t1.tv_usec ) / 1000.0;

std::cout << "Result(" << total << ") Elapsed time for the " << name << " call was: " << elapsed_time << " ms\n" << std::endl;
}

inline int getmax( int a, int b ) { if ( a < b ) return b; else return a; }

int main()
{
timeval t1, t2;
const unsigned int RUNL = 1000000000;

std::vector<int> data(RUNL);
for(int loop=0;loop < RUNL;++loop)
{
data[loop]  = rand();
}
std::cout << "LoadData DONE" << std::endl;

int j = data;
int k;
gettimeofday( &t1, NULL );
for(int loop = 1;loop < RUNL;++loop)
{
k = data[loop];
j = j ^ ( ( j ^ k ) & -( j < k ) );
}
gettimeofday( &t2, NULL );
printTime(j, "BIT TWIDDLE", t1, t2);

j = data;
gettimeofday( &t1, NULL );
for(int loop = 1;loop < RUNL;++loop)
{
k = data[loop];
j = max( j, k );
}
gettimeofday( &t2, NULL );
printTime(j, "std::max", t1, t2);

j = data;
gettimeofday( &t1, NULL );
for(int loop = 1;loop < RUNL;++loop)
{
k = data[loop];
j = getmax( j, k );
}
gettimeofday( &t2, NULL );
printTime(j, "inline max", t1, t2);
}

Results:

> g++ -O3 x.cpp
> ./a.out
Result: total( 2147483645) Elapsed time for the BIT TWIDDLE call was: 1968.2 ms

Result: total( 2147483645) Elapsed time for the std::max call was: 1170.83 ms

Result: total( 2147483645) Elapsed time for the inline max call was: 1178.05 ms

It's easy to see why the optimizer runs so much faster than the bit hack from this code from between the gettimeofday calls):

STLMAX
movl    28(%esp), %ecx
movl    $1, %edx movl$1, %eax
.p2align 4,,7
L34:
movl    (%ecx,%edx,4), %edx
cmpl    %edx, %ebx
cmovl   %edx, %ebx
addl    $1, %eax cmpl$1000000000, %eax
movl    %eax, %edx
jne L34
leal    40(%esp), %eax
movl    $0, 4(%esp) movl %eax, (%esp) BIT HACK movl 28(%esp), %edi movl$1, %eax
movl    1, %edx .p2align 4,,7 L25: movl (%edi,%eax,4), %ecx xorl %eax, %eax cmpl %ebx, %ecx setg %al xorl %ebx, %ecx negl %eax addl1, %edx
andl    %ecx, %eax
xorl    %eax, %ebx
cmpl    $1000000000, %edx movl %edx, %eax jne L25 leal 40(%esp), %eax movl$0, 4(%esp)
movl    %eax, (%esp)

Basically two effective instructions in the loop doing the actual max in optimized STL compiler compared with seven for the bit hack. Lesson learned.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Code for hasZeroByte which gave about 2.5x improvement for the bit hack over the other two under -O3 optimization conditions:

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

using namespace std;
void printTime(int total, std::string const& name, timeval& t1, timeval& t2)
{
double elapsed_time;

elapsed_time = ( t2.tv_sec - t1.tv_sec ) * 1000.0;
elapsed_time += ( t2.tv_usec - t1.tv_usec ) / 1000.0;

std::cout << "Result(" << total << ") Elapsed time for the " << name << " call was: " << elapsed_time << " ms\n" << std::endl;
}

inline bool checkZbyte1( int a )
{
for ( int i = 0; i < sizeof( int ); i++ )
{
if ( !( 0xff & a ) )
return true;
else
a >>= 8;
}
return false;
}

inline bool checkZbyte2( int a )
{
if ( !( 0xff & a ) || !( 0xff00 & a )  || !( 0xff0000 & a )  || !( 0xff000000 & a ) )
return true;
return false;
}

int main()
{
timeval t1, t2;
const unsigned int RUNL = 100000000;

std::vector<int> data(RUNL);
for(int loop=0; loop < RUNL; ++loop)
data[loop]  = rand();
std::cout << "LoadData DONE" << std::endl;

int j;
int count = 0;

gettimeofday( &t1, NULL );
for(int loop = 0; loop < RUNL ;++loop)
{
if ( checkZbyte1( data[loop] ) )
count++;
}
gettimeofday( &t2, NULL );
printTime( count, "inline version #1", t1, t2 );

count = 0;
gettimeofday( &t1, NULL );
for( int loop = 0; loop < RUNL; ++loop )
{
if ( checkZbyte2( data[loop] ) )
count++;
}
gettimeofday( &t2, NULL );
printTime( count, "inline version #2", t1, t2 );

count = 0;
gettimeofday( &t1, NULL );
for( int loop = 0; loop < RUNL; ++loop )
{
j = data[loop];
if ( ~( ( ( (j & 0x7F7F7F7F ) + 0x7F7F7F7F ) | j ) | 0x7F7F7F7F ) )
count++;
}
gettimeofday( &t2, NULL );
printTime( count, "BIT HACK", t1, t2 );

}
• Unless your compiler is extremely ancient/stupid, it will generate better code for max than any bit-twidding hack you come up with. Otherwise these are good ideas :-)
– Nemo
Jan 26 '12 at 2:22
• I think bit twiddling is silly. Also I am not sure I agree that operator[] is a problem. This is simply returns base[index] and as such is probably inlined and is no more expensive than a normal array access. If you are saying that the 2D array is the problem then maybe. Jan 26 '12 at 13:50
• hmm.. Why are bit hacks silly? I just ran 3 different cases of max using 1Billion of each all in identical loops. The results: Jan 27 '12 at 0:58
• Thing cut me off for taking to long... ironic... the results: bit hack max as above: 3.052s stl max() call: 4.238s my own getmax() call: 4.470s the results were consistent. I'm using cygwin with gcc 4.5 on a quad 2.5GHz Dell M6400. Try it yourself... I don't think we could disregard an improvement of 29%. Jan 27 '12 at 1:09
• They are silly because the compiler will always do as well and usually better. If you have found a new optimization to max (unlikely) then it will be introduced into the compiler and the next evolution of the compiler will be just as quick as your code. Post your code. :-) we will see how well it really does. Jan 27 '12 at 3:10

Why only use memoization for "small" values of i and j?

Without memoization, your program runs in exponential time. The problem, which memoization intends to solve, is that you tend to compute the same value many times along the way.

So you memoize some of the values, to save time. On those areas of the table you aren't memoizing, you still suffer the exponential slowdown. And you're only memoizing 1/4 of your domain.