内容简介：在一个数组中查找某一个元素，或是在一个字符串中查找某个字符，我们一般用的代码虽然简洁明了，但在数组元素很多的情况下，并不是一个很好的解决方案，今天我就来分享一个提高查找速度的小技巧.
在一个数组中查找某一个元素，或是在一个字符串中查找某个字符，我们一般都会写出如下代码。这样的代码虽然简洁明了，但在数组元素很多的情况下，并不是一个很好的解决方案，今天我就来分享一个提高查找速度的小技巧.
|
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; } |
运行结果如下：
速度还是会快一点
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- PHP有序表查找之二分查找（折半查找）算法示例
- 查找--插值查找（Java）
- 查找算法（一）：查找
- 二叉查找树（查找、插入、删除）——C语言
- 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
- 七大查找算法
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
A=B
Marko Petkovsek、Herbert S. Wilf、Doron Zeilberger / AK Peters, Ltd. / 1996-01 / USD 49.00
At some point, this book describes methods of solving the problem raised by Donald E. Knuth in the classical book "The Art of Computer Programming, Volume 1: Fundamental Algorithms". The main purpo......一起来看看 《A=B》 这本书的介绍吧!
