设计网站栏目,企业公示信息查询系统浙江,wordpress 聊天,网页界面设计想法1. 查找的概念
在一堆数据中#xff0c;找到我们想要的那个数据#xff0c;就是查找#xff0c;也称为搜索#xff0c;很容易想到#xff0c;查找算法的优劣#xff0c;取决于两个因素#xff1a;
数据本身存储的特点查找算法本身的特点
比如#xff0c;如果数据存储…1. 查找的概念
在一堆数据中找到我们想要的那个数据就是查找也称为搜索很容易想到查找算法的优劣取决于两个因素
数据本身存储的特点查找算法本身的特点
比如如果数据存储是无序的那么当我们想要在其中找到某个节点时一般就只能对它们逐个比对。如果数据存储是有序且存放在一片连续的内存中那么我们可以考虑从中间开始找二分法。因此可以看到在实际应用中如果需要优化数据的查找搜索性能我们主要从以上两方面入手当然有时数据的存储特性是无法更改的那么此时就只能靠优化算法本身去达到提供程序性能的目的了。
2. 经典查找算法
2.1 顺序查找
顺序查找顾名思义就是挨个找这是一种不是算法的“算法”最没办法的“办法”简单直接童叟无欺。时间复杂度就是 O(n)
适用情况
无序的数据无法或不便于对这些数据进行有效的整理
以下是示例代码
// 数据规模100万
#define SCALE 1000*1000// 查找次数统计
static int count;int sequentialSearch(unsigned data[], int len, int n)
{for(int i0; iSCALE; i){if(data[i] n)return i;count;}return -1;
}int main(int argc, char const *argv[])
{// 产生一系列无序数据srand(time(NULL));unsigned *data calloc(SCALE, sizeof(unsigned));for(int i0; iSCALE; i)data[i] rand()%((int)pow(10, rand()%85));// 不进行任何数据整理直接进行顺序查找unsigned n;printf(请输入你要找的正整数\n);while(1){scanf(%u, n);int pos sequentialSearch(data, SCALE, n);if(pos -1)printf(找不到你要的数据);elseprintf(你要找的数据第%d行, pos);printf(【找了%d次】\n, count);count 0;}return 0;
}以下是执行效果
gecubuntu: ~$ ./sequential_search
请输入你要找的正整数
132096806
你要找的数据第87行【找了87次】
951578948
你要找的数据第999999行【找了999999次】
951578949
找不到你要的数据【找了1000000次】很显然除非数据完全无序且无法整理否则顺序查找的效率在大规模数据面前是非常低下的因此一般情况下对于大数据量的查找我们都会尽量先对数据进行不同程度的整理。
2.2 分块查找
在一本字典中查找某个汉字的时候一般是先找目录在目录中找到对应拼音或笔画然后直接翻到对应的页面再往下找很显然这能大大提高查找的效率。
分块查找实质就是给数据建立索引将查找的过程分成两个步骤
在索引目录中找到数据所属分块在所属分块中查找到该数据
以下例子中先是产生系列长度和内容都随机的字符串作为待查数据集。然后对这些字符串按首字符进行整理形成字母表索引目录。最后利用索引提高查找效率。
核心代码示例
// 数据规模: 100万
#define SCALE 1000*1000 // 字符串总数
#define MAXLEN 20 // 字符串最大长度// 查找次数统计
static int count;char *random_string()
{int len rand()%(MAXLEN);len ((len2)? 2 : len); // len: 2~19char *s calloc(1, len);char letter[] {a, A};for(int i0; ilen-1; i) // i: 0~[1~18]s[i] letter[rand()%2]rand()%26;return s;
}void create_index(char data[][MAXLEN], int **index)
{// 统计各个首字符出现的频次int n[52]{0}; // [a, b, ... z, A, B, ... Z]for (int k 0; k SCALE; k){// 小写字母[00~25]大写字母[26~51]int pos ((data[k][0] a) ? (data[k][0]-a) : (data[k][0]-A26));n[pos];}// 给index分配内存// 每个字母分配一段存储以该字母为首的字符串所在的行号的内存// 第一个位置存储总行数因此所需分配的内存单元数是1n[i]。// 例如:// index[2] -- [ 242 3 22 213 ... ... 42513 46698]// c -- 总行数 第3行 第22行 ... ...for(int i0; i52; i)index[i] calloc(1n[i], sizeof(int));// 记录每个字母出现的行号for(int i0; iSCALE; i){int pos ((data[i][0] a) ? (data[i][0]-a) : (data[i][0]-A26));int k index[pos][0];index[pos][k] i;}
}int main(int argc, char const *argv[])
{// 1. 产生随机字符串数据集// 假设每个字符串长度不超过MAXLEN个字符char (*data)[MAXLEN] calloc(SCALE, MAXLEN);srand(time(NULL));for(int i0; iSCALE; i){char *s random_string();strncpy(data[i], s, strlen(s));free(s);}// 2. 按首字母建立索引分块int **index calloc(52, sizeof(int *));create_index(data, index);// 3. 利用索引进行查找char str[32];printf(请输入你要查找的字符串:\n);while(1){// 从键盘接收一个待查找的字符串并去掉回车符bzero(str, 32);fgets(str, 32, stdin);strtok(str, \n);bool done false;for(int i1; iSCALE; i){// 小写字母[00~25]大写字母[26~51]int pos ((str[0]a) ? (str[0]-a) : (str[0]-A26));count;if(iindex[pos][0] strcmp(data[index[pos][i]], str) 0){printf(你要找的字符串在第%d行, index[pos][i]);done true;break;}else if(i index[pos][0])break;}if(!done)printf(没有你要的字符串);printf(【找了%d次】\n, count);count0;}return 0;
}以下是执行效果
gecubuntu: ~$ ./index_search
请输入你要查找的字符串:
e
你要找的字符串在第8行【找了1次】
sdf
你要找的字符串在第206096行【找了4078次】
ssHcbSJC
你要找的字符串在第396828行【找了7891次】由于对数据进行了分块引入了索引查找效率大大提高对于上述的100万个数据来说假设以各个大小写字母开头的字符串概率相等那么相当于将整体数据分成了52块整体效率平局提升52倍这个性能的提升的相当显著的所付出的代价是需要额外的内存空间存储索引表index这是以空间换时间的经典思路。
2.3 二分查找
分块查找是在不对数据进行排序的情况下采用的颇为有效的查找办法但如果待查找的数据本身是有序的或者在查找前可以对数据先进行排序比如数据量虽然较大但短期较稳定无大面积更新这种情况下使用二分查找可以进一步提升效率。
二分法的思路相当朴实无华从中间开始找。既然数据是有序的那么如果将待查找的节点跟中间节点对比就可以以排除掉一半的数据接着再在剩余的数据的中间开始找又可以很快排除掉剩下的一半的数据这种一半一半筛查数据的办法就是所谓的二分法。
例如下图想要在一系列有序从小到大的数据中查找45中间的节点数据是22很显然左侧数据可以立即排除45只可能存在于22右侧的序列中若有 二分查找算法示意图
假设有一系列有序数据以下是二分查找算法的核心代码
// 数据规模: 100万
#define SCALE 1000*1000// 查找次数统计
static int count;int main(int argc, char const *argv[])
{// 1. 产生SCALE个随机整数序列unsigned *data calloc(SCALE, sizeof(unsigned));srand(time(NULL));for(int i0; iSCALE; i)data[i] rand()%((int)pow(10, rand()%85));// 2. 排序quick_sort(data, SCALE);// 3. 进行二分查找unsigned n;printf(请输入你要查找的正整数:\n);while(1){scanf(%u, n);int low, high, mid;low 0, high SCALE-1;bool found false;while(low high){count;mid (lowhigh)/2;if(n data[mid]){printf(你要找的数据在第%d行, mid);found true;break;}if(n data[mid])high mid - 1;elselow mid 1;} if(!found)printf(找不到你要的数据);printf(【找了%d次】\n, count);count0;}return 0;
}以下是执行效果
gecubuntu: ~$ ./binary_search
请输入你要查找的正整数:
1
你要找的数据在第6行【找了17次】
534
你要找的数据在第731行【找了12次】
6996
你要找的数据在第9534行【找了16次】
5863827
你要找的数据在第333334行【找了20次】可见二分查找的查找效率得到了质的飞跃在最不利的情况下100万个数据最多仅需查找20次就能锁定结果这个效率大大优于顺序查找和分块查找。但别忘记适合于用二分查找的场合是有条件的数据是严格有序的。
