别人的经验，我们的阶梯！

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

在某个线程中，同步周期需要保证在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 ＂， i）；

      break；

  ｝

｝

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

比较箱子的编号 i 是否到了最后一个箱子；

比较箱子里的纸条上数字，是否与要查找的目标数字相同；

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

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

循环次数设置为 1000000 万次；

箱子里纸条上的数字按顺序存放，不影响讨论问题的本质；

查找的数字设置为一个中间值 500000；

测试文件：loop1．c

＃include ＜unistd．h＞

＃include ＜stdio．h＞

＃include ＜stdlib．h＞

＃include ＜time．h＞

＃include ＜sys／time．h＞

＃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 ＂， 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 ＂， us2 － us1）；

       return 0；

｝

编译：gcc loop1．c －o loop1

执行：

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

哨兵算法

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

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

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

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

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

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

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

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

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

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

测试代码loop2．c：

＃include ＜unistd．h＞

＃include ＜stdio．h＞

＃include ＜stdlib．h＞

＃include ＜time．h＞

＃include ＜sys／time．h＞

＃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 ＂， 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 ＂， us2 － us1）；

      return 0；

｝

编译：gcc loop2．c －o loop2

执行：

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

小结

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

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