哨兵節點：思想簡單，效果很棒的編程算法
別人的經驗，我們的階梯！
今天和同事一起調代碼，定位到一處很耗時的地方。
在某個線程中，同步周期需要保證在??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??。
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??：
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??循環來討論哨兵的編程思想。
在其它的一些編程場景中，應用的機會還是挺多的，也能夠非常顯著的提升代碼的執行效率。
