C#中如何實現(xiàn)位圖BitArray

這篇文章主要介紹了C#中如何實現(xiàn)位圖BitArray，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

位圖

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

乍一看是一個查找問題，循環(huán)、二分查找都是常規(guī)思路。

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

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

最后，所有的籃子有兩種狀態(tài)：有球/無球，我們要確定某個數(shù)字是否存在，就看對應籃子是否為空。

什么是位圖？每一位存放某種狀態(tài)，適用于海量數(shù)據(jù)，通常用于判斷數(shù)據(jù)是否存在。位圖的空間由數(shù)據(jù)的最大值決定。

位圖這種數(shù)據(jù)結構來大大節(jié)省內存的使用量。

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

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

常用屬性

Count BitArray中包含實例的個數(shù)

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

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

Length 獲取或設置BitArray中元素的數(shù)目

常用的方法

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); //用布爾數(shù)組初始化
    
    public BitArray(byte[] bytes);  //用字節(jié)數(shù)組初始化
    
    public BitArray(int length);    //初始化并設置位數(shù)值，此值會在使用中自動增長
    
    public BitArray(int[] values);  //用int數(shù)組初始化
    
    public BitArray(int length, bool defaultValue); //初始化并設置默認值
    
    public int Count { get; }   //位數(shù)組中現(xiàn)存的位的個數(shù)
    
    public bool IsReadOnly { get; } //確定位數(shù)組是否只讀

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

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

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

    public IEnumerator GetEnumerator(); //返回循環(huán)訪問BitArray 的枚舉數(shù)

    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# 有專業(yè)的位圖數(shù)組：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($"找到數(shù)字{num}");
            }
            else
            {
                Console.WriteLine($"未找到數(shù)字{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是管理位值的緊湊數(shù)組，用布爾值表示，其中true表示位是開啟的(1)，false表示位是關閉的(0)， 是引用類型，位于System.Collections命名空間。

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

還是籃子中放球的思路，這次我們要兩排籃子，也就是兩個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#中如何實現(xiàn)位圖BitArray”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業(yè)資訊頻道，更多相關知識等著你來學習!