C++检查前5个或后5个元素中的任何一个是否等于一个值

Question

如果没有for循环或许多ifs和elses,有没有一种简单的方法可以做到这一点.

所以举个例子..

for (i=0;i<arr.size;i++) 
    if (any of the values from i-5 to i+5, ignoring i = value) 
    {
        // Do stuff ...
    }

我是否需要设置从-5到+5的嵌套循环.或者我std::any_of 也许可以使用

Answer 1

尽管描述可能看起来如此,但复杂性是线性的,因为内部循环(如果有的话)迭代恒定次数(并且不依赖于数据的数量).

由于您建议您的数据具有数组形式(连续且可随机索引),并且使用嵌套循环实际上是使所有优化功能和处理器缓存受益的最简单且最直接的方式.由于数据的分布式特性,无论"动态排序"的容器窗台表现不佳.

我很可能会这样做

for(size_t i=5; i<N-5-1; ++i)
{
    int good=0; //will count the successful comparisons
    for(size_t j=i-5; j<=i+5; ++j) 
    {
        if(i==j) continue; //skip the i on i case
        if(array[j]==value) ++good;
    }
    if(good==10) do_stuff(i);
}

内部循环完全在缓存数据上执行(并且不依赖于N,因此它不会影响复杂性).现在,CPU工作可能会更快,尝试以某种方式对类似集合的容器(具有非连续存储)中的数据进行排序.

尽管许多开始/结束方法的优雅,旧的KISS索引获胜.

您可以免费参数化array[j]==value谓词以及5(和10 == 2*5)(模板函数将被内联),这使得它更加通用.

如果你不想分支内循环,你甚至可以用它来加快速度

for(size_t i=5; i<N-5-1; ++i)
{
    int good=0; //will count the successful comparisons
    for(size_t j=i-5; j<i; ++j) good+=(array[j]==value);
    for(size_t j=i+1; j<=i+5; ++j) good+=(array[j]==value);
    if(good==10) do_stuff(i);
}

11个元素循环被分成两半(避免检查j == i),并且增量on good是在功能上"计算",没有分支.这也将使预测管道处理器的执行速度更快.

编辑

看起来我误解了只有一个相等的值就足够了(不是全部).

如果是这种情况,你可以检查good!=0,但你甚至可以做空:

for(size_t i=5; i<N-5-1; ++i)
{
    bool good=false; //will count the successful comparisons
    for(size_t j=i-5; j<i && !good; ++j) good|=(array[j]==value);
    for(size_t j=i+1; j<=i+5  && !good; ++j) good|=(array[j]==value);
    if(good) do_stuff(i);
}

这会在找到匹配后立即中断循环,但会使循环不再可展开.移除&& !good不会切断环路,但可能正在运行它们直到结束比检查切割更快.

如果你快捷切割循环,你可以使用=而不是|=,如果你没有快捷方式,使用bool没有任何优势:|=通过编译器的立场点比+=

Answer 2

您可以使用线段树来解决此类问题，并且复杂性会大大降低。