理解位圖算法:使用 C++ 實現高效數據查重

在處理海量數據時,我們常常需要檢查某個元素是否已經存在于集合中。傳統的方法如哈希表或集合容器雖然有效,但在數據量極大的情況下會占用大量內存。這時,位圖算法 (Bitmap) 就成為了一種非常高效的解決方案。本文將通過分析一段使用位圖算法的 C++ 代碼,深入探討這種算法的原理和實現。

位圖算法基本原理

位圖算法的核心思想是使用一個二進制位 (bit) 來表示某個元素是否存在。每個位對應一個特定的值,如果該值存在,則對應的位被置為 1,否則為 0。這種方法的優勢在于它能極大地節省存儲空間。例如,使用一個 64 位的long long類型變量,我們可以表示 64 個不同的值,而不是像傳統數組那樣每個元素占用一個完整的存儲單元。

代碼實現分析

讓我們來分析這段使用位圖算法的 C++ 代碼:

#include<iostream>
#include<algorithm>
#include<vector>
#include<memory>
using namespace std;
typedef long long LL;
int main()
{int num;//元素個數;cin >> num;LL MAX = 0;vector<LL>q;for (int i = 0; i < num; i++){LL sum;cin >> sum;MAX = max(MAX, abs(sum));q.push_back(sum);}const LL len = MAX / 64 + 1;//位圖算法,長度由最大值的絕對值/容器數據類型字節大小,long long是64字節的;//LL arr[len]由于len是變量,所以這里沒辦法在棧上定義了unique_ptr<LL[]>arr(new LL[len]);unique_ptr<LL[]>brr(new LL[len]);LL mod = 64;for (auto it : q){LL sum = 1;if (it > 0){int idx = it / mod;LL num = it % mod;if (arr[idx] >> num)continue;else arr[idx] |= (sum << num);}else{int idx = abs(it) / mod;LL num = abs(it) % mod;if (brr[idx] >> num)continue;else brr[idx] |= (sum << num);}}
}

代碼功能解析

這段代碼的主要功能是讀取一組整數,然后使用位圖算法來標記每個數是否存在。代碼處理了正數和負數兩種情況,下面是詳細的步驟解析:

  1. 輸入處理與最大值計算

    • 首先讀取元素的數量num
    • 依次讀取每個元素,并計算它們的絕對值的最大值MAX
    • 將所有元素存儲在向量q
  2. 位圖數組初始化

    • 計算位圖數組的長度len,公式為MAX / 64 + 1
    • 使用unique_ptr動態分配兩個long long類型的數組arrbrr
    • arr用于存儲正數的位圖
    • brr用于存儲負數的位圖
  3. 位圖操作

    • 遍歷每個元素,根據其正負分別處理
    • 對于正數,計算其在位圖數組中的索引idx和位偏移num
    • 使用位運算檢查該位是否已被設置,如果未設置則設置該位
    • 負數的處理類似,但使用brr數組

位運算詳解

在位圖算法中,位運算是核心操作。讓我們詳細解釋代碼中的位運算部分:

計算索引和位偏移

int idx = it / mod;  // 計算元素所在的數組索引
LL num = it % mod;   // 計算元素在該索引位置的位偏移

檢查位是否已設置

if (arr[idx] >> num) continue;

這行代碼將arr[idx]右移num位,如果結果不為 0,則表示該位已被設置。

設置位

arr[idx] |= (sum << num);

這行代碼將 1 左移num位,然后使用按位或操作將對應位置為 1。

位圖算法的優勢與應用場景

位圖算法的主要優勢包括:

  • 空間效率極高:每個值只占用一個位,相比傳統方法節省大量內存
  • 操作速度快:位運算在現代計算機上非常高效
  • 實現簡單:核心邏輯只需要基本的位運算

位圖算法適用于以下場景:

  • 數據查重:檢查元素是否已經存在
  • 數據排序:可以在位圖上進行高效的排序操作
  • 數據統計:統計某個范圍內數據的分布情況

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/80111.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/80111.shtml
英文地址,請注明出處:http://en.pswp.cn/web/80111.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

數學復習筆記 12

