簡單實用演算法——點陣圖演算法(BitMap)

来源:https://www.cnblogs.com/timefiles/archive/2020/07/23/BitMap.html
-Advertisement-
Play Games

BitMap的基本思想就是用一個bit位來標記某個元素對應的Value,而Key即是該元素。由於採用了Bit為單位來存儲數據,因此可以大大節省存儲空間。 BitMap可以看成一種數據結構。 ...


目錄

演算法原理

BitMap的基本思想就是用一個bit位來標記某個元素對應的Value,而Key即是該元素。由於採用了Bit為單位來存儲數據,因此可以大大節省存儲空間
BitMap可以看成一種數據結構

假設有這樣一個需求:在20億個隨機整數中找出某個數m是否存在其中,並假設32位操作系統,4G記憶體。
在Java中,int占4位元組,1位元組=8位(1 byte = 8 bit)。
如果每個數字用int存儲,那就是20億個int,因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45G
如果按位存儲就不一樣了,20億個數就是20億位,占用空間約為 (2000000000/8/1024/1024/1024)≈0.233G

優點和缺點

優點:由於採用了Bit為單位來存儲數據並建立映射關係來查找位置,因此可以大大減少存儲空間,加快在大量數據中查詢的時間。(有點哈希表的意思,但哈希中的value值數據類型可以豐富多樣,而BitMap最終查到的value只能表示簡單的幾種狀態。)
缺點:BitMap中的查詢結果(value)能表達的狀態有限,且所有的數據不能重覆。即不可對重覆的數據進行排序和查找

演算法實現(C#)

.NET中已經實現了BitMap的數據結構——BitArray,建議使用BitMap演算法解決問題時直接使用官方的BitArray
我參照.NET源碼實現了一個簡化版的BitMap,以int數組存儲位值(最多存21億個位值),代碼如下:

    class BitMap
    {
        public int Length{ get{ return m_length;}
        }
        private int[] m_array;
        private int m_length;

        public BitMap(int length):  this(length, false) { }

        //索引根據需求添加
        public bool this[int index]
        {
            get
            {                
                return Get(index);
            }
            set
            {
                Set(index,value); 
            }
        }

        //分配空間以容納長度位值, 位數組中的所有值都設置為defaultValue。
        public BitMap(int length, bool defaultValue)
        {
            if (length < 0) {
                throw new ArgumentOutOfRangeException("length", "長度值不能小於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;
        }
    
        //將位置索引處的位值設置為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));
            }
        }
    }

演算法應用

問題1:給40億個不重覆的unsigned int的整數,沒有排過序,然後再給一個數,如果快速判斷這個數是否在那40億個數當中。(解決海量數據中的查詢問題
問題1解法:建立一個位集合,全部初始化為0。遍歷40億個不重覆的整數,通過上述提供的一種映射(每個不重覆的整數映射到給定的位)找到其位的位置,標記為1。判斷這個數是否在大整數集合中,即通過映射關係計算此整數的位位置,檢查是否為1,若為1,則存在,若為0,則不存在

問題2:資料庫里存了很多800電話號碼,數量特別大,以至於記憶體放不下,如何排序,時間比空間更重要?電話號碼類似於800-810-5555。(高效排序
問題2解法:其實就是不重覆的任意7位數及其之內的排序問題。我們用1位來表示電話是否出現,遍歷整個電話號序列,設置相應的位,遍歷點陣圖收集位被設置的號碼即可。查看上述的實現代碼

參考文章:
演算法系列-bitmap演算法詳解和實現——CSDN
Bitmap簡介——博客園
經典演算法系列之(一) - BitMap——簡書


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1.首先手機安裝Xposed(app) 2.安裝Fdex2(app) 3.打開Fdex2 4.點擊要脫殼的app 5.adb pull (點擊脫殼app時候彈出的來的路徑) 保存本地路徑 6.完結-.- 後面湊字數........................................... ...
  • 例如導出指定文件夾中的所有mp4文件的文件名 1 @echo off 2 for /r C:\Users\Administrator\Desktop\video %%i in (*.mp4) do ( 3 echo %%i 4 echo %%i>>C:\Users\Administrator\Des ...
  • 看到一篇關於Java學習體系的總結,在這裡給大家分享一下: 一、Java SE部分 java基礎:基礎語法;面向對象(重點);集合框架(重點);常見類庫API;java界面編程:AWT;事件機制;Swing;java高級知識:Annotation;IO和NIO、AIO;多線程、線程池;阻塞、非阻塞、 ...
  • 介面概述: 1、介面是Java語言中的一種引用類型,是方法的"集合",所以介面的內部主要就是定義方法,包含常量,抽象方法(JDK 7及以前),額外增加預設方法和靜態方法(JDK 8),額外增加私有方法(jdk9)。 介面的定義,它與定義類方式相似,但是使用 interface 關鍵字。它也會被編譯成 ...
  • 智能指針可以對動態資源進行管理,保證任何情況下,已經構造的對象能夠安全的自動銷毀。 ...
  • 任何Java開發人員的必備技能 現在,讓我們一起探索這個Java開發人員路線圖,並找出應該學習哪些工具,框架,庫和API。 1.工具 路線圖工具部分分為兩個主要部分。首先,IDE是您的主要工具,它幾乎可以完成您所要求的一切,例如編譯,運行,調試,分析,測試,比較文件和代碼,重構等等。 第二部分是構建 ...
  • 內容簡介 · · · · · · 本書是經典教程的全新改版,作者根據Python 3.0版本的種種變化,全面改寫了書中內容,做到既能“瞻前”也能“顧後”。本書層次鮮明、結構嚴謹、內容翔實,特別是在最後幾章,作者將前面講述的內容應用到了10個引人入勝的項目中,並以模板的形式介紹了項目的開發過程。本書既 ...
  • 方法一:新增models的Manager方法 下麵就直接發代碼了 class RandomManager(models.Manager): def get_queryset(self): return super(RandomManager, self).get_queryset().order_b ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...