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

运行结果如下：

速度还是会快一点

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。