你好,游客 登录
背景:
阅读新闻

据处理时的一种BitMap小算法

[日期:2017-09-13] 来源:csdn  作者:Vincent_Song [字体: ]

一种大数据外部排序(内存无法加载所有排序元素)、去除重复元素、快速找到随机被删除元素的BitMap小算法,核心思想即通过将一个数作为下标(index)来索引一个bit表示一个数是否存在,排序时的时间复杂度为O(N),需要的额外空间的复杂度O(N/8),支持整个int范围(正负数都支持)的算法示例如下:

 

 

  1. char BitMask[] = {0x80 , 0x40 , 0x20 , 0x10 , 0x8 , 0x4 , 0x2 , 0x1}; 
  2.  
  3.  
  4. int WriteNumberBitToByte(char *ByteArra , unsigned int ByteArraSize , int Number) 
  5.     //printf("%d,%d,%d\n",(ByteArraSize * 4) - 1,-(ByteArraSize*4),Number); 
  6.      
  7.     if (((int)(ByteArraSize * 4) - 1) < Number || Number<-(int)(ByteArraSize*4) ) 
  8.     { 
  9.         return 0;   //failed,number out of bytearra. 
  10.     } 
  11.  
  12.     int BaseArraBitPos = ByteArraSize *4;   //ByteArraSize *8 /2 
  13.  
  14.     BaseArraBitPos+=Number; 
  15.  
  16.  
  17.     printf("BaseArraBitPos=%d,Number=%d\n",BaseArraBitPos,Number); 
  18.     ByteArra[BaseArraBitPos/8] |= Mask[BaseArraBitPos%8]; 
  19.  
  20.     return 1;   //success 
  21.  
  22. int IsNumberBitInByte(char *ByteArra , unsigned int ByteArraSize , int Number) 
  23.     if (((int)(ByteArraSize * 4) - 1) < Number || Number<-(int)(ByteArraSize*4) ) 
  24.     { 
  25.         return 0;   //failed,number out of bytearra. 
  26.     } 
  27.  
  28.  
  29.     int BaseArraBitPos = ByteArraSize *4;   //ByteArraSize *8 /2 
  30.  
  31.     BaseArraBitPos+=Number; 
  32.  
  33.     if (ByteArra[BaseArraBitPos/8] & BitMask[BaseArraBitPos%8]) { 
  34.         return 1; 
  35.     } 
  36.  
  37.     return 0;   //number not found. 
  38.  
  39. void PrintOrderedBitMap(char *BitMap,unsigned int BitMapCount) 
  40.     int MinmumNumber = -(BitMapCount*8/2); 
  41.     int MaximumValue = (BitMapCount*8/2)-1; 
  42.  
  43.     for (int i = MinmumNumber; i <= MaximumValue; ++i) 
  44.     { 
  45.         if (IsNumberBitInByte(BitMap,BitMapCount,i)) 
  46.         { 
  47.             printf("%d,", i); 
  48.         } 
  49.     } 
  50.  
  51.     printf("\n"); 
  52.  
  53.  
  54. int main() 
  55.     int Arra[] = {3,-4,2,0,-1,-8,7,-12,10}; 
  56.  
  57.     int MaximumValue =Arra[0],MinmumValue=Arra[0]; 
  58.     for (int i = 0; i < sizeof(Arra)/sizeof(Arra[0]); ++i) 
  59.     { 
  60.         if(MaximumValue<Arra[i]) { 
  61.             MaximumValue = Arra[i]; 
  62.         } 
  63.         if (MinmumValue>Arra[i]) 
  64.         { 
  65.             MinmumValue = Arra[i]; 
  66.         } 
  67.     } 
  68.  
  69.     MaximumValue=MaximumValue<0?-MaximumValue:MaximumValue; 
  70.     MinmumValue=MinmumValue<0?-MinmumValue:MinmumValue; 
  71.  
  72.     MaximumValue=MaximumValue>MinmumValue?MaximumValue:MinmumValue; 
  73.      
  74.     printf("MaximumValue=%d\n",MaximumValue); 
  75.     //unsigned int BitMapCount = (MaximumValue*2+7)/8; 
  76.     unsigned int BitMapCount = (MaximumValue+3)/4; 
  77.     BitMapCount = BitMapCount>0?BitMapCount:1; 
  78.     char *BitMap = (char*)malloc(BitMapCount); 
  79.  
  80.     for (int i = 0; i < sizeof(Arra)/sizeof(Arra[0]); ++i) 
  81.     { 
  82.         WriteNumberBitToByte(BitMap,BitMapCount,Arra[i]); 
  83.     } 
  84.  
  85.     PrintOrderedBitMap(BitMap,BitMapCount); 


仅支持unsigned int范围的算法示例如下:

 

  1. char BitMask[] = {0x80 , 0x40 , 0x20 , 0x10 , 0x8 , 0x4 , 0x2 , 0x1}; 
  2.  
  3.  
  4. int WriteNumberBitToByte(char *ByteArra , unsigned int ByteArraSize , unsigned int Number) 
  5.     if (((ByteArraSize * 8) - 1) < Number ) 
  6.     { 
  7.         return 0;   //failed,number out of bytearra. 
  8.     } 
  9.  
  10.     int BytePos = Number / 8; 
  11.     int BitPos = Number % 8; 
  12.  
  13.  
  14.     ByteArra[BytePos] |= BitMask[BitPos]; 
  15.  
  16.     return 1;   //success 
  17.  
  18. int IsNumberBitInByte(char *ByteArra , unsigned int ByteArraSize , unsigned int Number) 
  19.     if ((ByteArraSize * 8 - 1) < Number ) 
  20.     { 
  21.         return 0;   //failed,number out of bytearra. 
  22.     } 
  23.  
  24.     int BytePos = Number / 8; 
  25.     int BitPos = Number % 8; 
  26.  
  27.     if (ByteArra[BytePos] & BitMask[BitPos]) { 
  28.         return 1; 
  29.     } 
  30.  
  31.     return 0;   //number not found. 


上面的算法都是用一个bit来表示一个数,即只有2种可能,要么有,要么无,可以扩展到一个字节表示一个数,这样就可以统计出现255次范围内的重复元素,原理以此类推。

 

另外用bit来表示一个int数,节约了31倍的内存空间,即int(4*8),bit(8/1),所以数据量越来使用这种方式的优势越明显,前提是场景适用这种方式。

收藏 推荐 打印 | 阅读:
相关新闻       bitmap算法