別人的經(jīng)驗(yàn)，我們的階梯！

今天和同事一起調(diào)代碼，定位到一處很耗時(shí)的地方。

在某個(gè)線程中，同步周期需要保證在??2???毫秒(如果耗時(shí)不到??2???毫秒，那么就讓剩下的時(shí)間進(jìn)行??sleep??)。

但是在調(diào)用一個(gè)模塊的內(nèi)部函數(shù)時(shí)，時(shí)不時(shí)的就飄到了??3~5??毫秒，時(shí)間抖動(dòng)毫無(wú)保證。

后來(lái)仔細(xì)分析了一下被調(diào)用的函數(shù)，發(fā)現(xiàn)是在查找鏈表中某個(gè)目標(biāo)節(jié)點(diǎn)時(shí)，由于目標(biāo)節(jié)點(diǎn)的不確定性，導(dǎo)致耗時(shí)飄來(lái)飄去。

后來(lái)想到是否可以用"哨兵"的思路來(lái)解決問(wèn)題，于是就試了一下，果然有效。

特分享于此，使用??2??段代碼來(lái)看一下代碼執(zhí)行效率的提升。

普通的算法

所謂的哨兵，就是一個(gè)標(biāo)志，一個(gè)與查找目標(biāo)對(duì)象一樣的操作對(duì)象。

以前有一本書中舉過(guò)這樣的一個(gè)例子：

假如有??10000???個(gè)紙箱，每個(gè)箱子里面都有一張紙條，紙條上寫有??1 ~ 10000??這些數(shù)字，數(shù)字不會(huì)重復(fù)。

現(xiàn)在：別人給了一個(gè)隨機(jī)的數(shù)字，我們需要在這??10000??個(gè)箱子里找到與這個(gè)數(shù)字相同的紙條，找到之后退出操作。

面對(duì)這個(gè)問(wèn)題，最直覺(jué)的想法就是：從頭開(kāi)始，遍歷這??10000??個(gè)箱子，檢查其中的紙條上數(shù)字是否與目標(biāo)相同。

因?yàn)榧埾淅锏募垪l不是按照順序排列的，所以只能從頭開(kāi)始遍歷;

大概就是下面這個(gè)樣子：

int lookfor_num = xxx;
for (int i = 0; i < 10000; ++i)
{
    if (box[i] == lookfor_num)
    {
        printf("找到了！箱子編號(hào)是：%d \n", i);
        break;
    }
}

從上面這段示意性代碼中可以看出，在??for???循環(huán)中主要有??2??個(gè)比較指令：

1. 比較箱子的編號(hào) i 是否到了最后一個(gè)箱子;
2. 比較箱子里的紙條上數(shù)字，是否與要查找的目標(biāo)數(shù)字相同;

為了便于量化問(wèn)題，我們寫一個(gè)測(cè)試代碼，打印出??for??循環(huán)的時(shí)間消耗。

為了便于客觀比較，在測(cè)試代碼中：

1. 循環(huán)次數(shù)設(shè)置為 500000 萬(wàn)次;
2. 箱子里紙條上的數(shù)字按順序存放，不影響討論問(wèn)題的本質(zhì);
3. 查找的數(shù)字設(shè)置為一個(gè)中間值 500000;

測(cè)試文件：??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 \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??。

執(zhí)行：

耗時(shí)大概在??1350 ~ 1380??微秒左右。

哨兵算法

哨兵算法的主要思想就是：降低在??for??循環(huán)中的比較操作。

因?yàn)榧埾涞臄?shù)量是有限的，上面的代碼中，在還沒(méi)有找到目標(biāo)數(shù)字之前，需要對(duì)紙箱的序號(hào)進(jìn)行檢查：以免超過(guò)了最大的紙箱。

我們可以在最后額外添加一個(gè)紙箱，并且在其中存放我們查找的目標(biāo)數(shù)字，額外添加的這個(gè)紙箱就叫做??哨兵??！

這樣的話，在??for??循環(huán)中，就不需要檢查當(dāng)前這個(gè)紙箱序號(hào)是否超過(guò)了最大的紙箱。

因?yàn)椋何覀冊(cè)谏诒埾渲蟹帕吮徊檎业哪莻€(gè)數(shù)字，所以是一定能夠找到目標(biāo)數(shù)字的：

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

因此，在??for??循環(huán)中，就只需要比較紙條上的數(shù)字，而不用比較紙箱的序號(hào)是否達(dá)到最后一個(gè)了。

當(dāng)找到目標(biāo)數(shù)字之后，唯一要多做的步驟是：檢查這個(gè)箱子是否為哨兵紙箱。

如果是哨兵紙箱：說(shuō)明前面的紙箱中沒(méi)有查找到目標(biāo)數(shù)字。

如果不是哨兵紙箱：說(shuō)明在前面的紙箱中查找到了目標(biāo)數(shù)字。

測(cè)試代碼??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 \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??。

執(zhí)行：

耗時(shí)大概在??960 ~ 990??微秒之間。

小結(jié)

這篇短文僅僅是用??for??循環(huán)來(lái)討論哨兵的編程思想。

在其它的一些編程場(chǎng)景中，應(yīng)用的機(jī)會(huì)還是挺多的，也能夠非常顯著的提升代碼的執(zhí)行效率。