C/C++中提高查找速度的小技巧
2019/7/10 22:50:58
本文主要是介绍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; }
运行结果如下:
速度还是会快一点
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。
这篇关于C/C++中提高查找速度的小技巧的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-25Elevate Your Lead Generation Game with Maps Scraper AI
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能