位图排序(位图技术应用)
1. 问题描述
给定不大于整数 n 的 k 个互不相等的整数 ( k <n ) , 对这些整数进行排序。本文讨论的内容具体可参见《编程珠玑》(第二版)的第一章。
2. 问题分析
关于排序,已经有多种排序方法了:插入排序,归并排序,快速排序,希尔排序等。每种排序都有不同的用武之地。为什么需要位图排序呢?所有的内部排序(上述所提及)都必须一次性将所有排序元素载入内存。假如有1000,000个整数,每个整数4字节,则意味着,至少需要4000,000B 约为 4MB 的内存空间, 如果仅仅只有 1MB 的内存空间可用,那么,应该怎么办呢?
很多问题都有通用的求解策略,而在通用之外,常常需要根据问题的实际需求及特征挖掘有针对性的解决方案。这里的特征是,所有整数均不大于 n , 并且整数互不重复。怎么利用这一特征呢?
可以采用位图技术。所谓位图技术,就是将问题映射到位串上,对位串进行处理后,再将位串逆射到问题空间上。具体而言, 假设要对数组 不大于 20 的元素数组 [5, 2, 12, 18, 7, 9, 13, 19, 16, 4, 6] 进行排序, 则可以将其映射到位串 11010011001001110100 ,其中, 1 表示数组元素出现的位置(最高位在后面,最低位在左边,以下标0起头),然后,从低位往高位扫描, 即可得到 { 2, 4, 5, 6, 9, 12,13,16,18,19} 这样就排序好了。根据位图技术, 1000,000 个互不重复的整数数组的排序, 只需要大约 1000,000 b = 0.125MB 内存空间。
3. 详细设计
[ 1 ] 输入: 一个未排序的数组, 数组中的各数互不相等, 都不大于某个整数 n , 且稠密地分布在[0, n-1] 的区间中
[ 2 ] 输出: 一个已排序的数组
[ 3 ] 数据结构: 位向量。 位图排序的关键在于位向量的实现。位向量有“置一”、“清零”、“测试位是否为1”等操作。从实现角度,可以使用一个整型数组来实现(因为在Java中,移位、按位运算都是以整数为基本单位),这意味着,每32位为一组。 位向量长度最好取为 32 的倍数, 以方便编程。 假设有 64位, 那么对第59位置1, 59/32 = 1 , 59 %32 = 27;这意味着,需要对第1组 a[1] 的第 27 位进行置位。 除以32 可使用 右移 5 位 ( i >> 5) 来实现, 对 32 取模, 可以通过 1 << ( i & 0x1f ) 来实现。 剩下的,就是细节问题了,比如,确保边界不出错。位串方向规定为: a[p]a[p-1]...a[1]a[0] , p = N / 32; N 为不小于 n 的 32 倍数的最小整数。 a[p] 为最高位的32位, a[0] 为最低位的32位。
4. 算法描述
STEP1: 根据问题描述确定位向量的位数, 初始化位向量bv;
STEP2: 对于数组的每一个元素,用其数值作为位置,对位向量的相应位置 1;
STEP3: 从低位向高位扫描,对位向量的每一位,若位为1, 则输出该位的位置下标,作为最终排序数组的元素值。
5. Java 代码实现
package datastructure.vector; /** * 实现 n 维位向量 * */ public class NBitsVector { private static final int BITS_PER_INT = 32; private static final int SHIFT = 5; // 将一个整型数组中的所有整数的位串联成一个位向量 private int[] bitsVector; // 位向量的总位数 private int bitsLength; public NBitsVector(int n) { int i = 1; while (i * BITS_PER_INT < n) { i++;} this.bitsLength = i * BITS_PER_INT; if (bitsVector == null) { bitsVector = new int[i]; } } /** * setBit: 将位向量的第 i 位置一 * @param i 要置位的位置 */ public void setBit(int i) { bitsVector[i >> SHIFT] |= 1 << (i & 0x1f); } /** * clrBit: 将位向量的第 i 位清零 * @param i 要清零的位置 */ public void clrBit(int i) { bitsVector[i >> SHIFT] &= ~(1 << (i & 0x1f)); } /** * testBit: 测试位向量的第 i 位是否为 1 * @param i 测试位的位置 * @return 若位向量的第 i 位为 1, 则返回true, 否则返回 false */ public boolean testBit(int i) { return (bitsVector[i >> SHIFT] & 1 << (i & 0x1f)) != 0; } /** * clr: 位向量全部清零 */ public void clr() { int vecLen = bitsVector.length; for (int i = 0; i < vecLen; i++) { bitsVector[i] = 0; } } /** * getBitsLength: 获取位向量的总位数 */ public int getBitsLength() { return bitsLength; } /** * 获取给定整数 i 的二进制表示, 若高位若不为 1 则补零。 * @param i 给定整数 i */ public String intToBinaryStringWithHighZero(int i) { String basicResult = Integer.toBinaryString(i); int bitsForZero = BITS_PER_INT - basicResult.length(); StringBuilder sb = new StringBuilder(""); while (bitsForZero-- > 0) { sb.append(‘0‘); } sb.append(basicResult); return sb.toString(); } public String toString() { StringBuilder sb = new StringBuilder("Bits Vector: "); for (int i = bitsVector.length-1; i >=0 ; i--) { sb.append(intToBinaryStringWithHighZero(bitsVector[i])); sb.append(" "); } return sb.toString(); } public static void main(String[] args) { NBitsVector nbitsVector = new NBitsVector(64); nbitsVector.setBit(2); System.out.println(nbitsVector); nbitsVector.setBit(7); nbitsVector.setBit(18); nbitsVector.setBit(25); nbitsVector.setBit(36); nbitsVector.setBit(49); nbitsVector.setBit(52); nbitsVector.setBit(63); System.out.println(nbitsVector); nbitsVector.clrBit(36); nbitsVector.clrBit(35); System.out.println(nbitsVector); System.out.println("52: " + nbitsVector.testBit(52)); System.out.println("42: " + nbitsVector.testBit(42)); nbitsVector.clr(); System.out.println(nbitsVector); } }
package algorithm.sort; import java.util.Arrays; import datastructure.vector.NBitsVector; /** * 位图排序 * */ public class BitsMapSort { private NBitsVector nBitsVector; public BitsMapSort(int n) { if (nBitsVector == null) { nBitsVector = new NBitsVector(n); } } public int[] sort(int[] arr) throws Exception { if (arr == null || arr.length == 0) { return null; } nBitsVector.clr(); int arrLen = arr.length; for (int i=0; i < arrLen ; i++) { if (arr[i] < 0 || arr[i] > nBitsVector.getBitsLength()-1) { throw new Exception("给定整数 " + arr[i] + " 超过范围,请检查输入"); } if (nBitsVector.testBit(arr[i])) { throw new Exception("存在重复整数: " + arr[i] + " ,请检查输入!"); } nBitsVector.setBit(arr[i]); } int bitsLength = nBitsVector.getBitsLength(); int count = 0; for (int i=0; i < bitsLength; i++) { if (nBitsVector.testBit(i)) { arr[count++] = i; } } return arr; } public static int maxOfArray(int[] arr) { int max = arr[0]; for (int i=1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } public static void test(int[] arr) { try { // 63 可以改为 数组最大值 maxOfArray(arr) BitsMapSort bms = new BitsMapSort(64); System.out.println("排序前: " + Arrays.toString(arr)); int[] sorted = bms.sort(arr); System.out.println("排序后: " + Arrays.toString(sorted)); } catch(Exception e) { System.out.println(e.getMessage()); } } public static void main(String[] args) { int[] empty = null; test(empty); empty = new int[0]; test(empty); int[] unsorted = new int[] { 15, 34, 46, 52, 7, 9, 5, 10, 25, 37, 48, 13}; test(unsorted); int[] unsorted2 = new int[] { 15, 34, 46, 52, 7, 9, 5, 7, 25, 37, 48, 13}; test(unsorted2); int[] unsorted3 = new int[] { 15, 34, 46, 52, 7, 9, 5, 72, 25, 37, 48, 13}; test(unsorted3); } }
6. C 源程序:
/* * bitvec.c : N维位向量的实现 * author: shuqin1984 2011-08-31 */ #include <assert.h> #define N 10000000 #define M ((N%32==0) ? (N/32) : (N/32+1)) #define SHIFT 5 #define mod32(n) ((n) - (((n) >> SHIFT) << SHIFT)) int bitvec[M]; // N维位向量用 M个整数的数组来实现 int test(int i); // 测试位向量的位 i 是否为 1 void set(int i); // 将位向量第 i 位置 1 void clear(int i); // 将位向量第 i 位清零 void clearAll(); // 将位向量所有位清零 void show(); // 显示位向量的当前值 void printb(int x, int i); // 打印正整数 x 的第 i 位二进制 void printbz(int x, int n); // 打印正整数的二进制表示(从低位数起的n位),若位数不够前面补零 int test(int i) { assert(i >= 0); return (bitvec[i>>SHIFT] & (1 << mod32(i))) != 0; } void set(int i) { assert(i >= 0); bitvec[i>>SHIFT] |= (1 << mod32(i)); } void clear(int i) { assert(i >= 0); bitvec[i>>SHIFT] &= ~(1 << mod32(i)); } void clearAll() { int i; for (i = 0; i < M; i++) { bitvec[i] = 0; } } void show() { int i = 0; if (M == 1) { printbz(bitvec[i], N); } else { int bits = (N%32==0)? 32: (N%32); printbz(bitvec[M-1], bits); for (i=M-2; i >=0 ; i--) { printbz(bitvec[i], 32); } } printf("\n"); } void printb(int x, int i) { printf("%c", ‘0‘ + ((((unsigned)x) & (1 << i)) >> i)); } void printbz(int x, int n) { int i; for (i = n-1; i >= 0; i--) { printb(x, i); } }
/* * bitsort.c: 实现位图排序并测量运行时间 * author: shuqin1984 2011-8-31 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #include <assert.h> #include <limits.h> #include "bitvec.c" #define MAX_LEN 10 void bitsort(char* filename); void bitsortf(); void runtime(void (*f)()); void testdata(int, int); int randRange(int low, int high); int main() { srand(time(0)); printf("sizeof(int) = %d\n", sizeof(int)); printf("RAND_MAX = %d\n", RAND_MAX); printf("INT_MAX = %d\n", RAND_MAX); runtime(bitsortf); getchar(); return 0; } /* * 从指定文件名中读取数据,并进行排序,最后将排序后的数据写入 output.txt 中 */ void bitsort(char* filename) { int i; char buf[MAX_LEN]; FILE* fin = fopen(filename, "r"); if (fin == NULL) { fprintf(stderr, "can‘t open file: %s", filename); exit(1); } while (fgets(buf, MAX_LEN, fin)) { set(atoi(buf)); } fclose(fin); // show(); FILE* fout = fopen("output.txt", "w"); if (fout == NULL) { fprintf(stderr, "can‘t open file: %s", "output.txt"); exit(1); } for (i = 0; i < N; i++) { if (test(i)) { fprintf(fout, "%d\n", i); } } fclose(fout); printf("---------- sort successfully ---------------"); printf("\n"); } void bitsortf() { bitsort("data.txt"); } void runtime(void (*f)()) { printf("runtime ... \n"); int scale = 10; while (scale <= N) { testdata(scale, N); clock_t start = clock(); (*f)(); clock_t end = clock(); printf("scale: %d\t cost : %8.4f\n", scale, (double)(end-start)/CLOCKS_PER_SEC); printf("---------------------------------------------------"); printf("\n"); scale *= 10; } } /* * 创建测试数据:选出不大于 max 的 num 个正整数,并写入文件 data.txt 中 */ void testdata(int num, int max) { int i; assert(num <= max); FILE* fout = fopen("data.txt", "w"); if (fout == NULL) { fprintf(stderr, "can‘t open file: %s", "data.txt"); exit(1); } for (i = 0; i < num; i++) { fprintf(fout, "%d\n", (rand()*rand()) % max); } fclose(fout); printf("---------- testdata successfully ---------------"); printf("\n"); } /* * randRange: 生成给定范围的随机整数 */ int randRange(int low, int high) { assert (high <= low) ; return rand() % (high-low) + low; }
7. 额外说明
位图技术,可以说是一种非常有效的求解技术,在文件管理中就有应用到, 其作用类似于二分搜索技术。位图技术还能检测重复整数,缺失整数,比如在 43亿多个不大于2^32的随机整数排列中寻找一个重复整数(根据抽屉原理知必然存在)。在读书时,不仅要汲取问题的求解方案,还要领悟背后的通用技术。
如果问题不是对整数数组排序,而是对一系列记录排序,怎么利用已有算法呢? 可以通过某种函数对记录的关键字进行计算,得到互不重复的整数(这个过程类似于散列法),然后,使用位图技术对整数数组进行排序。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。