DistinctCount的Bitmap怎么做排序
本篇内容主要讲解“Distinct Count的Bitmap怎么做排序”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Distinct Count的Bitmap怎么做排序”吧!
目前创新互联已为上千多家的企业提供了网站建设、域名、虚拟空间、绵阳服务器托管、企业网站设计、网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。我们拥有完善的网络基础设施服务,能够为企业或个人提供空间域名、虚拟空间、企业邮局、网站加速、数据库、云主机等网络基础服务。
大数据(big data),IT行业术语,是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。 |
1. Bitmap介绍
Bitmap是一个十分有用的数据结构。所谓的Bitmap就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此在内存占用方面,可以大大节省。
简而言之——用一个bit(0或1)表示某元素是否出现过,其在bitmap的位置对应于其index。
用bitmap做排序的例子:
/* Copyright (C) 1999 Lucent Technologies */ /* From 'Programming Pearls' by Jon Bentley */ /* bitsort.c -- bitmap sort from Column 1 * Sort distinct integers in the range [0..N-1] */ #include#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N / BITSPERWORD]; void set(int i) { a[i >> SHIFT] |= (1 << (i & MASK)); } void clr(int i) { a[i >> SHIFT] &= ~(1 << (i & MASK)); } int test(int i) { return a[i >> SHIFT] & (1 << (i & MASK)); } int main() { int i; for (i = 0; i < N; i++) clr(i); /* Replace above 2 lines with below 3 for word-parallel init int top = 1 + N/BITSPERWORD; for (i = 0; i < top; i++) a[i] = 0; */ while (scanf("%d", &i) != EOF) set(i); for (i = 0; i < N; i++) if (test(i)) printf("%d\n", i); return 0; }
上面代码中,用int的数组存储bitmap,对于每一个待排序的int数,其对应的index为其int值。
2. Distinct Count优化
index生成
为了使用bitmap做Distinct Count,首先需得到每个用户(uid)对应(在bitmap中)的index。有两种办法可以得到从1开始编号index表(与uid一一对应):
hash,但是要找到无碰撞且hash值均匀分布[1, +∞)区间的hash函数是非常困难的;
维护一张uid与index之间的映射表,并增量更新
比较两种方法,第二种方法更为简单可行。
UV计算
在index生成完成后,RDD[(uid, V)]与RDD[(uid, index)]join得到index化的RDD。bitmap的开源实现有EWAH,采用RLE(Run Length Encoding)压缩,很好地解决了存储空间的浪费。Distinct Count计算转变成了求bitmap中1的个数:
// distinct count for rdd(not pair) and the rdd must be sorted in each partition def distinctCount(rdd: RDD[Int]): Int = { val bitmap = rdd.aggregate[EWAHCompressedBitmap](new EWAHCompressedBitmap())( (u: EWAHCompressedBitmap, v: Int) => { u.set(v) u }, (u1: EWAHCompressedBitmap, u2: EWAHCompressedBitmap) => u1.or(u2) ) bitmap.cardinality() } // the tuple_2 is the index def groupCount[K: ClassTag](rdd: RDD[(K, Int)]): RDD[(K, Int)] = { val grouped: RDD[(K, EWAHCompressedBitmap)] = rdd.combineByKey[EWAHCompressedBitmap]( (v: Int) => EWAHCompressedBitmap.bitmapOf(v), (c: EWAHCompressedBitmap, v: Int) => { c.set(v) c }, (c1: EWAHCompressedBitmap, c2: EWAHCompressedBitmap) => c1.or(c2)) grouped.map(t => (t._1, t._2.cardinality())) }
但是,在上述计算中,由于EWAHCompressedBitmap的set方法要求int值是升序的,也就是说RDD的每一个partition的index应是升序排列:
// sort pair RDD by value def sortPairRDD[K](rdd: RDD[(K, Int)]): RDD[(K, Int)] = { rdd.mapPartitions(iter => { iter.toArray.sortWith((x, y) => x._2.compare(y._2) < 0).iterator }) }
为了避免排序,可以为每一个uid生成一个bitmap,然后在Distinct Count时将bitmap进行or运算亦可:
rdd.reduceByKey(_ or _) .mapValues(_._2.cardinality())
到此,相信大家对“Distinct Count的Bitmap怎么做排序”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
本文名称:DistinctCount的Bitmap怎么做排序
文章源于:http://scyanting.com/article/jgppis.html