前言 現在做一下例題和練習題。矩陣的秩和線性相關。另外還要復盤前面高數的部分的內容。奧&#xff0c;之前矩陣的例題和練習題&#xff0c;也沒有做完&#xff0c;行列式的例題和練習題也沒有做完。累加起來了。以后還是得學一個知識點就做一個部分的內容&#xff0c;日拱一…

1-10 目錄樹

在ZIP歸檔文件中&#xff0c;保留著所有壓縮文件和目錄的相對路徑和名稱。當使用WinZIP等GUI軟件打開ZIP歸檔文件時&#xff0c;可以從這些信息中重建目錄的樹狀結構。請編寫程序實現目錄的樹狀結構的重建工作。 輸入格式: 輸入首先給出正整數N&#xff08;≤104&#xff09;…

Python爬蟲實戰:研究 RPC 遠程調用機制,實現逆向解密

1. 引言 在網絡爬蟲技術的實際應用中,目標網站通常采用各種加密手段保護其數據傳輸和業務邏輯。這些加密機制給爬蟲開發帶來了巨大挑戰,傳統的爬蟲技術往往難以應對復雜的加密算法。逆向解密作為一種應對策略,旨在通過分析和破解目標網站的加密機制,獲取原始數據。 然而,…

debugfs:Linux 內核調試的利器

目錄 一、什么是 debugfs&#xff1f;二、debugfs 的配置和啟用方式2.1 內核配置選項2.2 掛載 debugfs2.3 Android 系統中的 debugfs 三、debugfs 的典型應用場景3.1 調試驅動開發3.2 內核子系統調試3.3 性能分析 四、常見 debugfs 子目錄與功能示例4.1 /sys/kernel/debug/trac…

lua 作為嵌入式設備的配置語言

從lua的腳本中獲取數據 lua中棧的索引 3 | -1 2 | -2 1 | -3 可以在lua的解釋器中加入自己自定的一些功能,其實沒啥必要,就是為了可以練習下lua

棋牌室臺球室快速接入美團團購接口

北極星平臺從2024年12月份開始慢慢關閉&#xff0c;現在很多開發者反饋北極星token已經不能刷新了&#xff0c;全部遷移到美團團購綜合平臺。 申請這個平臺要求很高 1、保證金費用要15萬起步 2、平臺必須是二級等保和安全產品 &#xff0c;一個二級等保費用10萬起步 所以很多…

開源輕量級地圖解決方案leaflet

Leaflet 地圖&#xff1a;開源輕量級地圖解決方案 Leaflet 是一個開源的 JavaScript 庫&#xff0c;用于在網頁中嵌入交互式地圖。它以輕量級、靈活性和易用性著稱&#xff0c;適用于需要快速集成地圖功能的項目。以下是關于 Leaflet 的詳細介紹和使用指南。 1. Leaflet 的核心…

一個批量文件Dos2Unix程序(Microsoft Store,開源)1.1.0 編碼檢測和預覽

之前的版本是個意思意思&#xff0c;驗證商店發布的&#xff08;其實是我以前自己用的工具&#xff09;&#xff0c;這次把格式檢查和轉換都做上了&#xff0c;功能應該差不多了&#xff0c;還有一些需要小改進的地方。 因為還沒什么用戶嘛&#xff0c;還是保持全功能免費試用。…

特征提取:如何從不同模態中獲取有效信息?

在多模態學習中&#xff0c;不同模態&#xff08;文本、圖像、語音、視頻、傳感器數據等&#xff09;所攜帶的信息豐富且互補。但不同模態的數據結構、表示空間、時空分布截然不同&#xff0c;因此&#xff0c;如何對各模態進行高效、有效的特征提取&#xff0c;是整個多模態學…

Go語言爬蟲系列教程 實戰項目JS逆向實現CSDN文章導出教程

爬蟲實戰&#xff1a;JS逆向實現CSDN文章導出教程 在這篇教程中&#xff0c;我將帶領大家實現一個實用的爬蟲項目&#xff1a;導出你在CSDN上發布的所有文章。通過分析CSDN的API請求簽名機制&#xff0c;我們將繞過平臺限制&#xff0c;獲取自己的所有文章內容&#xff0c;并以…

交叉熵損失函數,KL散度, Focal loss

