数据结构与算法专题——第一题 Bitmap算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法专题——第一题 Bitmap算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5254字，纯文字阅读大概需要8分钟。

内容图文

在所有具有性能优化的数据结构中，我想大家使用最多的就是hash表，是的，在定位查找场景上具有O(1)的常量时间，多么的简洁优美，

但是在特定的场合下：

①：对10亿个不重复的整数进行排序。

②：找出10亿个数字中重复的数字。

当然我只有普通的服务器，就算2G的内存吧，在这种场景下，我们该如何更好的挑选数据结构和算法呢？

一：问题分析

这年头，大牛们写的排序算法也就那么几个，首先我们算下放在内存中要多少G: (10亿 32)/(1024102410248)=3.6G，可怜的2G内存直接爆掉，所以各种神马的数据结构都玩不起来了，当然使用外排序还是可以解决问题的，由于要走IO所以暂时剔除，既然是数据结构和算法，所以高性能是必须的，想想可不可以在二进制位上做些手脚？比如我要对 {1,5,7,2} 这四个byte类型的数字做排序，该怎么做呢？大家知道byte是占用8bit，转变思路可以将数组中的值作为bit位的key，value用”0，1“来标识该key是否出现过？下面看图：

从图中我们精彩的看到，数组值都已经作为byte中的key了，最后我只要遍历对应的bit位是否为1就可以了，那么自然就成了有序数组。可能有人说，我增加一个13怎么办？很简单，一个字节可以存放8个数，那两个byte是不是就可以存16个数？刚好了覆盖了13个，画图如下：

可以看出我将一个线性的数组变成了一个bit位的二维矩阵，最终需要的空间仅仅是:3.6G/32=0.1G即可，要注意的是bitmap排序不是O(N)的，而是取决于待排序数组中的最大值，有时候必须要加速的话，可以开10个线程去读byte数组，那么复杂度为:O(Max/10)。

二：代码

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

1:Clear方法（将数组的所有bit位赋值0）

比如要将当前4对应的bit位赋值0的话，只需要1左移4位取反与B[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);
 ? ? ? ?}

2:Add方法（将bit置1操作）

同样也很简单，要将当前4对应的bit位赋值1的话，只需要1左移4位与B[0] | 即可。

 ? ? ? /// <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;
 ? ? ? ?}

3:Contain方法（判断当前bit位是否是1）

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

 ? ? ? /// <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;
 ? ? ? ?}

4. 最后上总的代码：

 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
 ? ? }
 }

非常简单的一个数据结构，您学会了吗？

内容总结

以上是互联网集市为您收集整理的数据结构与算法专题——第一题 Bitmap算法全部内容，希望文章能够帮你解决数据结构与算法专题——第一题 Bitmap算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---