一个提高查找速度的小技巧

huojia2120 7年前
   <pre>  //在一个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;  }  </pre>    <p>虽然每次都是写出这样的代码,但我总觉得for循环中的,昨天晚上看编程珠玑的时候发现了这个小技巧,今天就来分享一下。</p>    <p>通过哨兵的方式去掉这多余的判断,将上面两个方法改造如下:</p>    <pre>  //在一个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;   }  </pre>    <p>我勒个去,怎么变得这么长,但的确是减少了判断的次数,如果数组较大的话提高运行速度肯定是一定的,如果你非要说数组很小的话,说不定速度还要降低呢,那你不这样写不就得了,好了废话少说,虽然代码已经很简单明了了,但我还是简单说一下思路。</p>    <p>就是在数组的末尾加一个哨兵,即使不判断i也能确保数组不越界,加了哨兵之后if语句是必然会break的。</p>    <p>先判断最后一个元素的值是不是我们要查找的数,如果是,返回其下标;如果不是,将最后一个数的值保存起来,将要查找的那个数赋给最后一个元素,循环查找指定的元素,不用判断数组越界,if <strong>语句必然break</strong> ,将最后一个元素的值还原,最后只用判断i <strong>,如果是i</strong> <strong>即为所求,否则要查找的元素不在数组中。</strong></p>    <p>最后在做一个简单的性能测试,看到底能否提高查找速度。</p>    <p>测试代码如下:</p>    <pre>  void testFind()  {      int N = 200000;      int* A = new int[N];      A[N-2] = 1;          DWORDstart = ::GetTickCount64();      for( int i = 0; i < 10000; i++ )           find(A,N,1);      DWORDend = ::GetTickCount64();      cout <<"优化前:" << end - start <<" 毫秒" << endl;          start = ::GetTickCount64();       for( int i = 0; i < 10000; i++ )           find1(A,N,1);      end = ::GetTickCount64();      cout <<"优化后:" << end - start <<" 毫秒" << endl;   }  </pre>    <p>运行结果如下:</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/13580171fb8a9ca18f19db58e9dfc944.png"></p>    <p>速度还是会快一点</p>    <p> </p>    <p>来自:http://blog.jobbole.com/109729/</p>    <p> </p>