赞
踩
在文件中产生10 0000个随机数字,数字的取值范围0~32767,按如下要求实现,在实现过程中能够使用的数组最长为10000,个别变量的内存忽略
- 找到重复次数最多的那个数字(如果有多个,选择任意一个)
- 找到重复次数最多的前100个
第一问:找到重复次数最多的那个数字(如果有多个,选择任意一个)
第二问:找到重复次数最多的前100个
#define MAX_NUM 100000 //十万个随机数字
#define ITEM_NUM 10000 //计数器大小为1万
typedef struct Pair //定义数对
{
int num;//数字
int times; //次数
};
void CreateBigFile(const char* path)//产生MAX_NUM个随机数字
{
FILE *fw = fopen(path, "wb");
assert(fw != NULL);
int tmp;
for (int i = 0; i < MAX_NUM; i++)
{
tmp = rand();
fwrite(&tmp, sizeof(int), 1, fw);
}
fclose(fw);
}
辅助函数:显示path路径文件里边的数字
void Show(const char *path)//显示path文件含有的数字
{
FILE *fr = fopen(path, "rb");
assert(fr != NULL);
int tmp;
int i = 0;
while (fread(&tmp, sizeof(int), 1, fr) > 0)
{
printf("%d ", tmp);
i++;
if (i % 10 == 0) printf("\n");
}
fclose(fr);
}
Pair HashFile(const char * path) { int *arr = (int *)calloc(ITEM_NUM, sizeof(int)); FILE *fr = fopen(path, "rb"); assert(arr != NULL && fr != NULL); int tmp; //统计hash文件中每个数字出现的次数 //文件0:0,4,8->0,1,2 文件1:1,5,9->0,1,2 文件2:2,6,10->0,1,2 文件3:3,7,11->0,1,2 哈希函数y=x/4 while (fread(&tmp, sizeof(int), 1, fr) > 0)//(0,1,2,3)->0,即四个文件中最小的数字对应的计数器下标都是0 { arr[tmp / 4]++;//hash函数 y = x/4 } //找到次数最多的数字及次数 Pair pa = { 0 }; for (int i = 0; i < ITEM_NUM; i++) { if (pa.times < arr[i]) { pa.num = i * 4 + tmp % 4; //反推:0->(0,1,2,3),i*4加该文件数字对4的余数 pa.times = arr[i]; } } fclose(fr); free(arr); return pa; }
Pair MaxTimes(const char * path) { FILE *fr = fopen(path, "rb"); int tmp; //生成四个不同的文件名 char pathArr[4][20];//四个文件名,0.txt 1.txt 2.txt 3.txt for (int i = 0; i < 4; i++)//批量生成文件名 { sprintf(pathArr[i], "%d.txt", i); } //定义四个hash文件并打开 FILE *fw[4]; for (int i = 0; i < 4; i++) { fw[i] = fopen(pathArr[i], "wb"); } //将原来的数据散列到四个hash文件中 while (fread(&tmp, sizeof(int), 1, fr) > 0) { fwrite(&tmp, sizeof(int), 1, fw[tmp % 4]); } for (int i = 0; i < 4; i++) { fclose(fw[i]); } //统计每个hash文件中出现次数最多的数字 Pair paArr[4]; for (int i = 0; i < 4; i++) { paArr[i] = HashFile(pathArr[i]); } //找到四个里面次数最大的 int index = 0;//保存次数最多的数据下标 for (int i = 0; i < 4; i++) { if (paArr[index].times < paArr[i].times) { index = i; } } return paArr[index]; }
int main()
{
const char*path = "big.txt";
CreateBigFile(path);
Pair pa = MaxTimes(path);
printf("十万个数据中重复次数最多的是:\n\n 数字=%d,次数=%d\n\n", pa.num, pa.times);
//Show(path);
}
注意:由于哈希,数字存放的位置和数字本身有映射关系,而排序的交换会破坏这种关系,所以数字本身和它的次数都得保存起来,因而计数器数组元素类型要改成结构体Pair类型
//统计hash文件中出现次数最多的前100个数字,计数器限制为ITEM_NUM Pair *HashFile2(const char *path) { //arr 为ITEM_NUM长的int型数组,计数器 注意:数字存放的位置和数字本身有关系 //将arr改为元素类型为Pair的数组 FILE *fr = fopen(path, "rb"); Pair *arr = (Pair*)calloc(ITEM_NUM , sizeof(Pair)); assert(fr != NULL && arr!=NULL); int tmp; //统计hash文件中每个数字出现的次数 //文件0:0,4,8->0,1,2 文件1:1,5,9->0,1,2 文件2:2,6,10->0,1,2 文件3:3,7,11->0,1,2 哈希函数y=x/4 while (fread(&tmp, sizeof(int), 1, fr) > 0)//(0,1,2,3)->0,即四个文件中最小的数字对应的计数器下标都是0 { arr[tmp / 4].num = tmp; arr[tmp / 4].times++;//hash函数 y = x/4 } //对arr数组按times递减排序, 排序选用堆排序,只需要得到前100个 HeapSort(arr, ITEM_NUM); fclose(fr); return arr; }
//在筛出的400个数据里找次数前100的 Pair * MaxTimes2(const char* path) { FILE *fr = fopen(path, "rb"); int tmp; //生成四个不同的文件名 char pathArr[4][20];//四个文件名,0.txt 1.txt 2.txt 3.txt for (int i = 0; i < 4; i++)//批量生成文件名 { sprintf(pathArr[i], "%d.txt", i); } //定义四个hash文件并打开 FILE *fw[4]; for (int i = 0; i < 4; i++) { fw[i] = fopen(pathArr[i], "wb"); } //将原来的数据散列到四个hash文件中 while (fread(&tmp, sizeof(int), 1, fr) > 0) { fwrite(&tmp, sizeof(int), 1, fw[tmp % 4]); } for (int i = 0; i < 4; i++) { fclose(fw[i]); } //统计每个hash文件中出现次数的前100----------- Pair *arr[4]; for (int i = 0; i < 4; i++) { arr[i] = HashFile2(pathArr[i]); } //400个里面找前100, 先把400个数对汇总到一起 Pair *fourHundred = (Pair*)malloc(sizeof(Pair) * 400); int index = 0; for (int i = 0; i < 4; i++) { for (int j = 0; j < 100; j++) { fourHundred[index++] = arr[i][j]; } } //汇总的400个数据进行递减式堆排 HeapSort(fourHundred, 400); return fourHundred; }
/// 递减式堆排序 // //一次堆调整 void HeapAdjust(Pair *arr, int start, int end)//start起始下标,end结尾下标,O(logn),O(1) { Pair tmp = arr[start]; int parent = start;//标记父节点下标 for (int i = 2 * start + 1; i <= end; i = 2 * i + 1)//i下一次要到它的左孩子 { //找左右孩子的较大值 if (i + 1 <= end && arr[i].times > arr[i + 1].times) { i++; }//i变为左右孩子较大值的下标 if (arr[i].times < tmp.times) { //arr[(i - 1) / 2] = arr[i];//放到i的父节点 arr[parent] = arr[i]; } else { break; } parent = i;//更新下一次i的父节点 } arr[parent] = tmp; } void HeapSort(Pair *arr, int len)//O(nlogn),O(1),不稳定(父子相互交换数据,父子下标是跳跃式的) { //建立大根堆,O(nlogn) for (int i = (len - 1 - 1) / 2; i >= 0; i--)//len-1最后一个的下标,再减一除以二是它的父节点下标,从后往前多次调整 { HeapAdjust(arr, i, len - 1);//每一个i都遍历到len-1作为end,因为即使有的没有len-1这个子节点,也不影响, } //每次将根和待排序最后的值交换,然后再调整,O(nlogn) Pair tmp; for (int i = 0; i < len - 1; i++) { tmp = arr[0]; arr[0] = arr[len - 1 - i]; arr[len - 1 - i] = tmp; HeapAdjust(arr, 0, len - 2 - i); } }
int main() { const char*path = "big.txt"; CreateBigFile(path); //第一问 Pair pa = MaxTimes(path); printf("十万个数据中重复次数最多的是:\n\n 数字=%d,次数=%d\n\n", pa.num, pa.times); //Show(path); //第二问 Pair *pa2 = MaxTimes2(path); printf("重复数字最多的前100个:\n\n"); for (int i = 0; i < 100; i++) { printf("(%d %d) ", pa2[i].num, pa2[i].times); if (i % 10 == 0) printf("\n"); } }
对于上述问题,其实主要就干了三件事
对于处理类似数据多而可用内存少的大数据问题,核心思想就是先哈希, 再堆排
海量数据处理,就是基于海量数据上的存储、处理、操作。海量数据问题,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。
算法思想:分而治之+Hash
假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
基本思想:哈希+堆排
即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N’*O(logK),(N为1000万,N’为300万)
基本思想:哈希+堆排+归并
大数据问题的处理:哈希+堆排
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。