哨兵節(jié)點(diǎn)：思想簡(jiǎn)單，效果很棒的編程算法
作 ?者：道哥，10+年嵌入式開(kāi)發(fā)老兵，專注于：C/C++、嵌入式、Linux。
關(guān)注下方公眾號(hào)，回復(fù)【書籍】，獲取 Linux、嵌入式領(lǐng)域經(jīng)典書籍；回復(fù)【PDF】，獲取所有原創(chuàng)文章( PDF 格式)。
目錄
普通的算法
哨兵算法
小結(jié)
今天和同事一起調(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è)比較指令：
比較箱子的編號(hào) i 是否到了最后一個(gè)箱子;
比較箱子里的紙條上數(shù)字，是否與要查找的目標(biāo)數(shù)字相同;
為了便于量化問(wèn)題，我們寫一個(gè)測(cè)試代碼，打印出for循環(huán)的時(shí)間消耗。
為了便于客觀比較，在測(cè)試代碼中：
循環(huán)次數(shù)設(shè)置為?1000000?萬(wàn)次;
箱子里紙條上的數(shù)字按順序存放，不影響討論問(wèn)題的本質(zhì);
查找的數(shù)字設(shè)置為一個(gè)中間值 500000;
測(cè)試文件：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
執(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
#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
執(zhí)行：
耗時(shí)大概在960 ~ 990微秒之間。
小結(jié)
這篇短文僅僅是用for循環(huán)來(lái)討論哨兵的編程思想。
在其它的一些編程場(chǎng)景中，應(yīng)用的機(jī)會(huì)還是挺多的，也能夠非常顯著的提升代碼的執(zhí)行效率。
既然看到這里了，如果覺(jué)得不錯(cuò)，請(qǐng)您隨手點(diǎn)個(gè)【贊】和【在看】吧!
如果轉(zhuǎn)載本文，文末務(wù)必注明：“轉(zhuǎn)自微信公眾號(hào)：IOT物聯(lián)網(wǎng)小鎮(zhèn)”。
推薦閱讀
【2】C語(yǔ)言指針-從底層原理到花式技巧，用圖文和代碼幫你講解透徹
【3】原來(lái)gdb的底層調(diào)試原理這么簡(jiǎn)單
【4】Linux中對(duì)【庫(kù)函數(shù)】的調(diào)用進(jìn)行跟蹤的3種【插樁】技巧
【5】?jī)?nèi)聯(lián)匯編很可怕嗎？看完這篇文章，終結(jié)它！
【6】gcc編譯時(shí)，鏈接器安排的【虛擬地址】是如何計(jì)算出來(lái)的？
【7】GCC 鏈接過(guò)程中的【重定位】過(guò)程分析
【8】Linux 動(dòng)態(tài)鏈接過(guò)程中的【重定位】底層原理
其他系列專輯：精選文章、應(yīng)用程序設(shè)計(jì)、物聯(lián)網(wǎng)、 C語(yǔ)言。