Proposed addition to the iterator library for iterating over all tuples.
Hi folks: I quite often have to write code to do the following: Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence. For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20). I think this problem could be solved elegantly with a iterator similar to zip_iterator. I have some questions: (1) Is there already a way to do this in boost? (2) If not, would this be a worthwhile addition to the iterator library? (3) If so, could I contribute code for this, or must the existing library owners write it? (4) If so, how would I go about getting my code added? Most of the docs seem to be about submitting entire libraries, rather than extensions to existing libraries. Thanks, Alex
On 07/24/2005 05:45 PM, Alex Mendes da Costa wrote:
Hi folks:
I quite often have to write code to do the following:
Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence.
For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20).
In: http://www.boost-consulting.com/metaprogramming-book.html exercise 7-8 requires that given "two original sequences" that the result be "all possible pairs of their elements in right cross product order". I *think* this is similar enough to your example to qualify. I don't know if the order matters, but it seems your example does produce "all possible pairs". Anyway, there is one solution to exercise 7-8 here: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answers... you might post your code there.
Larry Evans <cppljevans@cox-internet.com> writes:
On 07/24/2005 05:45 PM, Alex Mendes da Costa wrote:
Hi folks:
I quite often have to write code to do the following:
Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence.
For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20).
In:
The OP is undoubtedly talking about runtime iterators, since he referenced the iterator library. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Alex Mendes da Costa <alexmdac@gmail.com> writes:
Hi folks:
I quite often have to write code to do the following:
Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence.
For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20).
I think this problem could be solved elegantly with a iterator similar to zip_iterator. I have some questions:
Why not use zip_iterator?
(1) Is there already a way to do this in boost?
http://www.boost.org/libs/iterator/doc/zip_iterator.html ??
(2) If not, would this be a worthwhile addition to the iterator library?
Don't we already have it? -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 7/25/05, David Abrahams <dave@boost-consulting.com> wrote:
Why not use zip_iterator?
zip_iterator doesn't do what I want. From the documentation: "The zip iterator provides the ability to parallel-iterate over several controlled sequences simultaneously. A zip iterator is constructed from a tuple of iterators. Moving the zip iterator moves all the iterators in parallel. Dereferencing the zip iterator returns a tuple that contains the results of dereferencing the individual iterators." For example, if I had two sequences {1,2} and {10,20} and I used a zip_iterator to iterate through them, I would get (1,10) and (2,20). This can be verified by compiling and executing the following short program: #include <boost/iterator/zip_iterator.hpp> #include <boost/tuple/tuple.hpp> #include <iostream> #include <vector> int main() { typedef std::vector<int> IntSeq; // a = {1,2} IntSeq a; a.push_back(1); a.push_back(2); // b = {10,20} IntSeq b; b.push_back(10); b.push_back(20); typedef boost::zip_iterator< boost::tuples::tuple< IntSeq::const_iterator, IntSeq::const_iterator> > ZIt; ZIt cur(boost::make_tuple(a.begin(), b.begin())); ZIt end(boost::make_tuple(a.end(), b.end())); for ( ; cur != end; ++cur ) { std::cout << "{ " << boost::tuples::get<0>(*cur) << ", " << boost::tuples::get<1>(*cur) << " }" << std::endl; } return 0; } The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20). Alex
On 07/26/2005 07:25 AM, David Abrahams wrote:
Alex Mendes da Costa <alexmdac@gmail.com> writes:
The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20).
Oh, you want a cross-product iterator. Interesting idea.
BTW, the J or apl term for this would be "outer-product" (produced with '/' operator) applied to the "append" operator (','): ,/ IOW: 1 2 ,/ 10 20 produces: 1 10 2 10 1 20 2 20 With another operator, for example, '+' instead of ',', the result would be: 11 12 21 22 See "outer-product" on p.7 of: http://www.jsoftware.com/books/pdf/brief.pdf IOW, Alex's proposal is equivalent to J's: S1 ,/ S2 except the J result is a matrix instead of a vector, AFAICT. J uses the term "inner-product"[p.20] applied to '+' and '*' operators for "matrix-product" or "cross-product". ("cross product" doesn't occur in above pdf). A google search for outer product result in several different definitions :(
Larry Evans <cppljevans@cox-internet.com> writes:
On 07/26/2005 07:25 AM, David Abrahams wrote:
Alex Mendes da Costa <alexmdac@gmail.com> writes:
The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20).
Oh, you want a cross-product iterator. Interesting idea.
BTW, the J or apl term for this would be "outer-product" (produced with '/' operator) applied to the "append" operator (','):
,/
Wow, I'm impressed. I usedta know APL inside-out, but it's been 25 years. But that's just an ASCII translation of the real symbol, no? -- Dave Abrahams Boost Consulting www.boost-consulting.com
On 07/26/2005 10:39 AM, David Abrahams wrote:
Larry Evans <cppljevans@cox-internet.com> writes:
On 07/26/2005 07:25 AM, David Abrahams wrote:
Alex Mendes da Costa <alexmdac@gmail.com> writes:
The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20).
Oh, you want a cross-product iterator. Interesting idea.
BTW, the J or apl term for this would be "outer-product" (produced with '/' operator) applied to the "append" operator (','):
,/
Wow, I'm impressed. I usedta know APL inside-out, but it's been 25 years. But that's just an ASCII translation of the real symbol, no?
No, actually J is an ascii translation of apl. I should have been clearer ;( I originally started to use apl and %o% to "represent" the 'jot' apl symbol, but I figured referring to J with it's ascii characters would be easier and *hopefully* easier to read. Anyway, in apl, it would be: S1 %o%., S2 where, as mentioned, %o% represents to apl 'jot' symbol. The following is another reference to "outer-product" (and also where I got the idea to use %o%): http://www.math.unm.edu/splus/node37.html
On 07/26/2005 09:39 AM, Larry Evans wrote: [snip]
IOW:
1 2 ,/ 10 20
produces:
1 10 2 10 1 20 2 20
Actually, it produces 1 2 10 20 To get nearly what Alex wants, the following seems to work: <--------- cut here --------- r=: x ,"0/ y r 1 10 1 20 2 10 2 20 3 10 3 20 x 1 2 3 y 10 20 $r 3 2 2
--------- cut here --------- IOW, the result, r, is a 3 by 2 by 2 multi-dimensional array. I got this by downloading the J code as described here:
http://www.jsoftware.com/download_systems.htm and executing: jconsole and then simply trial-and-errored and reread: http://www.jsoftware.com/books/pdf/brief.pdf many times until I got something to work. The ,"0 causes , to be applied on rank 0 cells of the data (according to p. 16 of brief.pdf).
Quick update: I currently have a partial (but working) implementation of the cross_iterator. I hope to have a preliminary submission ready some time this week. Alex On 7/26/05, David Abrahams <dave@boost-consulting.com> wrote:
Alex Mendes da Costa <alexmdac@gmail.com> writes:
The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20).
Oh, you want a cross-product iterator. Interesting idea.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I've uploaded the first version of the cross_iterator. The file is called 'cross_iterator.zip'; it contains the header file and a very simple demo. There's no documentation yet. Let me know what you think. Alex On 8/1/05, Alex Mendes da Costa <alexmdac@gmail.com> wrote:
Quick update: I currently have a partial (but working) implementation of the cross_iterator. I hope to have a preliminary submission ready some time this week.
Alex
On 7/26/05, David Abrahams <dave@boost-consulting.com> wrote:
Alex Mendes da Costa <alexmdac@gmail.com> writes:
The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20).
Oh, you want a cross-product iterator. Interesting idea.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 08/01/05 03:41, Alex Mendes da Costa wrote:
Quick update: I currently have a partial (but working) implementation of the cross_iterator. I hope to have a preliminary submission ready some time this week.
Alex
On 7/26/05, David Abrahams <dave@boost-consulting.com> wrote:
Alex Mendes da Costa <alexmdac@gmail.com> writes:
The iterator that I am proposing would provide the sequence (1,10), (2,10), (1,20), (2,20). Oh, you want a cross-product iterator. Interesting idea.
A haskell list comprehension is what you need, AFAICT. FC++ can do this, if I'm correctly interpreting pages 16,19-20 of: http://www-static.cc.gatech.edu/~yannis/fc++/fcpp-lambda.pdf For example, p. 19 uses (in haskell syntax): [x+y|x <- [1,2,3], y <- [2,3], x<y] to produce: [3,4,5] (as shown on p. 16), and the corresponding FC++: compM<ListM> [ X %plus% Y | X <= list_with(1,2,3) , Y <= list_with(2,3) , guard[X %less% Y] ] is shown just below the haskell code on p. 19. In your case, I guess the X %plus% Y would maybe be replaced with some sort of mpl sequence, e.g. mpl::list<X,Y>, and for more than 2 domans, I'd guess you'd have to have: mpl::list<D1,D2,...,Dn> Also, maybe FC++ could be adapted to make this easier. Hmm.. maybe mpl::fold could be combined with compM to do this for any number of domains.
On 06/16/09 14:38, Larry Evans wrote: [snip]
FC++ can do this, if I'm correctly interpreting pages 16,19-20 of:
http://www-static.cc.gatech.edu/~yannis/fc++/fcpp-lambda.pdf
[snip]
For example, p. 19 uses (in haskell syntax):
The attached code (whose contents show the FC++ sourceforge project from which it was derived) produces: <--make run-- make -k run /home/evansl/prog_dev/boost-svn/ro/boost-trunk/sandbox/build/gcc4_4n/boost-trunk/sandbox/fc++/sourceforge/sandbox/monad_list_comprehension.exe ---------:41 1,3 1,4 2,3 2,4 ---------
--make run--
Unfortunately, while trying to figure how to convert this to have any number of input domains instead of just the two (the X and Y in | (X <= list_with(1,2)) , (Y <= list_with(3,4)) ) I ran into a roadblock of trying to understand what the code in lambda.h. The in in-source docs are sparse and the fcpp-lambda.pdf didn't explain the details either :( I may try to contact the authors or post something to the fcpp mailing list or try some more to decipher the code.
On 07/24/2005 05:45 PM, Alex Mendes da Costa wrote: [snip]
Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence.
For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20).
So the number of generated tuples is N*(min(S1.size(),S2.size). IOW, it's the same number as elements in a matrix of rank N*M where M is the size of the smallest of the N sequences. Is that right?
On 07/25/2005 07:06 PM, Larry Evans wrote: [snip]
matrix of rank N*M Should be:
shape of {N,M} and rank=size of shape, i.e. 2. That is, using apl terminology. I can see where this would be useful in forming cross product. If, instead of scalar elements in the tuples, the rows of matrix M1 and columns of matrix M2 were elements of these tuples, then you could simply apply zip_iterator to each of these and then multiply each element of that iterator and then accummulate that with plus and end up with matrix multiply!
On 07/25/2005 07:16 PM, Larry Evans wrote:
On 07/25/2005 07:06 PM, Larry Evans wrote: [snip] I can see where this would be useful in forming cross product. If, instead of scalar elements in the tuples, the rows of matrix M1 and columns of matrix M2 were elements of these tuples, then
Of course, to get the columns of matrix M2, you *might* could use the zip iterator constructed from the rows of M2. I *think* this would work with: vector<vector<int> > M2; but haven't tried. [snip]
that with plus and end up with matrix multiply! ^^^^^^^^^^^^^^^ i.e. cross product to remain consistent ;)
On 07/25/2005 07:16 PM, Larry Evans wrote: [snip]
I can see where this would be useful in forming cross product. If, instead of scalar elements in the tuples, the rows of matrix M1 and columns of matrix M2 were elements of these tuples, then you could simply apply zip_iterator to each of these and then multiply each element of that iterator and then accummulate that with plus and end up with matrix multiply!
Well, this *may* not be the most efficient method for implementing matrix multiply ;) My enthusiasm blinded my common sense. However, I've also got this wild idea that maybe template metaprogramming could maybe transform an matrix multiply expression written this way into a more efficient method. David (Abrahams), does this seem at all possible? I recall you were considering some sort of template library dealing with matrices or linear algebra or something of that sort.
Larry Evans <cppljevans@cox-internet.com> writes:
On 07/25/2005 07:16 PM, Larry Evans wrote: [snip]
I can see where this would be useful in forming cross product. If, instead of scalar elements in the tuples, the rows of matrix M1 and columns of matrix M2 were elements of these tuples, then you could simply apply zip_iterator to each of these and then multiply each element of that iterator and then accummulate that with plus and end up with matrix multiply!
Well, this *may* not be the most efficient method for implementing matrix multiply ;) My enthusiasm blinded my common sense. However, I've also got this wild idea that maybe template metaprogramming could maybe transform an matrix multiply expression written this way into a more efficient method. David (Abrahams), does this seem at all possible?
I don't really understand what you have in mind.
I recall you were considering some sort of template library dealing with matrices or linear algebra or something of that sort.
Yes, I am working on it, but I'm not going to approach matrix multiplication using anything like a cross product iterator. The key ideas in efficient matrix multiplication are hierarchical decomposition and blocking to make the best use of registers and various levels of cache (not to mention SMPs). -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (4)
-
Alex Mendes da Costa -
David Abrahams -
Larry Evans -
Larry Evans