Distinct Count的Bitmap怎么做排序

共计 2699 个字符，预计需要花费 7 分钟才能阅读完成。

本篇内容主要讲解“Distinct Count 的 Bitmap 怎么做排序”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让丸趣 TV 小编来带大家学习“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 怎么做排序”有了更深的了解，不妨来实际操作一番吧！这里是丸趣 TV 网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！