始兴县建设局网站,电商平台如何做推广,网站商城建设视频教程,电子商务网站推广论文有一个无符号整数的文件#xff0c;数据个数有40亿个#xff0c;如何通过1G的内存返回出现次数最多的数
1. 对每个数调用哈希函数得到哈希值#xff0c;将哈希值模上100#xff0c;进行小文件分类#xff08;相同的数一定在同一文件#xff09;
2. 将每个小文件内出现次…有一个无符号整数的文件数据个数有40亿个如何通过1G的内存返回出现次数最多的数
1. 对每个数调用哈希函数得到哈希值将哈希值模上100进行小文件分类相同的数一定在同一文件
2. 将每个小文件内出现次数最大的数进行比较即可 布隆过滤器
目前有100亿个URL需要通过黑名单来禁止访问每个URL 64Byte只需要添查操作。
使用布隆过滤器可以在很少空间内实现但存在一定的失误率不可避免错将不在黑名单的URL认为在黑名单内。—— 宁错杀不放过
1. 使用整形数组来进行bitmap表示
2. 建立一个长度为m的bitmap实际占用空间m/8 Byte
3. 添加黑名单将URL通过哈希函数得到输出值%m将该位设为1再通过另一个哈希函数同样处理一共使用k个哈希函数
4. 查找时通过同样的k个哈希函数只有全是1时判断该URL在黑名单内有一个不是1那么该URL不在黑名单内
提高m会降低失误率但随着m的逐渐增大失误率的降低越来越慢。k与失误率的关系为一个对勾函数。
n(样本量)p(失误率)
单样本的大小和布隆过滤器无关。
m(n*lnp)/(ln2)^2
kln2*m/n0.7*m/n
p(1-e(-n*k/m))^k
两个参数都向上取整即可
哈希一致性
用于讨论数据服务器组织的问题降低数据迁移的成本。
将哈希值的返回域想象成环假设有三台机器m1,m2,m3。 添加的时候只需要将某个输入对应的哈希值顺时针放到最近的服务器内即可
增加服务器将m4与其逆时针最近服务器中间的数给到m4即可
删除服务器数据全部给到顺时针最近的服务器内
存在的问题 1. 机器数量少时做不到分布均衡 2. 增加或删除机器时会导致负载不均衡
使用虚拟节点解决m1有一千个代表点m2有一千个代表点m3有一千个代表点使用代表点来进行抢环。
位图解决某一范围上数字出现节省大量空间 使用一个整形数组来表示所有范围内的数是否出现。 可以使用哈希函数分流进行实现同样使用位图来实现但1/0只能表示数字是否出现过所以需要使用两个位来表示一个数字出现的信息。 利用分段统计思想节省空间 假设3KB申请长度512的整形数组将题目中的这个范围分为512份则每一份都是等量的8388608。每一个数组表示该范围内的数出现了多少次统计范围内词频一定会有一个数小于8388608在该范围上继续分循环往复下去。 利用范围统计的思想 申请一个无符号整型数组做词频统计然后从左到右对整型数组求词频和第一次超过20亿时最近加入的数组里一定包含所要求的中位数周而复始即可。 利用堆、外排序来做多个处理单元的结果合并
10G文件每个文件是一个无符号整数使用5G内存使其文件输出有序
使用小根堆小根堆里的数据是一个结构体结构体包括数字及其出现的次数小根堆根据数值组织则5G内存肯定能支持一个2^28N条数据的小根堆将整数的数值范围除N等分为M个范围首先对第一个范围的数排序输出依次下去即可。
