[multi_array] Useful algorithms (from Re: Multi_array: A "proper" iterator over a N>1 Multi_array?)
On a recent thread, Bruno Martinez provided a std::for_each-like function for multi_arrays which lets users apply a function to each element in a multi_array or view without having to know anything about the dimensions. I've been playing around with it (on MSVC 7.1) and it works perfectly. It seems like a good utility for anyone using boost.multi_array. Working from Bruno's code, I wrote a similar std::accumulate-like function, which could also be generally useful. I'm fairly new to template programming, so if someone could look over the code below and see if I've done something dangerous or stupid, it would be much appreciated. Also, is there some standard Boost way of making this sort of code generally available? It probably isn't at a level where it could be included in the library, but it seems like a shame to just let it languish in the bowels of the mailing list archive. Anyway, here are both algorithms: My accumulate-like function: template<class MA, class T, class F, int dim> struct accum_impl { F f; T &val; accum_impl(T &val, F f) : f(f), val(val) {} T operator()(MA& ma) { std::for_each(ma.begin(), ma.end(), accum_impl<typename boost::add_const<MA::const_reference>::type, T, F, dim-1>(val, f)); return val; } }; template<class Ref, class T, class F> struct accum_impl<Ref, T, F, 0> { F f; T &val; accum_impl(T &val, F &f) : f(f), val(val) {} T operator()(Ref r) { val = f(val, r); return val; } }; template<class MA, class T, class F> T multi_accum(MA& ma, T init, F f) { accum_impl<MA, T, F, MA::dimensionality> impl(init, f); return impl(ma); } And a test: typedef boost::multi_array<int, 3> array_type; typedef array_type::index_range range; typedef array_type::index index; array_type B(boost::extents[4][2][3]); int values = 0; for(index i = 0; i != 4; ++i) for(index j = 0; j != 2; ++j) for(index k = 0; k != 3; ++k) B[i][j][k] = values++; array_type::array_view<2>::type myview = B[ boost::indices[range(1,3)][1][range(0,2)] ]; cout << "Sum: " << multi_accum(myview, 0, std::plus<int>()) << endl; cout << "Product: " << multi_accum(myview, 1, std::multiplies<int>()) << endl; Bruno Martinez's for_each-like function: template<class MA, class F, int dim> struct for_each_impl { F f; for_each_impl(F f) : f(f) {} void operator()(MA& ma) { std::for_each(ma.begin(), ma.end(), for_each_impl<typename MA::reference, F, dim-1>(f)); } }; template<class Ref, class F> struct for_each_impl<Ref, F, 0> { F f; for_each_impl(F f) : f(f) {} void operator()(Ref r) { f(r); } }; template<class MA, class F> void multi_for_each(MA& ma, F f) { for_each_impl<MA, F, MA::dimensionality> impl(f); impl(ma); } And a test: typedef boost::multi_array<double, 3> array_type; typedef array_type::index index; array_type myarray(boost::extents[3][4][2]); typedef array_type::index_range range; array_type::array_view<3>::type myview = myarray[ boost::indices[range(0,2)][range(1,3)][range(0,4,2)] ]; multi_for_each(myview, _1 = 56);
"Beth Jacobson" wrote [...]
Also, is there some standard Boost way of making this sort of code generally available? It probably isn't at a level where it could be included in the library, but it seems like a shame to just let it languish in the bowels of the mailing list archive.
The usual method is to put it in the Boost Vault : http://boost-consulting.com/vault/ in a zip file. You will need to register. (The login link also takes you to a register link.) regards Andy Little
Andy Little wrote:
"Beth Jacobson" wrote
[...]
Also, is there some standard Boost way of making this sort of code generally available? It probably isn't at a level where it could be included in the library, but it seems like a shame to just let it languish in the bowels of the mailing list archive.
The usual method is to put it in the Boost Vault :
http://boost-consulting.com/vault/
in a zip file.
You will need to register. (The login link also takes you to a register link.)
I'll also point out that there have been Wiki pages devoted to this sort of contribution for quite some time. These have the advantage that they make their way into Google. See http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?STLAlgorithmE... Although if this is limited to multi-array it might be a bit more specialized. I look at these Wiki contributions more like ideas than finished products, certainly not up to the usual Boost standards, but useful non-the-less. Jeff
Jeff Garland wrote:
Andy Little wrote:
"Beth Jacobson" wrote
[...]
Also, is there some standard Boost way of making this sort of code generally available? It probably isn't at a level where it could be included in the library, but it seems like a shame to just let it languish in the bowels of the mailing list archive. The usual method is to put it in the Boost Vault :
My impression was that the Boost Vault is intended for libraries on the Boost candidate track, that is they're put there with an eye to eventually submitting them for inclusion the the Boost libraries. If that's true, it's not really appropriate for this stuff.
I'll also point out that there have been Wiki pages devoted to this sort of contribution for quite some time. These have the advantage that they make their way into Google. See
http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?STLAlgorithmE...
Although if this is limited to multi-array it might be a bit more specialized. I look at these Wiki contributions more like ideas than finished products, certainly not up to the usual Boost standards, but useful non-the-less.
That sounds just right for these functions. They are specific to multi-arrays so they don't belong on the AlgorithmExtensions page, but I'd like to create a Boost.MultiArray/Algorithms page which could be added to as people adapt more algorithms for use with multi_arrays. Do I need to get somebody's ok for this, or can I just dive right in? (While we're at it, a "jeff's cool date time extensions" Wiki page might be nice too. ;-)) Regards, Beth
As I said in a former message that I am afraid fell through the cracks, sorry if I am repeating myself, I don't think rewriting the whole STL algorithm lib for multi_array is a solution. for_each, accumulate, sort, where do we stop? I recently needed to apply random shuffle, for instance. I think the solution is to define iterators that provide a "flat", element by element view of a multi_array. These iterators would be regular skip iterators that just a have a fancy increment operation that looks at the stride vector to decide by how much to jump when incremented. Let's say that these are returned by begin_element and end_element. Then you could do on multi array ma things like for_each(ma.begin_element(), ma.end_element(), do_something()) or accumulate(ma.begin_element(), ma.end_element(), 0) and so on for all STL algorithms, all the statstical functions that I wrote (GPLed, maybe the beginning of a boost stats lib?, mail me if interested) and more. I've been using data() and data()+num_elements for the same purpose, but that breaks for non contiguos storage (that is, not guaranteed to work for views) I don't think rewriting all the algorithms for multi_array is a viable strategy, nor is in keeping with the idea that data structures and algorithms should be made as ortogonal as reasonably possible. Just my 2c Antonio You can do that right now with data() and data() + num_elements On 5/16/06, Beth Jacobson <bethj@bajac.com> wrote:
On a recent thread, Bruno Martinez provided a std::for_each-like function for multi_arrays which lets users apply a function to each element in a multi_array or view without having to know anything about the dimensions. I've been playing around with it (on MSVC 7.1) and it works perfectly. It seems like a good utility for anyone using boost.multi_array.
Working from Bruno's code, I wrote a similar std::accumulate-like function, which could also be generally useful. I'm fairly new to template programming, so if someone could look over the code below and see if I've done something dangerous or stupid, it would be much appreciated.
Also, is there some standard Boost way of making this sort of code generally available? It probably isn't at a level where it could be included in the library, but it seems like a shame to just let it languish in the bowels of the mailing list archive.
Anyway, here are both algorithms:
My accumulate-like function: template<class MA, class T, class F, int dim> struct accum_impl { F f; T &val;
accum_impl(T &val, F f) : f(f), val(val) {}
T operator()(MA& ma) { std::for_each(ma.begin(), ma.end(), accum_impl<typename boost::add_const<MA::const_reference>::type, T, F, dim-1>(val, f)); return val; } };
template<class Ref, class T, class F> struct accum_impl<Ref, T, F, 0> { F f; T &val;
accum_impl(T &val, F &f) : f(f), val(val) {}
T operator()(Ref r) { val = f(val, r); return val; } };
template<class MA, class T, class F> T multi_accum(MA& ma, T init, F f) { accum_impl<MA, T, F, MA::dimensionality> impl(init, f); return impl(ma); }
And a test: typedef boost::multi_array<int, 3> array_type; typedef array_type::index_range range; typedef array_type::index index; array_type B(boost::extents[4][2][3]);
int values = 0; for(index i = 0; i != 4; ++i) for(index j = 0; j != 2; ++j) for(index k = 0; k != 3; ++k) B[i][j][k] = values++;
array_type::array_view<2>::type myview = B[ boost::indices[range(1,3)][1][range(0,2)] ];
cout << "Sum: " << multi_accum(myview, 0, std::plus<int>()) << endl; cout << "Product: " << multi_accum(myview, 1, std::multiplies<int>()) << endl;
Bruno Martinez's for_each-like function:
template<class MA, class F, int dim> struct for_each_impl { F f; for_each_impl(F f) : f(f) {}
void operator()(MA& ma) { std::for_each(ma.begin(), ma.end(), for_each_impl<typename MA::reference, F, dim-1>(f)); } };
template<class Ref, class F> struct for_each_impl<Ref, F, 0> { F f; for_each_impl(F f) : f(f) {}
void operator()(Ref r) { f(r); } };
template<class MA, class F> void multi_for_each(MA& ma, F f) { for_each_impl<MA, F, MA::dimensionality> impl(f); impl(ma); }
And a test:
typedef boost::multi_array<double, 3> array_type; typedef array_type::index index; array_type myarray(boost::extents[3][4][2]); typedef array_type::index_range range; array_type::array_view<3>::type myview = myarray[ boost::indices[range(0,2)][range(1,3)][range(0,4,2)] ]; multi_for_each(myview, _1 = 56);
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
I'm going to second Antonio's comments. A globally applicable iterator across a multi-array's data elements would provide a /very/ useful tool, and doesn't seem all that impossible to program, requiring all the magic be done behind the scenes in operator+ etc. In addition, I'd love to see a Boost statistical package, but am unfamiliar with the process of getting support for a new boost library, nor what the early stages of development look like. - Greg Link On May 17, 2006, at 2:46 PM, Antonio Piccolboni wrote:
As I said in a former message that I am afraid fell through the cracks, sorry if I am repeating myself, I don't think rewriting the whole STL algorithm lib for multi_array is a solution. for_each, accumulate, sort, where do we stop? I recently needed to apply random shuffle, for instance. I think the solution is to define iterators that provide a "flat", element by element view of a multi_array. These iterators would be regular skip iterators that just a have a fancy increment operation that looks at the stride vector to decide by how much to jump when incremented. Let's say that these are returned by begin_element and end_element. Then you could do on multi array ma things like
for_each(ma.begin_element(), ma.end_element(), do_something())
or
accumulate(ma.begin_element(), ma.end_element(), 0)
and so on for all STL algorithms, all the statstical functions that I wrote (GPLed, maybe the beginning of a boost stats lib?, mail me if interested) and more. I've been using data() and data()+num_elements for the same purpose, but that breaks for non contiguos storage (that is, not guaranteed to work for views)
I don't think rewriting all the algorithms for multi_array is a viable strategy, nor is in keeping with the idea that data structures and algorithms should be made as ortogonal as reasonably possible. Just my 2c
Antonio
Antonio Piccolboni wrote:
As I said in a former message that I am afraid fell through the cracks, sorry if I am repeating myself, I don't think rewriting the whole STL algorithm lib for multi_array is a solution. for_each, accumulate, sort, where do we stop? I recently needed to apply random shuffle, for instance. I think the solution is to define iterators that provide a "flat", element by element view of a multi_array. These iterators would be regular skip iterators that just a have a fancy increment operation that looks at the stride vector to decide by how much to jump when incremented.
I agree that would be the ideal solution, but the multi_array-specific algorithms have one big advantage that kind of iterator: they already exist.
I've been using data() and data()+num_elements for the same purpose, but that breaks for non contiguos storage (that is, not guaranteed to work for views)
That's exactly the issue that these algorithms address. They accept regular multi_arrays, subarrays, and views and handle them all correctly.
I don't think rewriting all the algorithms for multi_array is a viable strategy, nor is in keeping with the idea that data structures and algorithms should be made as ortogonal as reasonably possible. Just my 2c
I agree in theory, but I'm not familiar enough either with the multi_array library or template programming in general to tackle the job of writing the iterator myself. If you or someone else has definite plans to do it, I won't bother with a Wiki page for the algorithms, but if the iterator is likely to remain theoretical for the foreseeable future, it still seems worthwhile to offer a working, though imperfect solution for general use. Jeff Garland described Wiki contributions as "certainly not up to the usual Boost standards, but useful none-the-less." The algorithms don't meet Boost standards for the reasons you described, but I think they conform well to the "useful none-the-less" standard required for the Wiki. Regards, Beth
participants (5)
-
Andy Little -
Antonio Piccolboni -
Beth Jacobson -
Greg Link -
Jeff Garland