Jump to content
  • Advertisement
Sign in to follow this  
kRogue

C++ template challenge.

This topic is 3833 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Template meta-programming challenge: Create a template statically sized array class so that the number of elements in the staticly sized array is n choose k, where n and k are non-negative integers, i.e. if one has a staticly sized array class array<T,N>, create a declaration for a class combontoric_array<T,N,K> that is basically array<T, N choose K>. where N choose K is the binomial coeffiecient. What I do not accept is:

template<typename T, unsigned int N, unsigned int K, typename _Alloc>
combontoric_array
{
private:
  std::vector<T,_Alloc> m_data;
public:
 combontoric_array(void):
    m_data( binomial_function(n,k) )
  {}

  //access element methods.
}



since it forces the contents to be on the heap, the size of the array should be (N choose K)*sizeof(T)...

Share this post


Link to post
Share on other sites
Advertisement
You make it sound a bit more complex that it is. Or at least I hope I understood you correctly.

The number of elements in array is: n! / ( k! (n-k)! );

Since we know the canonical definition of template-based factorial function:

template <int N> struct Factorial { enum { value = N * Factorial<N - 1>::value }; };
template < > struct Factorial<0> { enum { value = 1 }; };

template < int N, int K >
struct Combinations {
enum { value = Factorial<N>::value / ( Factorial<K>::value * Factorial<N-K>::value) };
};

template < typename T, int N, int K >
struct combinatoric_array {
T m_data[Combinations<N,K>::value];
};





Of course, there's plenty of gotchas with integer overflow, but these can only be solved to a certain degree. The above will explode for even moderately sized N or K.

Share this post


Link to post
Share on other sites



template <unsigned int offset, unsigned int to>
struct recurMult { enum { value = (offset + to) * recurMult<offset,to-1>::value }; };

template <unsigned int offset>
struct recurMult<offset,0> { enum { value = 1 }; };

template <unsigned int from, unsigned int to>
struct factorMult { enum { value = recurMult<from,to-from>::value }; };

template <unsigned int N, unsigned int K>
struct bino { enum { value = factorMult<N-K+1, N>::value / factorMult<1,K>::value }; };

template <typename T, unsigned int N, unsigned int K>
struct CArray
{
T myData[bino<N,K>::value];
};


Share this post


Link to post
Share on other sites
Both of the solutions are not optimal, there are some properties of n choose k that one can use to avoid writing down n!/(k! (n-k)!, both solutions blow up for small values of n, even if n choose k is small, for example both barf on something like 23 choose 0, which is 1.... any takers to improve on their solutions? (they got the syntax trick, but now the analytic trick is needed). Hint an optimal solution can handle n=31 if an unsigned integer is 32 bits).

[Edited by - kRogue on June 17, 2008 4:12:49 AM]

Share this post


Link to post
Share on other sites
In this case, the problem is known to cause overflow, so it would help to state that it's non-overflow version you're looking for. It was stated as template challenge, which implied emphasis is on template meta-programming.

#include <iostream>

template < int N, int K >
struct Choose {
enum { result = Choose<N-1, K-1>::result + Choose<N-1, K>::result };
};

template < int N > struct Choose<N, 0> { enum { result = 1 }; };
template < int N > struct Choose<N, N> { enum { result = 1 }; };

int main(int argc, char**argv)
{
std::cout << Choose<9,5>::result << std::endl;
std::cout << Choose<12,7>::result << std::endl;
std::cout << Choose<30,15>::result << std::endl;
std::cout << Choose<32,15>::result << std::endl;

return 0;
}


We have only two operations, addition and constant value.

Every recursion result is obtained solely as result of addition. As such, if result fits into integer, so do all intermediate results, so do N and K, so does 1.

I believe it's safe to assume that this is overflow-safe version.

PS: I'm shocked that compiler evaluates this in a fraction of time that recursive, run-time implementation does.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
PS: I'm shocked that compiler evaluates this in a fraction of time that recursive, run-time implementation does.

The compiler will remember the types that it has seen already, so it doesn't keep recomputing the same numbers over and over again. If you add memory to your run-time implementation, you'll probably get something faster.

Note: Recursive solutions with memory are basically the same thing as dynamic programming.

Share this post


Link to post
Share on other sites
Quote:

I believe it's safe to assume that this is overflow-safe version.


as long as n choose k is strictly less than 2^32, this is guaranteed when n<32.

Quote:

PS: I'm shocked that compiler evaluates this in a fraction of time that recursive, run-time implementation does.


The compiler saves template implenetation, so when it sees

enum { result = Choose<N-1, K-1>::result + Choose<N-1, K>::result };




it looks up Choose<N-1, K-1>::result and Choose<N-1, K>::result if they were not computed yet the computes and then saves those values, so the compile computes Choose<N, K>::result in at worst O(N) where as the non-dynamic programming implementation:


unsigned int
n_choose_k(unsigned int n, unsigned int k)
{
if(n==0 or k==0 or k>=n)
{
return 1;
}
else
{
return n_choose_k(n-1,k-1) + n_choose_k(n-1,k);
}
}




will take O(2^n) time.

Share this post


Link to post
Share on other sites
Yes, I'm well aware of how it's done.

But I've had compiler blow up on template heavy projects, or take minutes to evaluate expressions. This was my natural assumption in this case as well. As always, solve first, optimize second...


It's also interesting to note that filling in values that will overflow results in a nice warning:
Quote:
1>.\choose.cpp(128) : warning C4307: '+' : integral constant overflow
1> .\choose.cpp(128) : see reference to class template instantiation 'Choose<N,K>' being compiled
1> with
1> [
1> N=35,
1> K=14
1> ]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!