哨兵节点：思想简单，效果很棒的编程算法

别人的哨兵思想算法经验，我们的节点简单阶梯！

今天和同事一起调代码，效果定位到一处很耗时的棒的编程地方。

在某个线程中，哨兵思想算法同步周期需要保证在​​2​​​毫秒(如果耗时不到​​2​​​毫秒，节点简单那么就让剩下的效果时间进行​​sleep​​)。

但是棒的编程在调用一个模块的内部函数时，时不时的哨兵思想算法就飘到了​​3~5​​毫秒，时间抖动毫无保证。节点简单

后来仔细分析了一下被调用的效果函数，发现是棒的编程在查找链表中某个目标节点时，由于目标节点的哨兵思想算法不确定性，导致耗时飘来飘去。节点简单

后来想到是效果否可以用"哨兵"的思路来解决问题，于是就试了一下，果然有效。

特分享于此，源码下载使用​​2​​段代码来看一下代码执行效率的提升。

普通的算法

所谓的哨兵，就是一个标志，一个与查找目标对象一样的操作对象。

以前有一本书中举过这样的一个例子：

假如有​​10000​​​个纸箱，每个箱子里面都有一张纸条，纸条上写有​​1 ~ 10000​​这些数字，数字不会重复。

现在：别人给了一个随机的数字，我们需要在这​​10000​​个箱子里找到与这个数字相同的纸条，找到之后退出操作。

面对这个问题，最直觉的想法就是：从头开始，遍历这​​10000​​个箱子，检查其中的纸条上数字是否与目标相同。

因为纸箱里的纸条不是按照顺序排列的，所以只能从头开始遍历;

大概就是下面这个样子：

int lookfor_num = xxx;

for (int i = 0; i < 10000; ++i)

{

if (box[i] == lookfor_num)

{

printf("找到了！站群服务器箱子编号是：%d \n", i);

break;

}

}

从上面这段示意性代码中可以看出，在​​for​​​循环中主要有​​2​​个比较指令：

比较箱子的编号 i 是否到了最后一个箱子;比较箱子里的纸条上数字，是否与要查找的目标数字相同;

为了便于量化问题，我们写一个测试代码，打印出​​for​​循环的时间消耗。

为了便于客观比较，在测试代码中：

循环次数设置为 500000 万次;箱子里纸条上的数字按顺序存放，不影响讨论问题的本质;查找的数字设置为一个中间值 500000;

测试文件：​​loop1.c​​。

#include

#include

#include

#include

#include

#define LOOP_NUM 1000000

int main(int argc, char *argv[])

{

long data[LOOP_NUM];

long rand_num = 500000;

struct timeval tv1, tv2;

for (long i = 0; i < LOOP_NUM; ++i)

{

data[i] = i;

}

gettimeofday(&tv1, 0);

for (long i = 0; i < LOOP_NUM; ++i)

{

if (data[i] == rand_num)

{

printf("hit rand_num. i = %ld \n", i);

break;

}

}

gettimeofday(&tv2, 0);

long us1 = tv1.tv_sec * 1000000 + tv1.tv_usec;

long us2 = tv2.tv_sec * 1000000 + tv2.tv_usec;

printf("time elapse: %ld \n", us2 - us1);

return 0;

}

编译：​​gcc loop1.c -o loop1​​。

执行：

耗时大概在​​1350 ~ 1380​​微秒左右。

哨兵算法

哨兵算法的主要思想就是：降低在​​for​​循环中的比较操作。

因为纸箱的数量是有限的，上面的代码中，在还没有找到目标数字之前，需要对纸箱的序号进行检查：以免超过了最大的亿华云计算纸箱。

我们可以在最后额外添加一个纸箱，并且在其中存放我们查找的目标数字，额外添加的这个纸箱就叫做​​哨兵​​！

这样的话，在​​for​​循环中，就不需要检查当前这个纸箱序号是否超过了最大的纸箱。

因为：我们在哨兵纸箱中放了被查找的那个数字，所以是一定能够找到目标数字的：

要么是在前面的纸箱中, 要么是在哨兵纸箱中！

因此，在​​for​​循环中，就只需要比较纸条上的数字，而不用比较纸箱的序号是否达到最后一个了。

当找到目标数字之后，唯一要多做的步骤是：检查这个箱子是否为哨兵纸箱。

如果是哨兵纸箱：说明前面的纸箱中没有查找到目标数字。

如果不是哨兵纸箱：说明在前面的纸箱中查找到了目标数字。

测试代码​​loop2.c​​：

#include

#include

#include

#include

#include

#define LOOP_NUM 1000000

int main(int argc, char *argv[])

{

long data[LOOP_NUM + 1]; // add another room

long rand_num = 500000;

struct timeval tv1, tv2;

for (long i = 0; i < LOOP_NUM; ++i)

{

data[i] = i;

}

data[LOOP_NUM] = rand_num; // add a sentinel

gettimeofday(&tv1, 0);

long i = 0;

while (1)

{

if (data[i] == rand_num)

{

if (i != LOOP_NUM)

{

printf("hit rand_num. i = %ld \n", i);

break;

}

}

++i;

}

gettimeofday(&tv2, 0);

long us1 = tv1.tv_sec * 1000000 + tv1.tv_usec;

long us2 = tv2.tv_sec * 1000000 + tv2.tv_usec;

printf("time elapse: %ld \n", us2 - us1);

return 0;

}

编译：​​gcc loop2.c -o loop2​​。

执行：

耗时大概在​​960 ~ 990​​微秒之间。

小结

这篇短文仅仅是用​​for​​循环来讨论哨兵的编程思想。

在其它的一些编程场景中，应用的机会还是挺多的，也能够非常显著的提升代码的执行效率。

很赞哦!（52）