优化遍历查询语句（编程珠玑）

本文主要是介绍优化遍历查询语句（编程珠玑），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://blog.jobbole.com/109729/?utm_source=tuicool&utm_medium=referral

在一个数组中查找某一个元素，或是在一个字符串中查找某个字符，我们一般都会写出如下代码。这样的代码虽然简洁明了，但在数组元素很多的情况下，并不是一个很好的解决方案，今天我就来分享一个提高查找速度的小技巧.

 
 
 
 
 
  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
 //在一个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循环中的，昨天晚上看编程珠玑的时候发现了这个小技巧，今天就来分享一下。

通过哨兵的方式去掉这多余的判断，将上面两个方法改造如下：

  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
 //在一个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也能确保数组不越界，加了哨兵之后if语句是必然会break的。

先判断最后一个元素的值是不是我们要查找的数，如果是，返回其下标；如果不是，将最后一个数的值保存起来，将要查找的那个数赋给最后一个元素，循环查找指定的元素，不用判断数组越界，if语句必然break，将最后一个元素的值还原，最后只用判断i，如果是i即为所求，否则要查找的元素不在数组中。

最后在做一个简单的性能测试，看到底能否提高查找速度。

测试代码如下：

 
 
 
 
 
  
 1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
 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 ;   
 } 
 