- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
大数据处理算法
大数据处理算法一:Bitmap算法 2
大数据处理算法二:Bloom Filter算法 5
大数据处理算法三:分而治之/hash映射 + hash统计 + 堆/快速/归并排序 11
标签:算法,大数据,编程,面试题,腾讯大数据处理算法一:Bitmap算法
解析:bitmap算法就好办多了
所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。
例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示。那么就可以开一个int数组,一个int有32个位,就可以表示32个人。操作的时候可以使用位操作。
一,申请512M的内存
一个bit位代表一个unsigned int值
读入20亿个数,设置相应的bit位
读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在
二、使用位图法判断整形数组是否存在重复
判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。
位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到 5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
import java.util.BitSet;
/**
* 大数据处理算法一,bitmap算法
* @author JYC506
*
*/
public class Bitmap {
byte[] tem;
public Bitmap(int length) {
this.tem = new byte[length];
}
public void add(int num) {
if (num tem.length) {
if (tem[num] != 1) {
tem[num] = 1;
}
}
}
public boolean contain(int num) {
if (num tem.length) {
if (tem[num] == 1) {
return true;
}
}
return false;
}
public static void main(String[] args) {
/*运行前内存*/
long beforeMemory = Runtime.getRuntime().totalMemory();
long start1=System.currentTimeMillis();
BitSet set = new BitSet(2000000000);
for (int i = 0; i 2000000000; i++) {
/*假设898989这个数不在20亿个数里面*/
if (i != 898989) {
set.set(i, true);
}
}
/*创建20亿个数后所占内存*/
long afterMemory = Runtime.getRuntime().totalMemory();
long end1=System.currentTimeMillis();
System.out.println(总共内存使用: + (afterMemory - beforeMemory) / 1024 / 1024 + MB);
System.out.println(存入内存耗时:+(end1-start1)+毫秒);
long start2 = System.currentTimeMillis();
boolean isExit1=set.get(898989);
boolean isExit2=set.get(900000);
long end2 = System.currentTimeMillis();
/*输出在20亿个数中判断898989是否包含在里面*/
System.out.println(isExit1);
System.out.println(20个亿中+(isExit1?包含:不包含)+898989);
System.out.println(20个亿中+(isExit2?包含:不包含)+900000);
System.out.println(查询用时:+(e
文档评论(0)