how to write this program

[jsmith]

@icerlion:

Huh? Show me a better way.

#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <sys/time.h>
#include <vector>

template< typename T, size_t N >
size_t asize( T (&)[ N ] )
{ return N; }

template< typename T, size_t N >
T* abegin( T (&a)[ N ] )
{ return a; }

template< typename T, size_t N >
T* aend( T (&a)[ N ] )
{ return a + N; }

void Output( const std::vector<int>& ans, int last, int sum )
{
    std::for_each( ans.begin(), ans.end(), std::cout << boost::lambda::_1 << " + " );
    std::cout << last << " = " << sum << std::endl;
}

void Run( int target, std::vector<int>& ans, int sum, const int* first, const int* last )
{
    for( const int* cur = first; cur != last; ++first )
        if( sum + *first == target )
        {
            Output( ans, *first, target );
            break;
        }
        else if( sum + *first < target )
        {
            ans.push_back( *first );
            Run( target, ans, sum + *first, first + 1, last );
            ans.pop_back();
        }
        else
            break;
}

int main() {
    int nums[] = { 
      103, 107, 109, 113, 127, 131, 137, 151, 157, 167,
        1,   2,   3,   5,   7,  11,  13,  17,  19,  23,  
       67,  71,  73,  79,  83,  89,  97, 101, 139, 149,
       29,  31,  37,  41,  43,  47,  53,  59,  61, 163
    };
    
    std::vector<int> ans;
    ans.reserve( asize( nums ) );

    struct timespec start, finish, diff;

    assert( clock_gettime( CLOCK_PROCESS_CPUTIME_ID, &start ) == 0 );
    std::sort( abegin( nums ), aend( nums ) );
    Run( 473, ans, 0, abegin( nums ), aend( nums ) );
    assert( clock_gettime( CLOCK_PROCESS_CPUTIME_ID, &finish ) == 0 );

    if( finish.tv_nsec < start.tv_nsec )
    {
        finish.tv_nsec += 1000000000UL;
        --finish.tv_sec;
    }

    diff.tv_sec = finish.tv_sec - start.tv_sec;
    diff.tv_nsec = finish.tv_nsec - start.tv_nsec;

    std::cerr 
        << "Execution time: " << diff.tv_sec << '.' << std::setw( 9 )
        << std::setfill( '0' ) << diff.tv_nsec << 's' << std::endl;
}

Over 11 runs of this code, the average execution time was 6.006109s with
a standard deviation of 0.000973s.

Code was compiled with

g++ -O3 -fomit-frame-pointer -lrt calc.cpp

Executable was run with:

a.out > /dev/null

(the program takes a _lot_ longer to run if output is not redirected because
there are over 2.2 million subsets that are matched)

EDIT: oops, of course there was bug in the output of the time measurement.
The actual average execution time was 6.6109s, not 6.006109s. The
std deviation was 0.0973s, not 0.000973s.

FWIW, if I comment out the lines of code in Output(), execution time goes
down to just under 1 second on my machine. (This is due to all the
function calls associated with the stream and with boost::lambda.)

[jsmith]

Also, FWIW,

I compared execution times of the program with four different versions of Output(). Those programmers
who complain that "I/O streams are slow, so I use printf instead" will not be interested in these results.

Version 1: (no-op)

void Output( const std::vector<int>& ans, int last, int sum )
{
}

Version 2: (printf)

void Output( const std::vector<int>& ans, int last, int sum )
{
    typedef std::vector<int>::const_iterator Iter;

    for( Iter i = ans.begin(); i != ans.end(); ++i )
        printf( "%d + ", *i );
    printf( "%d = %d\n", last, sum );
}

Version 3: (I/O streams without boost::lambda)

void Output( const std::vector<int>& ans, int last, int sum )
{
    typedef std::vector<int>::const_iterator Iter;

    for( Iter i = ans.begin(); i != ans.end(); ++i )
        std::cout << *i << " + ";
    std::cout << last << " = " << sum << std::endl;
}

Version 4: (I/O streams with boost::lambda)

void Output( const std::vector<int>& ans, int last, int sum )
{
    std::for_each( ans.begin(), ans.end(), std::cout << boost::lambda::_1 << " + " );
    std::cout << last << " = " << sum << std::endl;
}

Average runtimes, over 5 runs each:


Version 1: 0.97784s
Version 2: 5.04800s
Version 3: 6.42540s
Version 4: 6.62540s


The difference between 1 and 2 shows that the program spends over 80% of its time inside Output().

The difference between 2 and 3 (printf, I/O streams) is about 1.38s over 2,237,417 calls to the
function. This amounts to 0.000000615621s, or 0.615621 microseconds difference per call between
printf and I/O streams.

The difference between 3 and 4 is 0.2s which means that the "overhead" added by boost::lambda
is negligible.