前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >浪客剑心:位图法Bitmap算法分析

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

作者头像
用户1161731
发布2018-01-11 12:54:37
1.2K0
发布2018-01-11 12:54:37
举报
文章被收录于专栏:木宛城主

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

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

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

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

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

代码语言:javascript
复制
 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

位图法测试

代码语言:javascript
复制
  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可以考虑。。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2012-07-12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  •  位图法网上资料比较少,我在百科找到了对它的描述
  •   传统的双重循环查找也是可取的,但效率实在不敢恭维,特别是处理大量数据时候
  • 位图法测试
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档