快捷導航

C/C++中提高查找速度的小技巧

更新時間：2017年01月17日 10:37:16 作者：啊漢

這篇文章主要給大家介紹了C/C++中提高數(shù)組中查找某個元素或者字符串中查找某個字符效率的小技巧,提高速度對我們?nèi)粘ｉ_發(fā)來說還是很有用的，文中給出了詳細的示例代碼，需要的朋友可以參考借鑒，下面來一起看看吧。

前言

當看到題目是在一個數(shù)組中查找某一個元素，或是在一個字符串中查找某個字符，我們一般都會寫出如下代碼。但這樣的代碼雖然簡潔明了，但在數(shù)組元素很多的情況下，并不是一個很好的解決方案，今天我就來分享一個提高查找速度的小技巧.

//在一個int數(shù)組中查找某個元素
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循環(huán)中的<判斷有點多余，比如數(shù)組中有100個元素，我們明明知道前99個是不會數(shù)組越界的，根本不需要判斷i<n的，但我們卻多判斷了99次，昨天晚上看編程珠璣的時候發(fā)現(xiàn)了這個小技巧，今天就來分享一下。

通過哨兵的方式去掉這多余的判斷，將上面兩個方法改造如下：

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

我勒個去，怎么變得這么長，但的確是減少了判斷的次數(shù)，如果數(shù)組較大的話提高運行速度肯定是一定的，如果你非要說數(shù)組很小的話，說不定速度還要降低呢，那你不這樣寫不就得了，好了廢話少說，雖然代碼已經(jīng)很簡單明了了，但我還是簡單說一下思路。

就是在數(shù)組的末尾加一個哨兵，即使不判斷i<n也能確保數(shù)組不越界，加了哨兵之后if語句是必然會break的。

先判斷最后一個元素的值是不是我們要查找的數(shù)，如果是，返回其下標；如果不是，將最后一個數(shù)的值保存起來，將要查找的那個數(shù)賦給最后一個元素，循環(huán)查找指定的元素，不用判斷數(shù)組越界，if語句必然break，將最后一個元素的值還原，最后只用判斷i<n，如果是i即為所求，否則要查找的元素不在數(shù)組中。

最后在做一個簡單的性能測試，看到底能否提高查找速度。

測試代碼如下：

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; 
}

運行結(jié)果如下：