您好,登錄后才能下訂單哦!
這篇文章主要介紹了C/C++中如何提高查找速度,具有一定借鑒價(jià)值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
示例:
//在一個(gè)int數(shù)組中查找某個(gè)元素 int find(int A[],int n,int element) { for( int i = 0; i < n; i++ ) { if( A[i] == element ) return i; } return -1; } //在一個(gè)字符串中查找某個(gè)字符 int find(string& str,char c) { for( int i = 0; i < str.length(); i++ ) { if( str[i] == c ) return i; } return -1; }
雖然每次都是寫出這樣的代碼,但我總覺得for循環(huán)中的<判斷有點(diǎn)多余,比如數(shù)組中有100個(gè)元素,我們明明知道前99個(gè)是不會(huì)數(shù)組越界的,根本不需要判斷i<n的,但我們卻多判斷了99次,昨天晚上看編程珠璣的時(shí)候發(fā)現(xiàn)了這個(gè)小技巧,今天就來分享一下。
通過哨兵的方式去掉這多余的判斷,將上面兩個(gè)方法改造如下:
//在一個(gè)int數(shù)組中查找某個(gè)元素 int find1(int A[],int n,int element) { if( n <= 0 ) return -1; if( A[--n] == element ) return n; int hold = A[n]; A[n] = element; int i = 0; for( ; ; i++ ) { if( A[i] == element ) break; } A[n] = hold; return i < n ? i : -1; } //在一個(gè)字符串中查找某個(gè)字符 int find1(string& str,char c) { int n = str.length(); if( n <= 0 ) return -1; if( str[--n] == c ) return n; int hold = str[n]; str[n] = c; int i = 0; for( ; ; i++ ) { if( str[i] == c ) break; } str[n] = hold; return i < n ? i : -1; }
我勒個(gè)去,怎么變得這么長(zhǎng),但的確是減少了判斷的次數(shù),如果數(shù)組較大的話提高運(yùn)行速度肯定是一定的,如果你非要說數(shù)組很小的話,說不定速度還要降低呢,那你不這樣寫不就得了,好了廢話少說,雖然代碼已經(jīng)很簡(jiǎn)單明了了,但我還是簡(jiǎn)單說一下思路。
就是在數(shù)組的末尾加一個(gè)哨兵,即使不判斷i<n也能確保數(shù)組不越界,加了哨兵之后if語句是必然會(huì)break的。
先判斷最后一個(gè)元素的值是不是我們要查找的數(shù),如果是,返回其下標(biāo);如果不是,將最后一個(gè)數(shù)的值保存起來,將要查找的那個(gè)數(shù)賦給最后一個(gè)元素,循環(huán)查找指定的元素,不用判斷數(shù)組越界,if語句必然break,將最后一個(gè)元素的值還原,最后只用判斷i<n,如果是i即為所求,否則要查找的元素不在數(shù)組中。
最后在做一個(gè)簡(jiǎn)單的性能測(cè)試,看到底能否提高查找速度。
測(cè)試代碼如下:
void testFind() { int N = 200000; int* A = new int[N]; A[N-2] = 1; DWORD start = ::GetTickCount64(); for( int i = 0; i < 10000; i++ ) find(A,N,1); DWORD end = ::GetTickCount64(); cout <<"優(yōu)化前:" << end - start <<" 毫秒" << endl; start = ::GetTickCount64(); for( int i = 0; i < 10000; i++ ) find1(A,N,1); end = ::GetTickCount64(); cout <<"優(yōu)化后:" << end - start <<" 毫秒" << endl; }
運(yùn)行結(jié)果如下:
速度還是會(huì)快一點(diǎn)
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“C/C++中如何提高查找速度”這篇文章對(duì)大家有幫助,同時(shí)也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識(shí)等著你來學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。