在所有具有性能優化的數據結構中，我想大家使用最多的就是hash表，是的，在定位查找場景上具有O(1)的常量時間，多麼的簡潔優美，

但是在特定的場合下：

①：對10億個不重複的整數進行排序。

②：找出10億個數字中重複的數字。

當然我只有普通的服務器，就算2G的內存吧，在這種場景下，我們該如何更好的挑選數據結構和算法呢？

一：問題分析

這年頭，大牛們寫的排序算法也就那麼幾個，首先我們算下放在內存中要多少G: (10億 32)/(1024 1024 1024 8)=3.6G，可憐的2G內存直接爆掉，所以各種神馬的數據結構都玩不起來了，當然使用外排序還是可以解決問題的，由於要走IO所以暫時剔除，既然是數據結構和算法，所以高性能是必須的，想想可不可以在二進制位上做些手腳？比如我要對  {1,5,7,2} 這四個byte類型的數字做排序，該怎麼做呢？大家知道byte是佔用8bit，轉變思路可以將數組中的值作爲bit位的key，value用”0，1“來標識該key是否出現過？下面看圖：

從圖中我們精彩的看到，數組值都已經作爲byte中的key了，最後我只要遍歷對應的bit位是否爲1就可以了，那麼自然就成了有序數組。可能有人說，我增加一個13怎麼辦？很簡單，一個字節可以存放8個數，那兩個byte是不是就可以存16個數？剛好了覆蓋了13個，畫圖如下：

可以看出我將一個線性的數組變成了一個bit位的二維矩陣，最終需要的空間僅僅是:3.6G/32=0.1G即可，要注意的是bitmap排序不是O(N)的，而是取決於待排序數組中的最大值，有時候必須要加速的話，可以開10個線程去讀byte數組，那麼複雜度爲:O(Max/10)。

二：代碼

我想bitmap的思想大家都清楚了，這一次又讓我們見證了二進制的魅力，當然這些移位都是位運算的工作了，熟悉了你就玩轉了。

1:Clear方法（將數組的所有bit位賦值0）

比如要將當前4對應的bit位賦值0的話，只需要1左移4位取反與B[0] & 即可。

/// <summary>
        /// 初始化所用的bit位爲0
        /// </summary>
        /// <param name="i"></param>
        static void Clear(byte i)
        {
            //相當於 i%8 的功能
            var shift = i & 0x07;

            //計算應該放數組的下標
            var arrindex = i >> 3;

            //則將當前byte中的指定bit位取0，&後其他對方數組bit位必然不變，這就是 1 的妙用
            var bitPos = ~(1 << shift);

            //將數組中的指定bit位置一  “& 操作”
            a[arrindex] &= (byte)(bitPos);
        }

2:Add方法（將bit置1操作）

同樣也很簡單，要將當前4對應的bit位賦值1的話，只需要1左移4位與B[0] | 即可。

/// <summary>
        /// 設置相應bit位上爲1
        /// </summary>
        /// <param name="i"></param>
        static void Add(byte i)
        {
            //相當於 i%8 的功能
            var shift = i & 0x07;

            //計算應該放數組的下標
            var arrindex = i >> 3;

            //將byte中的 1 移動到i位
            var bitPos = 1 << shift;

            //將數組中的指定bit位置一  “| 操作”
            a[arrindex] |= (byte)bitPos;
        }

3:Contain方法（判斷當前bit位是否是1）

如果看懂了Clear和Add，我相信最後一個方法已經不成問題了。

/// <summary>
        ///判斷當前的x在數組的位中是否存在
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        static bool Contain(byte i)
        {
            var j = a[i >> 3] & (1 << (i & 0x07));

            if (j == 0)
                return false;
            return true;
        }

4. 最後上總的代碼：

using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Diagnostics;
 using System.Threading;
 using System.IO;

 namespace ConsoleApplication2
 {
     public class Program
     {
         static byte n = 7;

         static byte[] a;

         public static void Main()
         {
             //節省空間的做法
             a = new byte[(n >> 3) + 1];

             for (byte i = 0; i<n; i++)
                 Clear(i);

             Add(4);
             Console.WriteLine("插入4成功！");

             var s = Contain(4);

             Console.WriteLine("當前是否包含4:{0}", s);

             s = Contain(5);

             Console.WriteLine("當前是否包含5:{0}", s);

             Console.Read();
         }

         #region 初始化所用的bit位爲0
         /// <summary>
         /// 初始化所用的bit位爲0
         /// </summary>
         /// <param name="i"></param>
         static void Clear(byte i)
         {
             //相當於 i%8 的功能
             var shift = i & 0x07;

             //計算應該放數組的下標
             var arrindex = i >> 3;

             //則將當前byte中的指定bit位取0，&後其他對方數組bit位必然不變，這就是 1 的妙用
             var bitPos = ~(1 << shift);

             //將數組中的指定bit位置一  “& 操作”
             a[arrindex] &= (byte) (bitPos);
         }
         #endregion

         #region 設置相應bit位上爲1
         /// <summary>
         /// 設置相應bit位上爲1
         /// </summary>
         /// <param name="i"></param>
         static void Add(byte i)
         {
             //相當於 i%8 的功能
             var shift = i & 0x07;

             //計算應該放數組的下標
             var arrindex = i >> 3;

             //將byte中的 1 移動到i位
             var bitPos = 1 << shift;

             //將數組中的指定bit位置一  “| 操作”
             a[arrindex] |= (byte) bitPos;
         }
         #endregion

         #region 判斷當前的x在數組的位中是否存在
         /// <summary>
         ///判斷當前的x在數組的位中是否存在
         /// </summary>
         /// <param name="i"></param>
         /// <returns></returns>
         static bool Contain(byte i)
         {
             var j = a[i >> 3] & (1 << (i & 0x07));

             if (j == 0)
                 return false;
             return true;
         }
         #endregion
     }
 }

非常簡單的一個數據結構，您學會了嗎？

相關文章