做域名不做网站可以吗最近国际新闻热点

做域名不做网站可以吗,最近国际新闻热点,网站开发外包公司有哪些部门,科技产品你是否遇到过这样的场景#xff1a;面对 40 亿个无符号整数#xff0c;需要快速判断某个数是否存在#xff0c;但直接存储这些数据需要 16GB 内存#xff0c;普通电脑根本扛不住#xff1f;这时候#xff0c;位图#xff08;Bitmap#xff09;就能用不到 500MB 的空间解…你是否遇到过这样的场景面对 40 亿个无符号整数需要快速判断某个数是否存在但直接存储这些数据需要 16GB 内存普通电脑根本扛不住这时候位图Bitmap就能用不到 500MB 的空间解决这个难题 —— 它是海量数据判存场景的 “空间魔术师”也是 C 工程师必须掌握的核心数据结构。目录一、为什么需要位图—— 海量数据的存储困境1. 常规解法的致命缺陷2. 位图的核心思想用 “位” 代替 “字节”二、位图的底层实现从原理到代码1. 核心结构与初始化2. 核心接口实现set/reset/test1set标记数值存在置 12reset取消数值标记置 03test判断数值是否存在3. 关键注意事项三、位图的实战应用不止于判存1. 整型数据排序 去重2. 集合运算交集 / 并集3. 操作系统底层应用四、位图的局限性与扩展1. 核心局限2. 扩展双位标记法统计出现次数五、完整测试示例总结一、为什么需要位图—— 海量数据的存储困境先看一个经典面试题给定 40 亿个不重复的无符号整数未排序快速判断某个无符号整数是否存在。1. 常规解法的致命缺陷我们先算一笔空间账无符号整数占 4 字节40 亿个整数的总空间 40 亿 × 4B 16GB普通电脑内存通常为 8GB即便有 16GB操作系统和其他程序也会占用大量空间16GB 数据根本无法全部加载到内存。再看常见解法的问题解法时间复杂度核心问题排序 二分查找O(nlogn)O(logn)数据太大无法加载到内存排序set/unordered_set插入O(logn)/ 查询O(1)16GB 数据无法存入内存归并排序 磁盘排序O(nlogn)磁盘不支持高效随机访问字典树O(k)k 为位数仅适用于字符串不适合整数核心矛盾常规解法的空间复杂度太高无法适配海量数据的判存需求。2. 位图的核心思想用 “位” 代替 “字节”位图的本质是用一个二进制位表示一个数的存在状态1 存在0 不存在通过 “直接定址法” 建立数值到二进制位的映射无符号整数的范围是0∼232−1约 42 亿仅需 42 亿个二进制位空间计算42 亿 bit 42 亿 / 8 / 1024 / 1024 ≈ 512MB相比 16GB 节省 32 倍空间这种 “用位代替字节” 的设计让位图成为海量数据判存的最优解。二、位图的底层实现从原理到代码位图的实现核心是 “位运算”—— 计算机最小存储单位是字节8 位我们需要用整型数组如vectorint封装位操作每个 int 占 32 位可存储 32 个数值的状态。1. 核心结构与初始化先看bitset.h中的核心定义namespace sicheng { class bitset { public: // 构造函数初始化位图空间 bitset(size_t N) { // 关键N/321 避免N32时空间为0 _bits.resize(N/321, 0); _num 0; // 记录有效数据个数 } private: std::vectorint _bits; // 存储位数据的整型数组 size_t _num; // 标记的有效数据个数 }; }关键解读空间计算若需要存储 N 个位需开辟N/321个 int而非直接N/32避免 N32 时空间为 0如 N30 时30/3201 后至少分配 1 个 int初始化resize会将数组初始化为 0所有位默认表示 “不存在”。2. 核心接口实现set/reset/test位图的核心操作是 “标记存在” “取消标记” “判断存在”全部通过位运算实现1set标记数值存在置 1void set(size_t x) { size_t index x / 32; // 计算x映射到第几个int size_t pos x % 32; // 计算x在int中的第几位 _bits[index] | (1 pos); // 位或操作仅将pos位设为1不影响其他位 _num; }原理拆解例如 x60index60/321第 2 个 intpos60%3228第 28 位1 pos构造 “仅第 28 位为 1” 的掩码与_bits[index]做或运算即可将第 28 位置 1。2reset取消数值标记置 0void reset(size_t x) { size_t index x / 32; size_t pos x % 32; // 位与操作先取反掩码仅pos位为0再与运算将pos位置0 _bits[index] ~(1 pos); _num--; }原理拆解~(1 pos)会生成 “除 pos 位外全为 1” 的掩码与运算后只有 pos 位会被置 0其他位保持不变。3test判断数值是否存在bool test(size_t x) { size_t index x / 32; size_t pos x % 32; // 与运算仅保留pos位的值非0则存在0则不存在 return _bits[index] (1 pos); }原理拆解若 pos 位为 1与运算结果非 0返回 true若为 0结果为 0返回 false位运算效率极高时间复杂度为O(1)。3. 关键注意事项位运算优先级移位运算优先级低于取反~和加减必须加括号如~(1 pos)而非~1 pos大小端无关移位操作是逻辑层面的与内存的大小端存储无关编译器会自动处理边界处理空间计算N/321最多浪费 31 个位现代计算机中可忽略不计若追求极致空间可改用vectorchar计算N/81最多浪费 7 个位。三、位图的实战应用不止于判存位图的核心优势是 “空间效率” 和 “时间效率”除了 40 亿整数判存还有这些经典场景1. 整型数据排序 去重原理遍历所有数值存在的数值标记为 1再遍历位图输出所有标记为 1 的位置自然得到有序且去重的结果效率时间复杂度O(n)空间复杂度仅需位图大小远优于传统排序算法。2. 集合运算交集 / 并集并集两个位图的位或运算bits1 | bits2交集两个位图的位与运算bits1 bits2差集位图 1 与位图 2 取反后的位与运算bits1 ~bits2。3. 操作系统底层应用标记磁盘块的使用状态已分配 / 空闲进程调度中的资源标记如文件描述符的占用状态。四、位图的局限性与扩展1. 核心局限仅支持整型数据位图是 “数值→位” 的直接映射无法直接处理字符串、结构体等非整型数据空间浪费若数据稀疏且范围极大如仅存储 1 和 10 亿两个数位图仍需开辟 10 亿位空间造成浪费。2. 扩展双位标记法统计出现次数如果需要统计数值出现的次数如找出只出现一次的数可将 1 个位扩展为 2 个位00未出现01出现 1 次10/11出现多次优势仅需双倍位空间即可完成海量数据的频次统计远优于哈希表。五、完整测试示例#pragma once #include vector namespace sicheng { class bitset { public: bitset(size_t N) { _bits.resize(N/321, 0); _num 0; } void set(size_t x) { size_t index x / 32; //算出映射的位置再第几个整型 size_t pos x % 32; //算出x再整形的第几个位 _bits[index] | (1 pos); //将第pos个位置成1 表示该位存在x这个数据 _num; //_bits[index] _bits[index] |(1 pos); } void reset(size_t x) { size_t index x / 32; //算出映射的位置再第几个整型 size_t pos x % 32; //算出x再整形的第几个位 _bits[index] ~(1 pos); //将第pos给位置成0 _num--; //_bits[index] _bits[index] (~(1 pos)); } //判断x在不在也即是说x映射的位是否为1 bool test(size_t x) { size_t index x / 32; //算出映射的位置再第几个整型 size_t pos x % 32; //算出x再整形的第几个位 //如果该位为1则除该位外都置成0 相反的该位为0则全部置成0 0就是false 非0就是true return _bits[index] (1 pos); } private: //int* _bits; std::vectorint _bits; size_t _num; //映射存储了多少个数据 }; void test_bitset() { bitset bs(100); // 开辟100位空间4个int bs.set(98); bs.set(99); bs.set(5); bs.reset(99); // 遍历测试所有位 for (size_t i 0; i 100; i) { printf([%d]:%d\n, i, bs.test(i)); } } }输出结果仅 5 和 98 的位置为 199 的位置为 0其余均为 0。总结位图是 “空间换时间” 思想的极致体现核心要点如下核心原理用二进制位标记数值状态空间复杂度仅为O(N/8)N 为数值范围核心操作通过位运算实现 set/reset/test时间复杂度均为O(1)适用场景海量整型数据的存在性判断、排序去重、集合运算扩展方向双位标记法可解决频次统计问题布隆过滤器可解决非整型数据判存问题。 我是思成若这篇内容帮你理清了位图的底层实现与海量数据应用逻辑 【关注】跟我一起拆解数据结构核心知识点从位图的位运算实现到布隆过滤器扩展吃透每一个空间优化技巧❤️ 【点赞】让技术干货被更多人看见让 40 亿整数判存的内存难题用 500MB 空间轻松解决⭐ 【收藏】把位图的 set/reset/test 接口实现、双位标记法存好海量数据判重 / 排序去重面试时随时查阅 【评论】分享你使用位图处理大规模整型数据时踩过的坑或想深挖的位图扩展场景一起交流进步技术学习没有捷径但找对思路能少走弯路愿我们都能把位图的空间压缩思想转化为可落地的海量数据处理代码一步步构建高效的算法体系