当前位置: 首页 > news >正文

基于C#实现Bitmap算法

在所有具有性能优化的数据结构中,我想大家使用最多的就是 hash 表,是的,在具有定位查找上具有 O(1)的常量时间,多么的简洁优美,但是在特定的场合下:
①:对 10 亿个不重复的整数进行排序。
②:找出 10 亿个数字中重复的数字。
当然我只有普通的服务器,就算 2G 的内存吧,在这种场景下,我们该如何更好的挑选数据结构和算法呢?

一、问题分析

这年头,大牛们写的排序算法也就那么几个,首先我们算下放在内存中要多少 G:
(10 亿 * 32)/(102410241024*8)=3.6G,可怜的 2G 内存直接爆掉,所以各种神马的数据结构都玩不起来了,当然使用外排序还是可以解决问题的,由于要走 IO 所以暂时剔除,因为我们要玩高性能,无望后我们想想可不可以在二进制位上做些手脚?
比如我要对{1,5,7,2}这四个 byte 类型的数字做排序,该怎么做呢?我们知道 byte 是占 8 个 bit 位,其实我们可以将数组中的值作为 bit 位的 key,value 用”0,1“来标识该 key 是否出现过?下面看图:
image.png
从图中我们精彩的看到,我们的数组值都已经作为 byte 中的 key 了,最后我只要遍历对应的 bit 位是否为 1 就可以了,那么自然就成有序数组了。
可能有人说,我增加一个 13 怎么办?很简单,一个字节可以存放 8 个数,那我只要两个 byte 就可以解决问题了。
image.png
可以看出我将一个线性的数组变成了一个 bit 位的二维矩阵,最终我们需要的空间仅仅是:3.6G/32=0.1G 即可,要注意的是 bitmap 排序不是 N 的,而是取决于待排序数组中的最大值,在实际应用上关系也不大,比如我开 10 个线程去读 byte 数组,那么复杂度为:O(Max/10)。

二、代码

我想 bitmap 的思想大家都清楚了,这一次又让我们见证了二进制的魅力,当然这些移位都是位运算的工作了,熟悉了你就玩转了。

1、Clear 方法(将数组的所有 bit 位置 0)

比如要将当前 4 对应的 bit 位置 0 的话,只需要 1 左移 4 位取反与 B[0] & 即可。
image.png

 #region 初始化所用的bit位为0/// <summary>/// 初始化所用的bit位为0/// </summary>/// <param name="i"></param>static void Clear(byte i){//相当于 i%8 的功能var shift = i & 0x07;//计算应该放数组的下标var arrindex = i >> 3;//则将当前byte中的指定bit位取0,&后其他对方数组bit位必然不变,这就是 1 的妙用var bitPos = ~(1 << shift);//将数组中的指定bit位置一  “& 操作”a[arrindex] &= (byte)(bitPos);}#endregion

2、Add 方法(将 bit 置 1 操作)

同样也很简单,要将当前 4 对应的 bit 位置 1 的话,只需要 1 左移 4 位与 B[0] | 即可。
image.png

 #region 设置相应bit位上为1/// <summary>/// 设置相应bit位上为1/// </summary>/// <param name="i"></param>static void Add(byte i){//相当于 i%8 的功能var shift = i & 0x07;//计算应该放数组的下标var arrindex = i >> 3;//将byte中的 1 移动到i位var bitPos = 1 << shift;//将数组中的指定bit位置一  “| 操作”a[arrindex] |= (byte)bitPos;}#endregion

3、Contain 方法(判断当前 bit 位是否是 1)

如果看懂了 Clear 和 Add,我相信最后一个方法已经不成问题了。

 #region 判断当前的x在数组的位中是否存在/// <summary>///判断当前的x在数组的位中是否存在/// </summary>/// <param name="i"></param>/// <returns></returns>static bool Contain(byte i){var j = a[i >> 3] & (1 << (i & 0x07));if (j == 0)return false;return true;}#endregion