交叉熵損失函數&#xff08;Cross-Entropy Loss&#xff09; 交叉熵損失函數&#xff0c;涉及兩個概念&#xff0c;一個是損失函數&#xff0c;一個是交叉熵。 首先&#xff0c;對于損失函數。在機器學習中&#xff0c;損失函數就是用來衡量我們模型的預測結果與真實結果之間…

149.WEB滲透測試-MySQL基礎(四)

免責聲明&#xff1a;內容僅供學習參考&#xff0c;請合法利用知識&#xff0c;禁止進行違法犯罪活動&#xff01; 內容參考于&#xff1a; 易錦網校會員專享課 上一個內容&#xff1a;148.WEB滲透測試-MySQL基礎&#xff08;三&#xff09; 非關系型數據庫&#xff1a; &a…

c/c++中程序內存區域的劃分

c/c程序內存分配的幾個區域&#xff1a; 1.棧區&#xff1a;在執行函數時&#xff0c;函數內局部變量的存儲單元都可以在棧上創建&#xff0c;函數執行結束時這些存儲單元自動被釋放&#xff0c;棧內存分配運算內置于處理器的指令集中&#xff0c;效率很高但是分配的內存容量有…

構建穩定的金字塔模式生態:從自然法則到系統工程

在自然界中&#xff0c;金字塔結構廣泛存在于生態系統之中&#xff0c;表現為營養級能量金字塔、生物量金字塔和數量金字塔等形式。這種結構不僅形象地描述了生態能量流轉的規律&#xff0c;也體現出生態系統中“穩定性”與“層級性”的天然法則。在現代軟件架構、企業組織、平…

Vue 3.0雙向數據綁定實現原理

Vue3 的數據雙向綁定是通過響應式系統來實現的。相比于 Vue2&#xff0c;Vue3 在響應式系統上做了很多改進&#xff0c;主要使用了 Proxy 對象來替代原來的 Object.defineProperty。本文將介紹 Vue3 數據雙向綁定的主要特點和實現方式。 1. 響應式系統 1.1. Proxy對象 Vue3 …

TIP-2021《SRGAT: Single Image Super-Resolution With Graph Attention Network》

推薦深藍學院的《深度神經網絡加速&#xff1a;cuDNN 與 TensorRT》&#xff0c;課程面向就業&#xff0c;細致講解CUDA運算的理論支撐與實踐&#xff0c;學完可以系統化掌握CUDA基礎編程知識以及TensorRT實戰&#xff0c;并且能夠利用GPU開發高性能、高并發的軟件系統&#xf…

大語言模型與多模態模型比較

一、核心差異&#xff1a;輸入數據類型與模態融合 輸入數據類型 LLM&#xff1a;僅處理文本數據&#xff0c;例如文本分類、機器翻譯、問答等任務&#xff0c;通過大規模語料庫學習語言規律。 LMM&#xff1a;支持文本、圖像、音頻、視頻等多種模態輸入&#xff0c;例如根據圖…

Apache HttpClient 5 用法-Java調用http服務

Apache HttpClient 5 核心用法詳解 Apache HttpClient 5 是 Apache 基金會推出的新一代 HTTP 客戶端庫&#xff0c;相比 4.x 版本在性能、模塊化和易用性上有顯著提升。以下是其核心用法及最佳實踐&#xff1a; 一、添加依賴 Maven 項目&#xff1a; <dependency><…

基于 Spark 的流量統計

一、引言 在互聯網行業&#xff0c;流量統計是分析網站或應用用戶行為、評估業務表現、優化資源分配以及制定營銷策略的關鍵環節。借助 Apache Spark 強大的分布式數據處理能力&#xff0c;我們可以高效地對大規模的流量數據進行統計分析&#xff0c;獲取有價值的洞察。本文將…

Python模塊化編程進階指南:從基礎到工程化實踐

一、模塊化編程核心原理與最佳實踐 1.1 模塊化設計原則 根據企業級項目實踐&#xff0c;模塊化開發應遵循以下核心原則&#xff1a; ??單一職責原則??&#xff1a;每個模塊只承擔一個功能域的任務&#xff08;如用戶認證模塊獨立于日志模塊&#xff09;??接口隔離原則…