一種大數據外部排序（內存無法加載所有排序元素）、去除重復元素、快速找到隨機被刪除元素的BitMap小算法，核心思想即通過將一個數作為下標（index）來索引一個bit表示一個數是否存在，排序時的時間復雜度為O(N)，需要的額外空間的復雜度O(N/8)，支持整個int范圍（正負數都支持）的算法示例如下：

char BitMask[] = {0x80 , 0x40 , 0x20 , 0x10 , 0x8 , 0x4 , 0x2 , 0x1};int WriteNumberBitToByte(char *ByteArra , unsigned int ByteArraSize , int Number) {//printf("%d,%d,%d\n",(ByteArraSize * 4) - 1,-(ByteArraSize*4),Number);if (((int)(ByteArraSize * 4) - 1) < Number || Number<-(int)(ByteArraSize*4) ){return 0; //failed,number out of bytearra.}int BaseArraBitPos = ByteArraSize *4; //ByteArraSize *8 /2BaseArraBitPos+=Number;printf("BaseArraBitPos=%d,Number=%d\n",BaseArraBitPos,Number);ByteArra[BaseArraBitPos/8] |= Mask[BaseArraBitPos%8];return 1; //success }int IsNumberBitInByte(char *ByteArra , unsigned int ByteArraSize , int Number) {if (((int)(ByteArraSize * 4) - 1) < Number || Number<-(int)(ByteArraSize*4) ){return 0; //failed,number out of bytearra.}int BaseArraBitPos = ByteArraSize *4; //ByteArraSize *8 /2BaseArraBitPos+=Number;if (ByteArra[BaseArraBitPos/8] & BitMask[BaseArraBitPos%8]) {return 1;}return 0; //number not found. }void PrintOrderedBitMap(char *BitMap,unsigned int BitMapCount) {int MinmumNumber = -(BitMapCount*8/2);int MaximumValue = (BitMapCount*8/2)-1;for (int i = MinmumNumber; i <= MaximumValue; ++i){if (IsNumberBitInByte(BitMap,BitMapCount,i)){printf("%d,", i);}}printf("\n"); }int main() {int Arra[] = {3,-4,2,0,-1,-8,7,-12,10};int MaximumValue =Arra[0],MinmumValue=Arra[0];for (int i = 0; i < sizeof(Arra)/sizeof(Arra[0]); ++i){if(MaximumValue<Arra[i]) {MaximumValue = Arra[i];}if (MinmumValue>Arra[i]){MinmumValue = Arra[i];}}MaximumValue=MaximumValue<0?-MaximumValue:MaximumValue;MinmumValue=MinmumValue<0?-MinmumValue:MinmumValue;MaximumValue=MaximumValue>MinmumValue?MaximumValue:MinmumValue;printf("MaximumValue=%d\n",MaximumValue);//unsigned int BitMapCount = (MaximumValue*2+7)/8;unsigned int BitMapCount = (MaximumValue+3)/4;BitMapCount = BitMapCount>0?BitMapCount:1;char *BitMap = (char*)malloc(BitMapCount);for (int i = 0; i < sizeof(Arra)/sizeof(Arra[0]); ++i){WriteNumberBitToByte(BitMap,BitMapCount,Arra[i]);}PrintOrderedBitMap(BitMap,BitMapCount); }

僅支持unsigned int范圍的算法示例如下：

char BitMask[] = {0x80 , 0x40 , 0x20 , 0x10 , 0x8 , 0x4 , 0x2 , 0x1};int WriteNumberBitToByte(char *ByteArra , unsigned int ByteArraSize , unsigned int Number) {if (((ByteArraSize * 8) - 1) < Number ){return 0; //failed,number out of bytearra.}int BytePos = Number / 8;int BitPos = Number % 8;ByteArra[BytePos] |= BitMask[BitPos];return 1; //success }int IsNumberBitInByte(char *ByteArra , unsigned int ByteArraSize , unsigned int Number) {if ((ByteArraSize * 8 - 1) < Number ){return 0; //failed,number out of bytearra.}int BytePos = Number / 8;int BitPos = Number % 8;if (ByteArra[BytePos] & BitMask[BitPos]) {return 1;}return 0; //number not found. }

上面的算法都是用一個bit來表示一個數，即只有2種可能，要么有，要么無，可以擴展到一個字節表示一個數，這樣就可以統計出現255次范圍內的重復元素，原理以此類推。

另外用bit來表示一個int數，節約了31倍的內存空間，即int（4*8），bit（8/1)，所以數據量越來使用這種方式的優勢越明顯，前提是場景適用這種方式。

總結

以上是生活随笔為你收集整理的大数据处理时的一种BitMap小算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。