Multi-dimensional STL vector computations on rows and columns using iterators
Kamil
vector, or across each dimension... this is my old code:
#define v_ldouble vector<ldouble>
#define vv_ldouble vector<vector<ldouble> >
...
void vect_sum_old(const vv_ldouble& x, v_ldouble& sum, const int dir)
{
int v,nV,d,nD;
nV=x.size();
nD=x[0].size();
if(dir!=1)
{
sum = v_ldouble(nV,0.0);
for(v=0; v<nV; v++)
for(d=0; d<nD; d++)
sum[v]+=x[v][d];
}
else
{
sum = v_ldouble(nD,0.0);
for(d=0; d<nD; d++)
for(v=0; v<nV; v++)
sum[d]+=x[v][d];
}
}
Yeah I know... excuse my brute-force engineering approach. I am new to
STL -- I switched from C to C++ because STL vectors make my life
easier. Now I want to utilize more of what STL/C++ has to offer. I can
compute the sum of each row vector using iterators:
vv_ldouble::iterator iter;
v_ldouble::iterator iter1;
vv_ldouble mdv = vv_ldouble(3,v_ldouble(4,0.0));
v_ldouble sumrow = v_ldouble(mdv.size());
v_ldouble sumcol = v_ldouble(mdv[0].size());
...
//Sum each vector across its elements...
for(iter = mdv.begin(), iter1=sumrow.begin(); iter!=mdv.end(); iter++,
iter1++)
*iter1 = accumulate((*iter).begin(), (*iter).end(), 0.0);
How do I go about computing sum of each column using iterators
(efficiently)?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
John Potter
> #define v_ldouble vector<ldouble>
> #define vv_ldouble vector<vector<ldouble> >
Avoid macros.
typedef vector<ldouble> v_ldouble;
typedef vector<v_ldouble> vv_ldouble;
> //Sum each vector across its elements...
> for(iter = mdv.begin(), iter1=sumrow.begin(); iter!=mdv.end(); iter++,
> iter1++)
I will leave it to others to replace the loop with for_each.
> *iter1 = accumulate((*iter).begin(), (*iter).end(), 0.0);
> How do I go about computing sum of each column using iterators
> (efficiently)?
for(iter = mdv.begin(), iter1=sumcol.begin(); iter!=mdv.end(); ++iter)
transform(iter->begin(), iter->end(), iter1, iter1,
std::plus<double>());
In your original code, you could have computed both row and column sums
at the same time with the one set of loops. You can't get more
efficient than that. Had you done that or just reused the same loop
structure for columns, you might have noticed this solution for columns.
John
Wei
look at std::valarray and slices concept.
Carlos Moreno
> Months earlier I got the same problem. Maybe it's helpful to have a
> look at std::valarray and slices concept.
That's a nice solution -- particularly if the OP is using a
recent version of GCC, where valarray is nicely optimized!
(thanks Gabriel! :-))
I was also thinking that perhaps some notions from Data
Compression could be used in a custom implementation of
an Array class, given the description given by the OP.
In data compression, you use fewer bits to represent the
most common events -- in this application, ideally, one
should use a single bit to indicate the size -- 0 in that
bit means that the size is 2, and 1 in that bit means
that the next N bytes have to be interpreted differently
(indicating the non-default size). Since most of the
arrays are size 2, then you save space for most of the
cases. The problem is that stuffing that bit somewhere
may prove challenging -- it can't be part of the binary
representation of the pointer, for sure. It would perhaps
have to be part of the data pointed to (arrays a-la Pascal
-- was it in Pascal that the size of arrays was stored as
the first two characters of the array's data?). But still,
using only *one bit* may be too complicated...
The whole thing seems far too twisted and complicated, I
guess... But hey, some times crazy thoughts can lead to
useful solutions!
Carlos
--
John Potter
<moreno_at_mo...@xx.xxx> wrote:
> Wei wrote:
> > Months earlier I got the same problem. Maybe it's helpful to have a
> > look at std::valarray and slices concept.
> That's a nice solution -- particularly if the OP is using a
> recent version of GCC, where valarray is nicely optimized!
> (thanks Gabriel! :-))
Can you post some code to show how using valarray in place of
vector<vector<>> helps to compute column sums using iterators as the
subject asks?
> I was also thinking that perhaps some notions from Data
> Compression could be used in a custom implementation of
> an Array class, given the description given by the OP.
It looks like you are a victim of underquoting. This thread is about
computing column sums in a vector<vector<>>. Maybe you would like to
address this by removing the loop from the posted code for row sums and
producing a loop free solution to the column sum question.
John
Wei
> vector<vector<>> helps to compute column sums using iterators as the
> subject asks?
Sorry, not valarrays with iterators. What I meant is to use valarrays
with slices. For instance,
const int nrow = 4;
const int ncol = 3;
std::valarray<double> m(nrow * ncol); // used as a 4x3 matrix
// ... fill in the matrix ...
// C/C++ convention assumed, that's: m[2] represents the 3rd element in
the first row
std::slice s(ncol*i, nrow, ncol); // slice for column i
double colsum = m[s].sum(); // sum of column i
The method can easily be extended to n-dim problems. Some common
numeric operations are available as well. Just refer to Chapter 22 of
Stroustrup.
Wei
double colsum = m[s].sum(); // sum of column i
with
std::valarray<double> t = m[s]; // extract column i to temp valarray
double colsum = t.sum(); // sum of elems of t; thus, sum of column i in
m
Larry Evans
> I want to sum elements of a multi-dimensional vector, across each
> vector, or across each dimension... this is my old code:
Have you considered boost multi_array:
http://www.boost.org/libs/multi_array/doc/index.html
I've never used it, but during its review, I thought
a general transpose was considered. With such
a transpose (hopefully without moving any data),
the axis could be transposed so that the columns
become the rows; hence, the same algorithm you
used for summing the rows could be used to sum
the columns.
John Potter
> > Can you post some code to show how using valarray in place of
> > vector<vector<>> helps to compute column sums using iterators as the
> > subject asks?
> Sorry, not valarrays with iterators. What I meant is to use valarrays
> with slices. For instance,
> const int nrow = 4;
> const int ncol = 3;
> std::valarray<double> m(nrow * ncol); // used as a 4x3 matrix
> // ... fill in the matrix ...
> // C/C++ convention assumed, that's: m[2] represents the 3rd element in
> the first row
>
> std::slice s(ncol*i, nrow, ncol); // slice for column i
> double colsum = m[s].sum(); // sum of column i
You have mixed the form for rows with that for columns. Subscripts out
of range and undefined behavior. It is so confusing. Here are the two
sums.
for (int r(0); r != nrow; ++ r)
sr[r] = valarray<double>(m[std::slice(ncol * r, ncol, 1)]).sum();
for (int c(0); c != ncol; ++ c)
sc[c] = valarray<double>(m[std::slice(c, nrow, ncol)]).sum();
That has those messy subscript loops with low level one dimensional
thinking. Fun for mathematicians. Let's amuse ourselves by mixing
things.
std::vector<std::valarray<double> > mda(nrow,
std::valarray<double>(1., ncol));
std::vector<double> rs(nrow);
std::valarray<double> cs(0., ncol);
transform(mda.begin(), mda.end(), rs.begin(),
mem_fun_ref(&Ad::sum));
cs = accumulate(mda.begin(), mda.end(), cs);
Now we take advantage of standard algorithms and valarray operations
getting the best of both worlds. However, the OP had no valarrays and
they may introduce complications into his other code. OTOH changing to
valarrays may help his other code and mixing things would cause
problems.
For further amusement, here is a loop free solution for vector<vector>.
struct Summer {
template <class Cont>
typename Cont::value_type operator() (Cont const& c) {
return accumulate(c.begin(), c.end(),
typename Cont::value_type());
}
};
struct Adder {
template <class Cont>
Cont operator() (Cont lhs, Cont const& rhs) {
transform(lhs.begin(), lhs.end(), rhs.begin(), lhs.begin(),
std::plus<typename Cont::value_type>());
return lhs;
}
};
vector<vector<double> > mdv(nrow, vector<double>(ncol, 1.));
vector<double> rowSum(mdv.size());
vector<double> colSum(mdv[0].size());
transform(mdv.begin(), mdv.end(), rowSum.begin(), Summer());
colSum = accumulate(mdv.begin(), mdv.end(), colSum, Adder());
Now isn't that much cleaner than the original nested for loops? Anyone
feel like lambdaizing it?
It is also possible to write a loop free version that computes the row
and column sums at the same time, but that is just nested abuse of
for_each with self modifying functors. Of course, it is still much
clearer than the original for loops.
John