C/C++中進步查找速度的小技巧

C/C++中進步查找速度的小技巧。本站提示廣大學習愛好者：（C/C++中進步查找速度的小技巧）文章只能為提供參考，不一定能成為您想要的結果。以下是C/C++中進步查找速度的小技巧正文

前言

當看到標題是在一個數組中查找某一個元素，或是在一個字符串中查找某個字符，我們普通都會寫出如下代碼。但這樣的代碼雖然簡約明了，但在數組元素很多的狀況下，並不是一個很好的處理方案，明天我就來分享一個進步查找速度的小技巧.

//在一個int數組中查找某個元素
int find(int A[],int n,int element)
{
 for( int i = 0; i < n; i++ )
 {
  if( A[i] == element )
   return i;
 }
 return -1;
}

//在一個字符串中查找某個字符
int find(string& str,char c)
{ 
 for( int i = 0; i < str.length(); i++ )
 {
  if( str[i] == c )
   return i;
 }
 return -1;
}

雖然每次都是寫出這樣的代碼，但我總覺得for循環中的<判別有點多余，比方數組中有100個元素，我們明明知道前99個是不會數組越界的，基本不需求判別i<n的，但我們卻多判別了99次，昨天早晨看編程珠玑的時分發現了這個小技巧，明天就來分享一下。

經過哨兵的方式去掉這多余的判別，將下面兩個辦法改造如下：

//在一個int數組中查找某個元素
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; 
}

//在一個字符串中查找某個字符
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; 
}

我勒個去，怎樣變得這麼長，但確實是增加了判別的次數，假如數組較大的話進步運轉速度一定是一定的，假如你非要說數組很小的話，說不定速度還要降低呢，那你不這樣寫不就得了，好了廢話少說，雖然代碼曾經很復雜明了了，但我還是復雜說一下思緒。

就是在數組的末尾加一個哨兵，即便不判別i<n也能確保數組不越界，加了哨兵之後if語句是必定會break的。

先判別最後一個元素的值是不是我們要查找的數，假如是，前往其下標；假如不是，將最後一個數的值保管起來，將要查找的那個數賦給最後一個元素，循環查找指定的元素，不必判別數組越界，if語句必定break，將最後一個元素的值復原，最後只用判別i<n，假如是i即為所求，否則要查找的元素不在數組中。

最後在做一個復雜的功能測試，看究竟能否進步查找速度。

測試代碼如下：

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 <<"優化前：" << end - start <<" 毫秒" << endl; 

 start = ::GetTickCount64(); 
 for( int i = 0; i < 10000; i++ ) 
  find1(A,N,1);
 end = ::GetTickCount64();
 cout <<"優化後：" << end - start <<" 毫秒" << endl; 
}

運轉後果如下：

速度還是會快一點

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或許任務能帶來一定的協助，假如有疑問大家可以留言交流。