服务行业网站建设/搜索引擎优化的基本原理

海量数据求top k

问题：

- 求最大的前k个元素、求最小的前k个元素
- 求最大的第k个元素、求最小的第k个元素

解法：

- 大根堆、小跟堆 -》 优先级队列（priority_queue）
- 快速分割函数

priority_queue<int,vector<int>,greater<int>> //小根堆 priority_queue<int>//默认是大根堆

大根堆和小跟堆的方法

大根堆（堆顶是最大值） -》top 前k小的

小根堆 （堆顶是最小值）-》 top 前k大的

例如：10000个整数，找前10大的元素。

解决思路：

先用前十个整数创建一个小跟堆，最小值在堆顶，遍历剩下的整数，如果整数比堆顶元素大，删除堆顶元素，然后把整数入堆。遍历完所有整数，小跟堆里放的就是值最大的前十个元素。

例如：10000个整数，找第10小的元素。

只需要访问堆顶一个元素就可以了。用大根堆，堆顶放的就是第十大的。

如果是用小跟堆找到了前十大的元素，那么堆顶元素就是第十小的。

如果用快排分割的办法。

快速分割一趟排序就只需要log2N，对数时间就可能会实现。

能够在O（log2N）时间内，把小于基准数的整数调整在左边，大于的调整在右面，基准数（index）就可以认为是第index+1小的整数，[0，index]就是前index+1小的整数了。

#include<iostream>
#include<vector>
using namespace std;
int partation(vector<int>&arr,int i,int j) {int k = arr[i];while (i < j) {while (i < j && arr[j] >= k) j--;if (i < j)arr[i++] = arr[j];while (i < j && arr[i] < k)i++;if (i < j)arr[j--] = arr[i];}arr[i] = k;return i;
}
int selectNok(vector<int>&arr,int i,int j,int k) {int pos = partation(arr, i, j);if (pos == k - 1) return pos;else if(pos<k-1)    return selectNok(arr, pos+1,j,k);else return selectNok(arr, i, pos - 1, k);
}
int main() {/*求容器中前10小的元素*/vector<int> vec;for (int i = 0; i < 10000; ++i) {vec.push_back(rand()+i);}int pos=selectNok(vec,0,vec.size()-1,10);cout << vec[pos] << endl;//第十小的//前十小的,[0,pos]return 0;
}

海量数据查重

1.哈希表-》增删查都是O(1) -》用空间换时间

2.Bloom Filter布隆过滤器

3.TrieTree字典树(前缀树)

如果是特殊类型字符串可以使用布隆过滤器或前缀树。

基本数据查重思想：

#include<iostream>
#include<unordered_map>
using namespace std;int main() {/*在N的数据量中，谁重复了，重复的次数？
*/const int N = 10000;int arr[N] = { 0 };for (int i = 0; i < N; ++i) {arr[i] = rand();}//栈上的map非常小,支持不了上万数据查重unordered_map<int, int> map;//key存数据本身，value存出现的次数for (int it : arr) {map[it]++;}for (auto pair : map) {if (pair.second > 1) {cout << "数字:" << pair.first << "重复次数" << pair.second << endl;}}return 0;
}

考虑到内存的限制

有一个文件，有50亿个整数，内存限制400M，找出文件中重复的元素、次数

回答：使用分治思想，把大文件划分为小文件，使每一个小文件可以加载到内存中，求出对应重复元素，把结果写入一个存储重复元素的文件中

- 1.用大文件的内存除以小文件的内存（内存限制）求出小文件的个数。
- 2.遍历大文件的元素，把每个元素根据哈希映射函数，放到对应序号的小文件，data % 127=file_index
- 3.值相同的，通过一样的哈希映射函数，一定放在同一小文件中。

考虑到多个文件的内存限制

a,b两个文件都有十亿个整数，内存限制400M，求出a，b两个文件当中重复元素有哪些？

10亿-》1G*4=4G*2=8G,8G/400M=27个小文件

- 1.把a和b两个大文件划分为个数相等(27个)的小文件
- 2.从a文件中读取数据，通过数据 % 文件个数=file_index
- 3.从b文件中读取数据，通过数据 % 文件个数=file_index
- 4.a和b文件中，数据相同的元素进行哈希映射以后，肯定在相同序号里的小文件。
- 5.然后处理a1和b1....ax和bx等小文件在内存中，通过unorderde_map查重

海量数据的重复次数最大/小的前K个/第K个

综合使用：哈希表统计重复+根堆/快排

首先对于哈希表(unordered_map)的统计，如果这个val不存在，就插入一个【val，0】，下次再插入存在相同的val时，val++，变成【val，1】，以此类推，可以统计出重复的数据和重复的次数。

然后选择用大根堆或小根堆，再或者是快排找出前k个或第k个。

/如果是前X大的话，使用小跟堆
using P=pair<int,int>;//数据本身和重复次数
using Func=function<bool(P&,P&)>;//定义函数对象
using MinHeap=priority_queue<P,vector<P>,Func>;//参三书写比较规则
MinHeap minheap([](auto &a,auto &b)->bool{return a.second > b.second;//比较重复次数
});
int k=0;
auto it=numMap.begin();
//从map表中读取10个元素到小跟堆中，建立top 10小根堆，最小的元素在堆顶
for(;i!=numMap.end() && k<10 ; ++it , ++k){minheap.push_back(*it);
}
//把K+1到末尾的元素进行遍历，和堆顶元素进行比较。
for(;it!=numMap.end();++it){if(it->second > minheap.top().second()){minheap.pop();minheap.push_back(*it);}
}
//输出
while(!minheap.empty()){auto &pair=minheap.top();cout<<pair.first<<":"<<pair.second<<endl;minheap.pop();
}