On 03/12/08 06:10, Larry Evans wrote:

On 03/11/08 22:42, Max Motovilov wrote: [snip]

...

I apologize in advance if something along these lines is already available; however current public documentation doesn't mention such a facility and a brief glance into SVN did not reveal one either...

product_view

Description: provides a view of a Cartesian product of multiple sequences. Modeled after zip_view in that it expects a sequence [of length n] of sequences S1...Sn as its argument and lazily generates a sequence [of length Prod{1...n}( size< Si > )] of sequences S1[1]...Sn[1] through S1[n]...Sn[n]. Whew... I know I can write better documentation than that if I put my mind to it :(

From Prod[1..n}(size<Si>} it appears this just flattens a list 1 level. IOW: from: list < list< A0_0, A0_1> , list< A1_0, A1_1> ... , list< An_0, An_1. > it produces: list < A0_0, A0_1 , A1_0, A1_1 ... , An_0, An_1 >

Is that right?

OOPS, that would be Sum{1..n}(size<Si>} so I guess this would be more like an outer-product where for: Input: list < list<A0_0, A0_1> //S1 , list<A1_0, A1_1> //S2

Output: list < list<A0_0, A1_0> //s1[1]...S1[2]? Nope, this is S1[1]...S2[1] , list<A0_0, A2_0> , list<A0_1, A1_0> , list<A0_1, A1_1>

Here, since sizes of inputs are 2 and 2, size of output is 2*2=4. But that's inconsistent with: sequences S1[1]...Sn[1] through S1[n]...Sn[n] Could you please clarify? I'm lost ;(

On 03/12/08 07:40, Max Motovilov wrote:

Larry Evans wrote: [snip] Not quite like that, and I knew my "description" would end up being misleading :( -- so much for posting after a long working day.

Input:

list< list< A0_0, A0_1 >, list< A1_0, A1_1 >

...

Output:

list< list< A0_0, A1_0 >, list< A0_0, A1_1 >, list< A0_1, A1_0 >, list< A0_1, A1_1 >

...

I think this is what you meant to write above.

Yep. Hadn't had my first cup coffee yet ;)

Yes, it is an outer product, or direct product, or Cartesian product: C(A,B)={ [x,y] | for each x in A and y in B }

And of course if any of the sequences is empty, the output is also empty. Requires a separate rule, incidentally.

In that case, then yes, it's been at least considered. The _C++ Template Metaprogramming_ book has it as an exercise, exercise 7-8 and calls it crossproduct_view. A solution is posted here: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answers... It would be interesting to compare the two solutions. The exercise just specified 2 input sequences whereas your's allows (I guess) any n>0 number of input sequences.

On 03/12/08 08:22, Max Motovilov wrote: [snip]

...

A solution is posted here:

http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answers...

It would be interesting to compare the two solutions. The exercise just specified 2 input sequences whereas your's allows (I guess) any n>0 number of input sequences.

No, they don't look similar. As far as I can tell from a one-minute look, the solution is simply a nested for_each loop and does not provide an actual sequence adapter, despite the name cross_product_view. [snip] From one of your previous post's, the output is a crossproduct which requires a nested for_each loop to printout first the rows and for each row the elements in that row. That's the only reason for the static print_each and struct element_printer. I realize now that should have been commented to indicate it was not part of the solution but only used to demonstrate the correctness, which I hoped the printout:

Running 2 test cases... row.col=0.100 row.col=0.101 row.col=0.102 ... would have demonstrated. Also, I am not sure that cross_product_view: does not provide an actual sequence adapter because the superclass of cross_product_view is a transform_view and the first page of chapter 7 states: A sequence view ... is a lazy adapter So, in view of that, could you explain why it's not a sequence adapter?

On 03/12/08 09:56, Max Motovilov wrote:

...

...

No, they don't look similar. As far as I can tell from a one-minute look, the solution is simply a nested for_each loop and does not provide an actual sequence adapter, despite the name cross_product_view.

That's the danger of one-minute looks... I take that back. Yes, the whole thing is a sequence and output pairs are indeed lazily generated. I am not sure if this approach can be generalized to an arbitrary number of sequences. Perhaps it can be, by making the whole thing a recursive template instead of 3 separate ones. I'd try it just to see which version results in simpler code (gut feeling: the recursive template) and in faster compilation times (gut feeling: my current implementation) but customers and management are jointly snapping at my heels...

...

So, in view of that, could you explain why it's not a sequence adapter?

The usual explanation: needed more coffee :)

I'm afraid I was wrong. here's what I get as the transform output with my type_name_print: test_product boost::mpl::cross_product_view < boost::mpl::range_c < int , 0 , 3

, boost::mpl::range_c < int , 100 , 104

where the function producing this is: typedef mpl::range_c<int,0,3> seq0; typedef mpl::range_c<int,100,104> seq1; void test_product(void) { std::cout<<"test_product\n"; typedef mpl::cross_product_view<seq0,seq1> type; #ifdef TYPE_TREE_PRINT ::utility::type_name_print<type>(); #else type::print_each(); #endif } and with #define TYPE_TREE_PRINT. Which I expected to see was something contains pair's of mpl::integral_c<int,I>. So..., the code I posted is useless :( Sorry for noise. Back to drawing board.

Max Motovilov wrote:

...

...

I am not sure if this approach can be generalized to an arbitrary number of sequences. Perhaps it can be, by making the whole thing a recursive template instead of 3 separate ones. I'd try it just to see which version results in simpler code (gut feeling: the recursive template) and in faster compilation times (gut feeling: my current implementation) but customers and management are jointly snapping at my heels...

Against my better instincts I got drawn into this exercise... and I am now officially stumped. Since we have this thread, perhaps one of the MPL gurus would chime in. Here's the [entire!] code that uses the accumulator idiom:

===================================================================

template< typename S, typename A> struct product_view_ex : public if_< typename empty<S>::type, typename push_front< S, A >::type, transform_view< typename front<S>::type, product_view_ex< typename pop_front<S>::type, push_front<A,_1> > >

...

::type { typedef product_view_ex type; };

template< typename S> struct product_view : public if_< typename empty<S>::type, S, product_view_ex< S, typename clear<S>::type >

...

::type { typedef product_view type; };

===================================================================

The problem is that "if_< typename empty<S>::type ...." appears to always evaluate its "else" clause. Or, in other words [I think] empty<S>::type never evaluates as false_, even when the type of S is clearly an empty sequence (vector0<>) according to compiler messages. I am definitely missing something, but what?

The problem is that even when the sequence is empty, the pop_front<S>::type will still be evaluated. The if_ is working correctly, it's just that the compiler doesn't "know" about mpl::if_ and has to work out the template arguments even if they are not used. The following is still not quite right but it's closer. #include <boost/mpl/if.hpp> #include <boost/mpl/range_c.hpp> #include <boost/mpl/transform_view.hpp> #include <boost/mpl/back_inserter.hpp> #include <boost/mpl/push_front.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/clear.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/front.hpp> #include <boost/mpl/copy.hpp> using namespace boost::mpl; namespace mpl = boost::mpl; template< typename S, typename A> struct product_view_ex; template< typename S, typename A> struct product_view_ex_impl : public transform_view< typename front<S>::type, product_view_ex< typename pop_front<S>::type, push_front<A,_1> > > { }; template< typename S, typename A> struct product_view_ex : public eval_if<empty<S>, push_front< S, A >, product_view_ex_impl<S, A> > { }; template< typename S> struct product_view : public if_< typename empty<S>::type, S, product_view_ex< S, typename clear<S>::type > >::type { typedef product_view type; }; template<class T> struct print {}; int main() { typedef product_view<mpl::vector<mpl::range_c<int, 0, 2>, mpl::range_c<int, 3, 5> > > view; typedef print<mpl::fold<view, vector0<>, mpl::copy<_2, mpl::back_inserter<_1> > >::type>::type type; } In Christ, Steven Watanabe

on Wed Mar 12 2008, Max Motovilov <max-AT-motovilov.net> wrote:

...

In that case, then yes, it's been at least considered. The _C++ Template Metaprogramming_ book has it as an exercise, exercise 7-8 and calls it crossproduct_view.

Note to self: read the book :-). The MPL learning curve is steep and every little bit should help.

...

A solution is posted here:

http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answers...

It would be interesting to compare the two solutions. The exercise just specified 2 input sequences whereas your's allows (I guess) any n>0 number of input sequences.

No, they don't look similar. As far as I can tell from a one-minute look, the solution is simply a nested for_each loop and does not provide an actual sequence adapter, despite the name cross_product_view. Mine is a lazy view implemented using a sequence of iterator "digits".

If the original posting there isn't a true crossproduct view, I would be very grateful if you'd replace it with your own solution. Thanks and regards, -- Dave Abrahams Boost Consulting http://boost-consulting.com

AMDG Max Motovilov wrote:

David Abrahams wrote:

...

If the original posting there isn't a true crossproduct view, I would be very grateful if you'd replace it with your own solution.

I think we've settled that the solution to the book problem is a correct crossproduct view for 2 sequences. Mine is set up to handle any number of sequences from 0 to n but it is certainly bad illustrative material as it's much more convoluted.

The two are not the equivalent. Given vector_c<int, 0, 1> and vector_c<int, 2, 3> the book solution generates the equivalent of vector<vector<pair<0, 2>, pair<0, 3> >, vector<pair<1, 2>, pair<1, 3> > > while your solution flattens the result. In Christ, Steven Watanabe

Some final comments. First, in the code I posted above "push_back< S, A>" should be replaced with "push_front< S, A >", otherwise top-level sequence cannot be a list. Second, while recursive implementation is very similar to the iterative, it still generates the combinations in reverse order :) Not important for applications I can think of, but still. Finally, the performance comparison. I did it with GCC 4.2 on an Intel dual core with 4G RAM running 64-bit Ubuntu Gutsy. Iterative algorithm: 2^1 combinations: real 0m0.491s, user 0m0.432s, sys 0m0.048s 2^2 combinations: real 0m0.589s, user 0m0.488s, sys 0m0.084s 2^3 combinations: real 0m0.973s, user 0m0.624s, sys 0m0.060s 2^4 combinations: real 0m1.078s, user 0m0.824s, sys 0m0.120s 2^5 combinations: real 0m1.542s, user 0m1.424s, sys 0m0.092s 2^6 combinations: real 0m3.384s, user 0m3.012s, sys 0m0.212s 2^7 combinations: real 0m10.627s, user 0m8.781s, sys 0m0.320s 2^8 combinations: real 0m35.032s, user 0m33.582s, sys 0m0.652s 2^9 combinations: hit compiler limits, graceful exit Recursive algorithm: 2^1 combinations: real 0m0.493s, user 0m0.420s, sys 0m0.072s 2^2 combinations: real 0m0.584s, user 0m0.480s, sys 0m0.100s 2^3 combinations: real 0m0.934s, user 0m0.716s, sys 0m0.076s 2^4 combinations: real 0m1.795s, user 0m1.408s, sys 0m0.088s 2^5 combinations: real 0m5.507s, user 0m4.740s, sys 0m0.192s 2^6 combinations: real 0m29.325s, user 0m27.294s, sys 0m0.584s 2^7 combinations: overwhelmed system resources after 5min, killed

other implementations. If you post your benchmark, I could actually make a comparison.

Attaching the test program along with both versions of the product_view<>. I used the following [bash] commands to benchmark it:

for n in 1 2 3 4 5 6 7 8 9; do time g++-4.2 -DCOUNT=$n test_product_view.cpp; done

and

for n in 1 2 3 4 5 6 7 ; do time g++-4.2 -DCOUNT=$n -DRECURSIVE test_product_view.cpp; done

Note that both my versions produce flattened view (a sequence of tuples which are sequences of the same kind as the top-level sequence of the argument). Whether the flattened or the nested representations are more correct is, of course, a philosophical question -- but I originally needed the flattened view for my particular application. Regards, ...Max...

I finally looked more closely at your code and it doesn't use views as mine does. The reason I used views was because that was what the book exercise requested. On closer inspection, I'm guessing that your using a vector of "overflow" iterators, where the size of the vector is the number of domains, and each increment of the iterator increments the last element of the vector until it reaches the end, then resets that one and increments the previous overflow iterator in the vector. Is that about right?

That's correct for the "iterative" version. The "recursive" version is modeled after your code. Without the requirement to flatten the view the code was really simple; with this requirement most of the charm is gone and remaining marginal improvements in simplicity certainly don't seem to be worth the loss in performance.

This seems pretty good to me and I don't see how the one I produced could beat that. I may just try it anyway just to see.

I don't think any version that has an effective recursion on the length of the resulting sequence (as opposed to the number of domains) can do very well. On the other hand, iterator triplets and overflow flags look like ugly warts in the realm of functional programming ;) ...Max...

On 03/15/08 08:26, Larry Evans wrote:

On 03/12/08 20:21, Max Motovilov wrote: [snip]

...

Second, while recursive implementation is very similar to the iterative, it still generates the combinations in reverse order :) Not important for applications I can think of, but still.

*Maybe* one application would be matrix multiplication where the shape is known but the values aren't. Then the outer product of n domains, where each domain is range_c<0,size_rank> where size_rank is the size of the rank-th dimension of the array, would produce an matrix of the indices's into row of the left matrix and column of the right matrix.... Sorry, that explanation is getting too complicated, but anyway, the order would be important in this case.

Also, instead of a flatten'ed list, I think the cross_product should produce a nested list where the depth of nesting is the number of domains. IOW, given two domains, a matrix would be produced. Given n-domains, an array of rank n would be produced. At least I *think* that's what apl does.