1
\$\begingroup\$

I have a piece of C++ code that transforms a vector where an element only stays one if itself and both of it's neighbors are one as well. End-points are handled as if the missing element is one. For example:

old: 1 1 0 1 1 1 0 1 1 0
new: 1 0 0 0 1 0 0 0 0 0

The following block of code works, but I'm not sure if it is optimal. We can assume that block and state are of type std::vector<int>, both of size N, and only contain elements 0 or 1:

  // Handle the end-points
  block[0]   = state[0]*state[1];
  block[N-1] = state[N-2]*state[N-1];

  // Set the cooperative behavior
  for(int i=1;i<N-1;i++)
    block[i] = state[i-1]*state[i]*state[i+1];

Is there a better way to do this? Should I be using some kind of trickery with std::accumulate and the like? Profiling show that this piece of code is in the inner-block of my simulation and takes up a sizable fraction of my runtime.

\$\endgroup\$
  • 1
    \$\begingroup\$ Since you're just using 0s and 1s, you could consider std::vector<bool>. On the other hand, the answers here suggest otherwise. \$\endgroup\$ – Jamal Oct 30 '13 at 21:01
  • 2
    \$\begingroup\$ @Jamal space is not an issue, speed is. Some implementations of std::vector<bool> are problematic since it is specifically specialized. In general, I've found that I can avoid many of those headaches by using int's instead. \$\endgroup\$ – Hooked Oct 30 '13 at 21:03
  • 2
    \$\begingroup\$ @Jamal: std::vector<bool> is not recommended. It is only kept for compatability. It has sever performance issues and does not have the same usage characteristics as other containers. It is considered a bit of a mistake. Prefer std::bitset<> if you want bits. But std::vector<char> is a good compromise of speed and size. \$\endgroup\$ – Martin York Oct 30 '13 at 23:21
  • \$\begingroup\$ @LokiAstari: Yeah, I was hesitant about the vector, but I also wasn't sure about bitset (although not for the same reason). \$\endgroup\$ – Jamal Oct 30 '13 at 23:23
1
\$\begingroup\$

If speed really is an issue, I would try this rewrite of your loop:

const int *prev = &state[0];
int *pblock = &block[1];
for (int i = 0; i < N-1; ++i, ++prev, ++pblock) { // hopefully i is a compile-time constant?
    *pblock = prev[0] * prev[1] * prev[2];
}

If N is sufficiently large, this could reduce how much you have to jump around in memory, since you're only ever looking ahead 2, instead of potentially N - 1.

\$\endgroup\$
  • \$\begingroup\$ This doesn't actually speed things up, but you've given me an idea that does. I've posted it as an answer, but I'm accepting this one as both answers were useful! \$\endgroup\$ – Hooked Oct 31 '13 at 14:57
1
\$\begingroup\$

What you have is probably good enough. If you want to try something crazy, you could always do:

boost::range::transform(boost::irange(0, N), block.begin(), [&](const int i){
    int pre = i-1 >= 0 ? state[i-1] : 1;
    int post = i+1 < N ? state[i+1] : 1;
    return pre * state[i] * post;
});

Not sure I prefer that to the simple loop that you have, but just throwing it out as a potential alternative.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I appreciate the alternative. Wouldn't this be necessarily slower since pre,post have to be check N times rather than once? \$\endgroup\$ – Hooked Oct 30 '13 at 21:19
1
\$\begingroup\$

Like the way you're moving the iterators in sync. -Please check but playing around with N=2000000 and a share of 1s over 0s in the state vector between 1/8 and 1/2 gives me a comparative speed advantage of 20 to 10 times respectively, by structuring the loop:

    // ... your loop result; cstate is a copy of the random_shuffle-d state vector
block.clear();
block.assign(N, 0);

block[0]   = cstate[0]*cstate[1];
block[N-1] = cstate[N-2]*cstate[N-1];
block[N-2] = cstate[N-3]*cstate[N-2]*cstate[N-1];
block[N-3] = cstate[N-4]*cstate[N-3]*cstate[N-2];

b_itr = block.begin()+1;
itr0  = cstate.begin();
itr1  = itr0+1;
itr2  = itr1+1;
//end   = cstate.end();

unsigned c(0); // counter in lieu of cstate.end() which may or may not be hit

while(c < N-4) {
    if(0 == (*itr2)) {
        itr0 += 3; itr1 += 3; itr2 += 3; b_itr += 3; c +=3;
    }
    else if(0 == (*itr1)) {
        itr0 += 2; itr1 += 2; itr2 += 2; b_itr += 2; c +=2;
    }
    else if(0 == (*itr0)) {
        itr0++; itr1++; itr2++; b_itr++; c++;
    }
    else {
        (*b_itr) = 1;
        itr0++; itr1++; itr2++; b_itr++; c++;
    }
}

The idea is that if the leading value in state is 0, moving the pointers by 1 will result in a 0 in block next, likewise in the following step. (Replacing constantly assigning 0 or 1 with a default 0 block vector and a conditional if == 1 assignment did not make in itself a noticeable difference.)

\$\endgroup\$
0
\$\begingroup\$

For completeness, I'm using the solution posted below which is inspired from one of @Barry's answers. The idea is to replace [] with a pointer to dereference. This gives about 10% speedup.

  // Handle the end-points of the chain
  block[0]   = state[0]*state[1];
  block[N-1] = state[N-2]*state[N-1];

  auto b_itr = block.begin()+1;
  auto itr0  = state.begin();
  auto itr1  = itr0+1;
  auto itr2  = itr1+1;
  auto end   = state.end();

  while(itr2 != end) {
    (*b_itr) = (*itr0)*(*itr1)*(*itr2);
    itr0++; itr1++; itr2++; b_itr++;
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.