位图排序（位图技术应用）

首页 > 代码库 > 位图排序（位图技术应用）

位图排序（位图技术应用）

2024-07-28 06:06:16 221人阅读

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 是否为 1void set(int i);    // 将位向量第 i 位置 1void 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  10void 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的随机整数排列中寻找一个重复整数（根据抽屉原理知必然存在）。在读书时，不仅要汲取问题的求解方案，还要领悟背后的通用技术。

如果问题不是对整数数组排序，而是对一系列记录排序，怎么利用已有算法呢？可以通过某种函数对记录的关键字进行计算，得到互不重复的整数（这个过程类似于散列法），然后，使用位图技术对整数数组进行排序。

位图排序（位图技术应用）

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 位图排序（位图技术应用）

位图排序（位图技术应用）

看完仍有疑问？有类似问题直接问程序猿