文档章节

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

 木宛城主
发布于 2015/03/02 19:43
字数 831
阅读 22
收藏 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
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
【BAT面试现场】如何判断一个数是否在40亿个整数中?

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

CSDN程序人生
08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

GO 数组相关操作

package mainimport("fmt""math/rand""time")func main() {//数组的几种定义方式var arr1 [3]int = [3]int{1,2,3}var arr2 = [3]int{4,5,6}arr3 := [3]string{"h", "w", ......

汤汤圆圆
25分钟前
0
0
JAVA 中interrupt、interrupted和isInterrupted的区别

首先,我们说明下三个方法的功能 interrupt() 向当前调用者线程发出中断信号 isinterrupted() 查看当前中断信号是true还是false interrupted() 是静态方法,查看返回当前中断信号并将中断信号...

我爱春天的毛毛雨
29分钟前
0
0
Coding and Paper Letter(二十二)

资源整理。 1 Coding: 1.开源项目openeo api。oponEO开发了一个开放的API,以简单统一的方式将R,python和javascript客户端连接到对地观测大数据云平台的后台。 此存储库包含此API,即oponE...

胖胖雕
55分钟前
1
0
RxJS的另外四种实现方式(三)——性能最高的库

接上篇 RxJS的另外四种实现方式(二)——代码最小的库(续) 代码最小的库rx4rx-lite虽然在性能测试中超过了callbag,但和most库较量的时候却落败了,于是我下载了most库,要解开most库性能...

一个灰
今天
4
0
马太效应

马太效应

yizhichao
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部