最后上总的代码:

 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class Program{static byte n = 7;static byte[] a;public static void Main(){//节省空间的做法a = new byte[(n >> 3) + 1];for (byte i = 0; i < n; i++)Clear(i);Add(4);Console.WriteLine("插入4成功!");var s = Contain(4);Console.WriteLine("当前是否包含4:{0}", s);s = Contain(5);Console.WriteLine("当前是否包含5:{0}", s);Console.Read();}#region 初始化所用的bit位为0/// <summary>/// 初始化所用的bit位为0/// </summary>/// <param name="i"></param>static void Clear(byte i){//相当于 i%8 的功能var shift = i & 0x07;//计算应该放数组的下标var arrindex = i >> 3;//则将当前byte中的指定bit位取0,&后其他对方数组bit位必然不变,这就是 1 的妙用var bitPos = ~(1 << shift);//将数组中的指定bit位置一  “& 操作”a[arrindex] &= (byte)(bitPos);}#endregion#region 设置相应bit位上为1/// <summary>/// 设置相应bit位上为1/// </summary>/// <param name="i"></param>static void Add(byte i){//相当于 i%8 的功能var shift = i & 0x07;//计算应该放数组的下标var arrindex = i >> 3;//将byte中的 1 移动到i位var bitPos = 1 << shift;//将数组中的指定bit位置一  “| 操作”a[arrindex] |= (byte)bitPos;}#endregion#region 判断当前的x在数组的位中是否存在/// <summary>///判断当前的x在数组的位中是否存在/// </summary>/// <param name="i"></param>/// <returns></returns>static bool Contain(byte i){var j = a[i >> 3] & (1 << (i & 0x07));if (j == 0)return false;return true;}#endregion}}

image.png

相关文章:

基于C#实现Bitmap算法

在所有具有性能优化的数据结构中&#xff0c;我想大家使用最多的就是 hash 表&#xff0c;是的&#xff0c;在具有定位查找上具有 O(1)的常量时间&#xff0c;多么的简洁优美&#xff0c;但是在特定的场合下&#xff1a; ①&#xff1a;对 10 亿个不重复的整数进行排序。 ②&am…...

科学与工程计算基础(数值计算)知识点总结

数值计算 第1章 概论1.2 数值计算中的误差1.2.1 误差的来源和分类1.2.2 误差与有效数字1.2.3 数值运算的误差估计 1.3 误差定性分析和避免误差危害1.3.1 算法的数值稳定性1.3.3 避免误差危害 1.4 数值计算中算法设计的技术1.5 习题1.5.1 判断题1.5.2 计算题 第2章 插值法2.2 拉…...

oracle查询开始时间和结束时间之间的连续月份

SELECT TO_CHAR(ADD_MONTHS(TO_DATE(2023-01,YYYY-MM), ROWNUM - 1), YYYY-MM) AS fmonth FROM DUALCONNECT BY ROWNUM < CEIL(MONTHS_BETWEEN(TO_DATE(2023-11, YYYY-MM), TO_DATE(2023-01,YYYY-MM))1)...

通过 python 脚本迁移 Redis 数据

背景 需求&#xff1a;需要将的 Redis 数据迁移由云厂商 A 迁移至云厂商 B问题&#xff1a;云版本的 Redis 版本不支持 SYNC、MIGRATE、BGSAVE 等命令&#xff0c;使得许多工具用不了&#xff08;如 redis-port&#xff09; 思路 &#xff08;1&#xff09;从 Redis A 获取所…...

nodejs之express学习(1)

安装 npm i express使用 // 导入 const express require(express) // 创建应用 const app express() // 创建路由 app.get(/home,(req,res)>{res.end("hello express") }) app.listen(3000,()>{console.log("服务已启动~") })路由的介绍 什么是…...

【LeetCode】121. 买卖股票的最佳时机

121. 买卖股票的最佳时机 难度&#xff1a;简单 题目 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获…...

Vue3-VueRouter4路由语法解析

1.创建路由实例由createRouter实现 2.路由模式 1&#xff09;history模式使用createWebHistory()&#xff1a;地址栏不带# 2&#xff09;hash模式使用createWebHashHistory()&#xff1a;地址栏带# 3&#xff09;参数是基础路径&#xff0c;默认/ 括号里的就是设置路径的前…...

ChromeDriver最新版本下载与安装方法

关于ChromeDriver最新下载地址&#xff1a;https://googlechromelabs.github.io/chrome-for-testing/ 下载与安装 setp1&#xff1a;查看Chrome浏览器版本 首先&#xff0c;需要检查Chrome浏览器的版本。请按照以下步骤进行&#xff1a; 打开Chrome浏览器。 点击浏览器右上角…...

illuminate/database 使用 四

文档&#xff1a;Hyperf Database: Getting Started - Laravel 10.x - The PHP Framework For Web Artisans 因为hyperf使用illuminate/database&#xff0c;所以按照文章&#xff0c;看illuminate/database代码实现。 一、读写分离 根据文档读写的host可以分开。设置读写分…...

Spring面向切面编程(AOP);Spring控制反转(IOC);解释一下Spring AOP里面的几个名词;Spring 的 IoC支持哪些功能

文章目录 Spring面向切面编程(AOP)什么是AOPSpring AOP and AspectJ AOP 的区别&#xff1f;Spring AOP中的动态代理如何理解 Spring 中的代理&#xff1f;解释一下Spring AOP里面的几个名词Spring在运行时通知对象Spring切面可以应用5种类型的通知&#xff1a;什么是切面 Aspe…...

vatee万腾的科技征途:Vatee独特探索的数字化力量

在数字化时代的浪潮中&#xff0c;Vatee万腾以其独特的科技征途成为引领者。公司在数字化领域的探索之路不仅是技术的创新&#xff0c;更是一种对未知的勇敢涉足&#xff0c;是对新时代的深刻洞察和积极实践。 Vatee万腾通过独特的探索&#xff0c;展示了在数字化征途上的创新力…...

MySQL学习day03

一、SQL图形化界面工具 常用比较常用的图形化界面有sqlyog、mavicat、datagrip datagrip工具使用相当方便&#xff0c;功能比前面两种都要强大。 DataGrip工具的安装和使用请查看这篇文档&#xff1a;DataGrip 安装教程 DML-介绍 DML全称是Data Manipulation Language(数据…...

《QT从基础到进阶·三十七》QWidget实现左侧导航栏效果

NavigationBarPlugin插件类实现了对左侧导航栏的管理&#xff0c;我们可以在导航栏插件中添加界面&#xff0c;并用鼠标点击导航栏能够切换对应的界面。 源码在文章末尾 实现效果如下&#xff1a; NavigationBarPlugin实现的接口如下&#xff1a; class NAVIGATIONBAR_EXP…...

sftp学习

什么是sftp&#xff1f; sftp的简单操作 远程连接 int RobostSftp::Init(QString ip,QString port,QString user_name, QString user_password) { int rc;session ssh_new();if (!session) {fprintf(stderr, "ssh initialization failed\n");// return 1…...

C++之STL库:string类(用法列举和总结)

前言 大家在学习STL库的时候一定要学会看英文文档&#xff0c;俗话说熟能生巧&#xff0c;所以还得多练&#xff01;在使用string类之前&#xff0c;要包含头文件#include <string>和using namespace std; 文档链接&#xff1a;string - C Reference 一、string——构造…...

小程序中的大道理--综述

前言 以下将用一个小程序来探讨一些大道理, 这些大道理包括可扩展性, 抽象与封装, 可维护性, 健壮性, 团队合作, 工具的利用, 可测试性, 自顶向下, 分而治之, 分层, 可读性, 模块化, 松耦合, MVC, 领域模型, 甚至对称性, 香农的信息论等等. 为什么不用大程序来说大道理呢? …...

tlais智能学习辅助系统-修改部门功能实现

学习黑马程序员的JavaWeb课程&#xff0c;自己写的部门信息修改部分程序 控制层&#xff1a; //DeptController.java /** * 根据ID查询部门信息 * param id * return */ GetMapping("/{id}") public Result select(PathVariable Integer id){log.info("查询id…...

GLM: 自回归空白填充的多任务预训练语言模型

当前&#xff0c;ChatGLM-6B 在自然语言处理领域日益流行。其卓越的技术特点和强大的语言建模能力使其成为对话语言模型中的佼佼者。让我们深入了解 ChatGLM-6B 的技术特点&#xff0c;探索它在对话模型中的创新之处。 GLM: 自回归空白填充的多任务预训练语言模型 ChatGLM-6B 技…...

函数递归所应满足的条件

1.递归的概念 递归是学习C语⾔函数绕不开的⼀个话题&#xff0c;那什么是递归呢&#xff1f; 递归其实是⼀种解决问题的⽅法&#xff0c;在C语⾔中&#xff0c;递归就是函数⾃⼰调⽤⾃⼰。 递归的思想&#xff1a; 把⼀个⼤型复杂问题层层转化为⼀个与原问题相似&#xff0c;但…...

Python入职某新员工大量使用Lambda表达式,却被老员工喷是屎山

Python中Lambda表达式是一种简洁而强大的特性,其在开发中的使用优缺点明显,需要根据具体场景权衡取舍。 Lambda表达式的优点之一是它的紧凑语法,适用于一些短小而简单的函数。这种形式使得代码更为精炼,特别在一些函数式编程场景中,Lambda表达式可以提高代码的表达力。此外…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

英国云服务器上安装宝塔面板(BT Panel)

在英国云服务器上安装宝塔面板&#xff08;BT Panel&#xff09; 是完全可行的&#xff0c;尤其适合需要远程管理Linux服务器、快速部署网站、数据库、FTP、SSL证书等服务的用户。宝塔面板以其可视化操作界面和强大的功能广受国内用户欢迎&#xff0c;虽然官方主要面向中国大陆…...

2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】

1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...