點陣圖法

點陣圖法是大數據處理中經常用到的技巧，覺得挺有趣，就來講幾句，希望能把點陣圖的思想解釋清楚。

個人理解，如有錯誤，歡迎各路大神指正！

點陣圖法：電腦中表示數據的最小單位為Bit,存儲0或者1。而c#中int的大小為4個位元組，即32個bit。

如果用int類型表示一個數值，那麼一個數值就需要用到32位的存儲空間，如果使用0或者1來表示當前索引對應值是否存在，那麼原本一個int所占用的空間，可以表示32個整數。

[0] [1] [1] [0] [0] [0] [0] [1] ，如果當一個元素的值為1時，我們就可以判斷出其對應的索引值存在，這個例子中表示1，2，7存在。

可以簡單的說，數據記憶體占用率降低到了1/32.

當我們要處理的數據量不僅巨大，並且數據值也極大的時候，用一般的整數值類型（int，int64,long）會造成大量的記憶體消耗。

這時候使用點陣圖法，就能體現出其優勢。

實現（c#）：

這裡是用點陣圖法實現的排序方法。

public static Array BitSort(int[] arr, int largestNumber) //傳入數組，以及數組的最大值
        {
            BitArray bitAry = new BitArray(largestNumber+1);//根據數據的最大值，創建相應的點陣列

            foreach (var item in arr) 
            {
                bitAry[item] = true;//把數組元素值作為索引，將該索引對應的值置為1，表示該值存在
            }
            //一次遍歷之後，要排序的數組包含的所有值，在點陣列中被置為1

            int[] result = new int[arr.Length];

            var j = 0;
            for (var i = 0; i < bitAry.Length; i++) 
            {
                if (bitAry[i] == true) //遍歷點陣列，如果對應的值為1，則將其索引值放置到新集合內，一次遍歷，就可以完成排序
                {
                    result[j] = i;
                    j++;
                }
            }


            return result;
        }

用點陣圖法，也可以來快速判斷，一個大數據集合中，是否包含了某個特定的值。

思路：創建點陣圖來反應數據集，用特定值作為索引，判斷值是否為1，若為1，則表示該值存在於數據集合中。

也可以用來去重，有興趣的，可以自己實現以下。

劣勢：

1. 需要知道數據集的範圍，方可快速確定知道需要創建多大的點陣圖。

2. 如果數據離散程度大，那麼空間使用率低。如[1,2,3,4,5,900000,900001]

3. 可能較難理解。