C# 位圖BitArray的使用

Posted on by

前面聊瞭佈隆過濾器，回歸認識一下位圖BitMap，閱讀前文的同學應該發現瞭佈隆過濾器本身就是基於位圖，是位圖的一種改進。

位圖

先看一個問題， 假如有1千萬個整數，整數范圍在1到1億之間，如何快速確定某個整數是否在這個1千萬個整數中呢？

乍一看是一個查找問題，循環、二分查找都是常規思路。

一個好的答案是存儲結構和算法的完美結合， 基於題幹上的特征和條件，我們是否有其他思路。

對於題幹我們使用高中排列組合的思維：有1億個有編號的空籃子，我們拿出這1千萬個有數字的球，放進對應的籃子。

最後，所有的籃子有兩種狀態：有球/無球，我們要確定某個數字是否存在，就看對應籃子是否為空。

什麼是位圖？每一位存放某種狀態，適用於海量數據，通常用於判斷數據是否存在。位圖的空間由數據的最大值決定。

位圖這種數據結構來大大節省內存的使用量。

我們隻需要構造一個長度為1億的bit數組，將有球位置標記為1，無球位置默認記為0; 這樣我們就將數字轉換成瞭一個被壓縮緊致的數組索引，1億bit數組不到16M空間。

確定某位置有球，隻需要O(1)的時間復雜度。

常用屬性

Count BitArray中包含實例的個數

IsReadOnly 獲取一個值，該值指示BitArray是否為隻讀

Item 獲取或設置BitArray中特定位置的值

Length 獲取或設置BitArray中元素的數目

常用的方法

And 和指定的BitArray中相應的元素做and運算

Or 按位或運算

Xor 按位異或運算

Not 取反所有元素

Get 獲取特定位置處的值

Set 設定特定位置處的值

SetAll 將BitArray中所有的元素設定為指定的值 

public sealed class BitArray : ICollection, IEnumerable, ICloneable
{
    public BitArray(BitArray bits); //用已有的BitArray給新的BitArray初始化
    
    public BitArray(bool[] values); //用佈爾數組初始化
    
    public BitArray(byte[] bytes);  //用字節數組初始化
    
    public BitArray(int length);    //初始化並設置位數值，此值會在使用中自動增長
    
    public BitArray(int[] values);  //用int數組初始化
    
    public BitArray(int length, bool defaultValue); //初始化並設置默認值
    
    public int Count { get; }   //位數組中現存的位的個數
    
    public bool IsReadOnly { get; } //確定位數組是否隻讀

    public bool IsSynchronized { get; } //是否同步對此BitArray的操作，用在線程安全上
    
    public int Length { get; set; }   //位數組的位數

    public object SyncRoot { get; }
    
    public bool this[int index] { get; set; } //索引器，利用索引讀位值
    
    public BitArray And(BitArray value);  //按位與

    public object Clone();  //創建BitArray 的淺表副本。
    
    public void CopyTo(Array array, int index);  //將BitArray拷貝到其他數組中
    
    public bool Get(int index);    //按下標讀取位值

    public IEnumerator GetEnumerator(); //返回循環訪問BitArray 的枚舉數

    public BitArray Not();  //按位非

    public BitArray Or(BitArray value);  //按位或
    
    public void Set(int index, bool value);  //按位設置值
    
    public void SetAll(bool value); //設置所有位為指定值

    public BitArray Xor(BitArray value);  //按位異或
}

C# 有專業的位圖數組：BitArray

using System;
using System.Collections;

namespace Bitmap
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var num = int.Parse(input);
            var bitmap = InitBitMap();
            if (bitmap.Get(num))
            {
                Console.WriteLine($"找到數字{num}");
            }
            else
            {
                Console.WriteLine($"未找到數字{num}");
            }
        }
        public static BitArray InitBitMap()
        {
            var myBA1 = new BitArray(10000);
            var arr1 = new int[] { 1, 2, 4, 6, 77, 77, 88, 99, 100, 500, 600, 700, 999, 8888 };
            foreach (int element in arr1)
            {
                myBA1[element] = true;
            }
            return myBA1;
        }
    }
}

BitArray是管理位值的緊湊數組，用佈爾值表示，其中true表示位是開啟的(1)，false表示位是關閉的(0)， 是引用類型，位於System.Collections命名空間。

以上隻是小試牛刀，我們針對原題再發散一下，如何找到以上1千萬數字中重復的數字？

還是籃子中放球的思路，這次我們要兩排籃子，也就是兩個BitMap，利用位AND運算(同時為True，結果才是True）找到兩排籃子中均有球的位置。

using System;
using System.Collections;

namespace Bitmap
{
    class Program
    {
        static void Main(string[] args)
        {
            var bitmap = InitBitMap();
            for (int i = 0; i < bitmap.Length; i++)
            {
                if(bitmap[i] == true)
                {
                    Console.WriteLine(i);
                }
            }
        }
        public static BitArray InitBitMap()
        {
            var myBA1 = new BitArray(10000);
            var myBA2 = new BitArray(10000);
            var arr1 = new int[] { 1, 2, 4, 6, 77, 77, 88, 99, 100, 500, 600, 700, 999, 8888 };
            foreach (int element in arr1)
            {
                if (myBA1[element] == false)
                {
                    myBA1[element] = true;
                }
                else
                {
                    myBA2[element] = true;
                }
            }
            myBA1 = myBA1.And(myBA2);
            return myBA1;
        }
    }
}

最後提醒各位：寶藏組件Redis天然支持位圖

到此這篇關於C# 位圖BitArray的使用的文章就介紹到這瞭,更多相關C# 位圖BitArray內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：