共計 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 網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
