不管描述看起来如何,复杂性是linear因为内部循环(如果有)迭代恒定次数(并且不依赖于数据的数量)。
由于您建议您的数据具有数组形式(连续且可随机索引),并且使用嵌套循环实际上是利用所有优化功能和处理器缓存的最简单、最直接的方法。由于数据的分布式特性,任何“动态排序”容器的性能仍然很差。
我很可能会这样做
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)并且增量good
是按函数“计算”的,没有分支。这也将导致预测管道处理器的执行速度更快。
EDIT
看来我误解了只有一个相等的值就足够了(不是全部)。
如果是这种情况,您可以检查一下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 没有任何优势:|=
从编译器的角度来看,比+=