文档章节

浪客剑心:位图法Bitmap算法分析

 木宛城主
发布于 2015/03/02 19:43
字数 831
阅读 23
收藏 0

看了博客园里一篇文章《一道腾讯前端试题,谁来试试身手》,正好以前了解过位图法,确实不错。位图法适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在,如可标记1为存在,0为不存在。

  位图法网上资料比较少,我在百度百科找到了对它的描述


位图法比较适合于如下这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数,遇到几就给新数组的第几位置上1,如遇到 5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

 

  效率测试(参考一道腾讯前端试题,谁来试试身手):

  传统的双重循环查找也是可取的,但效率实在不敢恭维,特别是处理大量数据时候

  

class Program
    {
        static void Main(string[] args)
        {

            //产生随机数
            int[] array = Enumerable.Range(1, 100000).OrderBy
(n => Guid.NewGuid()).Take(80000).ToArray();
      
            DateTime dt1 = DateTime.Now;

            int max = array[0];
            int flag;
            //数组无序排列,查找最大值
            for (int i = 1; i < array.Length; i++)
            {
                if (array[i] > max)
                {
                    max = array[i];
                }
            }
            for (int i = 1; i <= max; i++)
            {
                flag = 1;
                for (int j = 0; j < array.Length; j++)
                {
                    //相等标记Flag=0,意味着不是缺少的数字
                    if (i.Equals(array[j]))
                    {
                        flag = 0;
                        break;
                    }

                }
                if (flag == 1)
                {
                    Console.Write("{0},", i);
                }

            }
            DateTime dt2 = DateTime.Now;
            TimeSpan ts = dt2 - dt1;
            Console.WriteLine("\r\n" + "共耗时间{0}ms", ts.TotalMilliseconds);//52730.5525
            Console.ReadKey();
        }
    }

测试结果:数据量小时,还OK,数据量大的情况下,显示很卡很缓慢,最坏的时间复杂度:T(n)=O(n*n)

以上测试,总时间约为:51291.2996MS

位图法测试

class Program
    {
        static void Main(string[] args)
        {


            //随即产生80000个不重复数
            int[] array = Enumerable.Range(1, 100000).OrderBy
(n => Guid.NewGuid()).Take(80000).ToArray();
          
            //int[] array={1,2,3,5,7,9,10,12,45,62,55,78,98,52,12,4,200,60,63,65,66,67,68,69,70,74,79,80,82,89,90,91,92,93,94,98,100,101};
            DateTime dt1=DateTime.Now;
            
            //找出最大值
            int max=array[0];
            for (int i = 1; i < array.Length; i++)
            {
                if (array[i]>max)
                {
                    max = array[i];
                }
            }
            //新数组的长度为旧数组最大数字+1
            int[] lose=new int[max+1];
            foreach (int item in array)
            {
                //若Item为2,则Lose[2]=1...所以新数组的长度为旧数组最大数字+1
                lose[item] = 1;
            }
            //那么为0的就是缺少值
            for (int i = 1; i < lose.Length; i++)//100
            {
                if (lose[i].Equals(0))
                {
                    Console.Write("{0},",i);
                }
            }
            DateTime dt2=DateTime.Now;
            Console.WriteLine("\r\n"+(dt2-dt1).TotalMilliseconds);//6004.3379Ms
            Console.ReadKey();

        }
    }

位图法在确定最大数值后的时间复杂度还是挺乐观的,最坏情况:T(n)=O(2n)

屏幕飞快的刷新着,测试时间约是:6295.3601MS

总结

判断集合中是否存在重复元素或者查找缺失元素是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可,位图法Bitmap可以考虑。

© 著作权归作者所有

共有 人打赏支持
粉丝 2
博文 222
码字总数 199010
作品 0
黄浦
私信 提问
大数据处理算法一:Bitmap算法

腾讯面试题:给20亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中并且所耗内存尽可能的少? 解析:bitmap算法就好办多了 所谓bitmap,...

超人学院
2015/04/29
0
2
RT-Thread的位图调度算法分析

RT-Thread的内核调度算法 rt-thread的调度算法为基于优先级调度和基于时间片轮转调度共存的策略。rt-thread内核中存在多个线程优先级,并且支持多个线程具有同样的线程优先级。线程级别数目在...

RTThread物联网操作系统
07/31
0
0
如何判断一个数是否在40亿个整数中

【面试现场】 题目:我有40亿个整数,再给一个新的整数,我需要判断新的整数是否在40亿个整数中,你会怎么做? 【请教大神】 小史回到学校,把面试的情况和计算机学院的吕老师说了一下。 小史...

Ocean_K
09/05
0
0
bitmap的六种压缩方式,Android图片压缩

转载请注明出处,谢谢:http://blog.csdn.net/harryweasley/article/details/51955467 Android中图片是以bitmap形式存在的,那么bitmap所占内存,直接影响到了应用所占内存大小,首先要知道b...

guozhendan
06/26
0
0
【BAT面试现场】如何判断一个数是否在40亿个整数中?

点击上方“程序人生”,选择“置顶公众号” 第一时间关注程序猿(媛)身边的故事 作者 channingbreeze 如需转载,请联系原作者授权。 小史是一个应届生,虽然学的是电子专业,但是自己业余时...

CSDN程序人生
08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Go 使用channel控制并发

前言 channel一般用于协程之间的通信,channel也可以用于并发控制。比如主协程启动N个子协程,主协程等待所有子协程退出后再继续后续流程,这种场景下channel也可轻易实现。 场景示例 总结 ...

恋恋美食
24分钟前
1
0
Apache Flink 漫谈系列 - 持续查询(Continuous Queries)

摘要: 实际问题 我们知道在流计算场景中,数据是源源不断的流入的,数据流永远不会结束,那么计算就永远不会结束,如果计算永远不会结束的话,那么计算结果何时输出呢?本篇将介绍Apache Fl...

阿里云官方博客
27分钟前
4
0
斐波那契堆的理解,节点mark属性和势函数

斐波那契堆 看了好多博客,都是照搬算法导论的内容,没有自己的理解,比如为什么有mark属性,势函数的作用,以及为什么叫斐波那契堆,下面说说鄙人的理解。 势函数 势函数是根节点个数加上2...

杨喆
28分钟前
3
0
NIO源码详解

阻塞io和无阻塞io: 阻塞io是指jdk1.4之前版本面向流的io,服务端需要对每个请求建立一堆线程等待请求,而客户端发送请求后,先咨询服务端是否有线程相应,如果没有则会一直等待或者遭到拒 ...

沉稳2018
33分钟前
0
0
如何把已经提交的commit, 从一个分支放到另一个分支

在本地master提交了一个commit(8d85d4bca680a5dbcc3e5cfb3096d18cd510cc9f),如何提交的test_2分之上? git checkout test_2git cherry-pick 8d85d4bca680a5dbcc3e5cfb3096d18cd510cc9f......

stephen_wu
36分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部