根据其邻域变换stl向量

Question

我有一段C++代码，它转换一个向量，其中一个元素只保留一个，而且两个元素的邻居也是一个。端点的处理就好像缺少的元素是一个。例如：

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

下面的代码块可以工作，但我不确定它是否最优。我们可以假设block和state都是std::vector<int>类型的，两者都是N大小的，并且只包含元素0或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];

有更好的方法吗？我应该对std::accumulate等使用某种诡计吗？分析显示，这段代码位于我模拟的内部块中，占用了运行时的相当一部分。

Answer 1

如果速度确实是一个问题，我会尝试重写您的循环：

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];
}

如果N足够大，这可能会减少您在内存中跳转的次数，因为您只考虑过前面的2，而不是潜在的N - 1。

Answer 2

你所拥有的可能已经足够好了。如果你想尝试疯狂的事情，你总是可以这样做：

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;
});

我不确定我更喜欢这个，而不是简单的循环，只是把它作为一个潜在的替代方案。

Answer 3

就像你同步移动迭代器的方式。在1/8和1/2之间的状态向量中使用-Please检查，但在状态向量中使用N=2000000和1s以上的份额，通过构造循环，使我获得了20到10倍的相对速度优势：

    // ... 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++;
    }
}

这样做的想法是，如果状态中的前导值为0，则将指针移动1将导致下一个块中的0，如下所示。(如果== 1赋值本身没有明显的差别，则用默认的0块向量和条件赋值替换0或1。)