文档章节

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

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

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

李序锴
2017/11/08
0
0
1.1.0-学习Opencv与MFC混合编程之---全屏截图,保存为BMP图像(并增加快捷键)

源代码:http://download.csdn.net/detail/nuptboyzhb/3961677 Ø 添加全屏截图菜单项,菜单项的属性如下; Ø 为该菜单项建立类向导。 编辑消息处理函数如下 voidCCVMFCView::OnPrintscreen(...

长平狐
2012/10/08
1K
0
bitmap的六种压缩方式,Android图片压缩

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

guozhendan
06/26
0
0
求爱程序代码一览-------C语言篇

开发环境,visual studio code: result love(boy, girl)       {       if( boy.有房() and boy.有车() )       {       boy.set(nothing); return girl.嫁给(boy)...

crossmix
2015/12/16
418
0
《编程珠玑,字字珠玑》1234读书笔记——多路归并排序

写在前面的 2012年3月25日买下《编程珠玑》,很期待但不知道它能给我带来什么! 编程珠玑,字字珠玑。但是翻译有点拗口,有时候整句话读下来都不知道在讲什么,多少有点掩饰了珠玑的魅力,真...

xumaojun
04/09
0
0
数据结构-位图(可对海量数据进行处理)

在学习linux过程中,wait函数中的status参数的用法其实就如同位图,位图法就是bitmap的缩写。所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常...

sssssuuuuu666
2017/12/07
0
0
Javascript的bitmap处理库--jsBitmap

基于Javascript的bitmap处理,并且将位图输出为base64编码以便于浏览器进行显示。 一、Bitmap.create(width, height, bgcolor) 创建一个width x height像素大小的位图,底色为bgcolor所代表的...

matrixy
2013/08/26
1K
1
Android java.lang.OutOfMemoryError: bitmap 解决方法

BitmapFactory.Options.inSampleSize 设置恰当的inSampleSize可以使BitmapFactory分配更少的空间以消除该错误。inSampleSize的具体含义请参考SDK文档。例如: 如何设置恰当的inSampleSize 设...

SRain215
2015/12/03
40
0
Bitmap.createBitmap函数有6个重载方法

  位图剪切参考重载方法4和6,重载方法6比较简单 public static Bitmap createBitmap (Bitmap src) 从原位图src复制出一个新的位图,和原始位图相同 public static Bitmap createBitmap (i...

天下杰论
2013/11/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

idea tomcat 远程调试

tomcat 配置 编辑文件${tomcat_home}/bin/catalina.sh,在文件开头添加如下代码。    CATALINA_OPTS="-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=7829" Idea端配......

qwfys
今天
1
0
遍历目录下的文件每250M打包一个文件

#!/usr/bin/env python # -*- utf-8 -*- # @Time : 2018/7/20 0020 下午 10:16 # @Author : 陈元 # @Email : abcmeabc@163.com # @file : tarFile.py import os import tarfile import thr......

寻爱的小草
今天
1
0
expect同步文件&expect指定host和要同步的文件&构建文件分发系统&批量远程执行命令

20.31 expect脚本同步文件 expect通过与rsync结合,可以在一台机器上把文件自动同步到多台机器上 编写脚本 [root@linux-5 ~]# cd /usr/local/sbin[root@linux-5 sbin]# vim 4.expect#!/...

影夜Linux
今天
0
0
SpringBoot | 第九章:Mybatis-plus的集成和使用

前言 本章节开始介绍数据访问方面的相关知识点。对于后端开发者而言,和数据库打交道是每天都在进行的,所以一个好用的ORM框架是很有必要的。目前,绝大部分公司都选择MyBatis框架作为底层数...

oKong
今天
12
0
win10 上安装解压版mysql

1.效果 2. 下载MySQL 压缩版 下载地址: https://downloads.mysql.com/archives/community/ 3. 配置 3.1 将下载的文件解压到合适的位置 我最终将myql文件 放在:D:\develop\mysql 最终放的位...

Lucky_Me
今天
1
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

问题终结者
今天
1
0
expect脚本同步文件expect脚本指定host和要同步的文件 构建文件分发系统批量远程执行命令

expect脚本同步文件 在一台机器上把文件同步到多台机器上 自动同步文件 vim 4.expect [root@yong-01 sbin]# vim 4.expect#!/usr/bin/expectset passwd "20655739"spawn rsync -av ro...

lyy549745
今天
1
0
36.rsync下 日志 screen

10.32/10.33 rsync通过服务同步 10.34 linux系统日志 10.35 screen工具 10.32/10.33 rsync通过服务同步: rsync还可以通过服务的方式同步。那需要开启一个服务,他的架构是cs架构,客户端服务...

王鑫linux
今天
0
0
matplotlib 保存图片时的参数

简单绘图 import matplotlib.pyplot as pltplt.plot(range(10)) 保存为csv格式,放大后依然很清晰 plt.savefig('t1.svg') 普通保存放大后会有点模糊文件大小20多k plt.savefig('t5.p...

阿豪boy
今天
2
0
java 8 复合Lambda 表达式

comparator 比较器复合 //排序Comparator.comparing(Apple::getWeight);List<Apple> list = Stream.of(new Apple(1, "a"), new Apple(2, "b"), new Apple(3, "c")) .collect(......

Canaan_
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部