经典算法题每日演练——第十一题 Bitmap算法-阿里云开发者社区

开发者社区> 人工智能> 正文

经典算法题每日演练——第十一题 Bitmap算法

简介: 原文:经典算法题每日演练——第十一题 Bitmap算法      在所有具有性能优化的数据结构中,我想大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美, 但是在特定的场合下: ①:对10亿个不重复的整数进行排序。
原文:经典算法题每日演练——第十一题 Bitmap算法

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

但是在特定的场合下:

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

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

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

 

一:问题分析

     这年头,大牛们写的排序算法也就那么几个,首先我们算下放在内存中要多少G: (10亿 * 32)/(1024*1024*1024*8)=3.6G,可怜

的2G内存直接爆掉,所以各种神马的数据结构都玩不起来了,当然使用外排序还是可以解决问题的,由于要走IO所以暂时剔除,因为我们

要玩高性能,无望后我们想想可不可以在二进制位上做些手脚?  

比如我要对{1,5,7,2}这四个byte类型的数字做排序,该怎么做呢?我们知道byte是占8个bit位,其实我们可以将数组中的值作为bit位的

key,value用”0,1“来标识该key是否出现过?下面看图:

从图中我们精彩的看到,我们的数组值都已经作为byte中的key了,最后我只要遍历对应的bit位是否为1就可以了,那么自然就成有序数组了。

可能有人说,我增加一个13怎么办?很简单,一个字节可以存放8个数,那我只要两个byte就可以解决问题了。

可以看出我将一个线性的数组变成了一个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] & 即可。

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

 

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

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

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

 

2:Contain方法(判断当前bit位是否是1)

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

 1         #region 判断当前的x在数组的位中是否存在
 2         /// <summary>
 3         ///判断当前的x在数组的位中是否存在
 4         /// </summary>
 5         /// <param name="i"></param>
 6         /// <returns></returns>
 7         static bool Contain(byte i)
 8         {
 9             var j = a[i >> 3] & (1 << (i & 0x07));
10 
11             if (j == 0)
12                 return false;
13             return true;
14         }
15         #endregion

最后上总的代码:

View Code
 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Diagnostics;
 6 using System.Threading;
 7 using System.IO;
 8 
 9 namespace ConsoleApplication2
10 {
11     public class Program
12     {
13         static byte n = 7;
14 
15         static byte[] a;
16 
17         public static void Main()
18         {
19             //节省空间的做法
20             a = new byte[(n >> 3) + 1];
21 
22             for (byte i = 0; i < n; i++)
23                 Clear(i);
24 
25             Add(4);
26             Console.WriteLine("插入4成功!");
27 
28             var s = Contain(4);
29 
30             Console.WriteLine("当前是否包含4:{0}", s);
31 
32             s = Contain(5);
33 
34             Console.WriteLine("当前是否包含5:{0}", s);
35 
36             Console.Read();
37         }
38 
39         #region 初始化所用的bit位为0
40         /// <summary>
41         /// 初始化所用的bit位为0
42         /// </summary>
43         /// <param name="i"></param>
44         static void Clear(byte i)
45         {
46             //相当于 i%8 的功能
47             var shift = i & 0x07;
48 
49             //计算应该放数组的下标
50             var arrindex = i >> 3;
51 
52             //则将当前byte中的指定bit位取0,&后其他对方数组bit位必然不变,这就是 1 的妙用
53             var bitPos = ~(1 << shift);
54 
55             //将数组中的指定bit位置一  “& 操作”
56             a[arrindex] &= (byte)(bitPos);
57         }
58         #endregion
59 
60         #region 设置相应bit位上为1
61         /// <summary>
62         /// 设置相应bit位上为1
63         /// </summary>
64         /// <param name="i"></param>
65         static void Add(byte i)
66         {
67             //相当于 i%8 的功能
68             var shift = i & 0x07;
69 
70             //计算应该放数组的下标
71             var arrindex = i >> 3;
72 
73             //将byte中的 1 移动到i位
74             var bitPos = 1 << shift;
75 
76             //将数组中的指定bit位置一  “| 操作”
77             a[arrindex] |= (byte)bitPos;
78         }
79         #endregion
80 
81         #region 判断当前的x在数组的位中是否存在
82         /// <summary>
83         ///判断当前的x在数组的位中是否存在
84         /// </summary>
85         /// <param name="i"></param>
86         /// <returns></returns>
87         static bool Contain(byte i)
88         {
89             var j = a[i >> 3] & (1 << (i & 0x07));
90 
91             if (j == 0)
92                 return false;
93             return true;
94         }
95         #endregion
96     }
97 }

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章