c# 實(shí)現(xiàn)位圖算法(BitMap)
算法原理
BitMap的基本思想就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value,而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù),因此可以大大節(jié)省存儲(chǔ)空間。
BitMap可以看成一種數(shù)據(jù)結(jié)構(gòu)。
假設(shè)有這樣一個(gè)需求:在20億個(gè)隨機(jī)整數(shù)中找出某個(gè)數(shù)m是否存在其中,并假設(shè)32位操作系統(tǒng),4G內(nèi)存。
在Java中,int占4字節(jié),1字節(jié)=8位(1 byte = 8 bit)。
如果每個(gè)數(shù)字用int存儲(chǔ),那就是20億個(gè)int,因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45G
如果按位存儲(chǔ)就不一樣了,20億個(gè)數(shù)就是20億位,占用空間約為 (2000000000/8/1024/1024/1024)≈0.233G
優(yōu)點(diǎn)和缺點(diǎn)
優(yōu)點(diǎn):由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)并建立映射關(guān)系來(lái)查找位置,因此可以大大減少存儲(chǔ)空間,加快在大量數(shù)據(jù)中查詢(xún)的時(shí)間。(有點(diǎn)哈希表的意思,但哈希中的value值數(shù)據(jù)類(lèi)型可以豐富多樣,而B(niǎo)itMap最終查到的value只能表示簡(jiǎn)單的幾種狀態(tài)。)
缺點(diǎn):BitMap中的查詢(xún)結(jié)果(value)能表達(dá)的狀態(tài)有限,且所有的數(shù)據(jù)不能重復(fù)。即不可對(duì)重復(fù)的數(shù)據(jù)進(jìn)行排序和查找。
算法實(shí)現(xiàn)(C#)
.NET中已經(jīng)實(shí)現(xiàn)了BitMap的數(shù)據(jù)結(jié)構(gòu)——BitArray,建議使用BitMap算法解決問(wèn)題時(shí)直接使用官方的BitArray。
我參照.NET源碼實(shí)現(xiàn)了一個(gè)簡(jiǎn)化版的BitMap,以int數(shù)組存儲(chǔ)位值(最多存21億個(gè)位值),代碼如下:
class BitMap { public int Length{ get{ return m_length;} } private int[] m_array; private int m_length; public BitMap(int length): this(length, false) { } //索引根據(jù)需求添加 public bool this[int index] { get { return Get(index); } set { Set(index,value); } } //分配空間以容納長(zhǎng)度位值, 位數(shù)組中的所有值都設(shè)置為defaultValue。 public BitMap(int length, bool defaultValue) { if (length < 0) { throw new ArgumentOutOfRangeException("length", "長(zhǎng)度值不能小于0"); } int arrayLength = length > 0 ? (((length - 1) / 32) + 1) : 0; m_array = new int[arrayLength]; m_length = length; int fillValue = defaultValue ? unchecked(((int)0xffffffff)) : 0; for (int i = 0; i < m_array.Length; i++) { m_array[i] = fillValue; } } //返回位置索引處的位值。 public bool Get(int index) { if (index < 0 || index >= Length) { throw new ArgumentOutOfRangeException("index", "索引值超出范圍"); } return (m_array[index / 32] & (1 << (index % 32))) != 0; } //將位置索引處的位值設(shè)置為value。 public void Set(int index, bool value) { if (index < 0 || index >= Length) { throw new ArgumentOutOfRangeException("index", "索引值超出范圍"); } if (value) { m_array[index / 32] |= (1 << (index % 32)); } else { m_array[index / 32] &= ~(1 << (index % 32)); } } }
算法應(yīng)用
問(wèn)題1:
給40億個(gè)不重復(fù)的unsigned int的整數(shù),沒(méi)有排過(guò)序,然后再給一個(gè)數(shù),如果快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中。(解決海量數(shù)據(jù)中的查詢(xún)問(wèn)題)
問(wèn)題1解法:
建立一個(gè)位集合,全部初始化為0。遍歷40億個(gè)不重復(fù)的整數(shù),通過(guò)上述提供的一種映射(每個(gè)不重復(fù)的整數(shù)映射到給定的位)找到其位的位置,標(biāo)記為1。判斷這個(gè)數(shù)是否在大整數(shù)集合中,即通過(guò)映射關(guān)系計(jì)算此整數(shù)的位位置,檢查是否為1,若為1,則存在,若為0,則不存在
問(wèn)題2:
數(shù)據(jù)庫(kù)里存了很多800電話(huà)號(hào)碼,數(shù)量特別大,以至于內(nèi)存放不下,如何排序,時(shí)間比空間更重要?電話(huà)號(hào)碼類(lèi)似于800-810-5555。(高效排序)
問(wèn)題2解法:
其實(shí)就是不重復(fù)的任意7位數(shù)及其之內(nèi)的排序問(wèn)題。我們用1位來(lái)表示電話(huà)是否出現(xiàn),遍歷整個(gè)電話(huà)號(hào)序列,設(shè)置相應(yīng)的位,遍歷位圖收集位被設(shè)置的號(hào)碼即可。查看上述的實(shí)現(xiàn)代碼
以上就是c# 實(shí)現(xiàn)位圖算法(BitMap)的詳細(xì)內(nèi)容,更多關(guān)于c# 位圖算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C#使用CefSharp實(shí)現(xiàn)內(nèi)嵌網(wǎng)頁(yè)詳解
這篇文章主要介紹了C# WPF里怎么使用CefSharp嵌入一個(gè)網(wǎng)頁(yè),并給出一個(gè)簡(jiǎn)單示例演示C#和網(wǎng)頁(yè)(JS)的交互實(shí)現(xiàn),感興趣的小伙伴可以了解一下2023-04-04C#調(diào)用打印機(jī)實(shí)現(xiàn)打印
這篇文章介紹了C#調(diào)用打印機(jī)實(shí)現(xiàn)打印的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-04-04C#中Winform窗體Form的關(guān)閉按鈕變灰色的方法
這篇文章主要介紹了C#中Winform窗體Form的關(guān)閉按鈕變灰色的方法,對(duì)于C#程序界面的設(shè)計(jì)有一定的借鑒價(jià)值,需要的朋友可以參考下2014-08-08C#實(shí)現(xiàn)基于XML配置MenuStrip菜單的方法
這篇文章主要介紹了C#實(shí)現(xiàn)基于XML配置MenuStrip菜單的方法,涉及C#使用XML配置MenuStrip菜單的原理與實(shí)現(xiàn)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-08-08C#使用LINQ查詢(xún)操作符實(shí)例代碼(一)
這篇文章介紹了C#使用LINQ查詢(xún)操作符的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-06-06C#實(shí)現(xiàn)簡(jiǎn)單串口通訊實(shí)例
這篇文章主要為大家詳細(xì)介紹了C#實(shí)現(xiàn)簡(jiǎn)單串口通訊的方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-02-02C#實(shí)現(xiàn)簡(jiǎn)單的Login窗口實(shí)例
這篇文章主要介紹了C#實(shí)現(xiàn)簡(jiǎn)單的Login窗口,實(shí)例分析了C#顯示及關(guān)閉登陸Login窗口的技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-08-08