×
新网 > 建站推广 > 正文

一个从四秒到10毫秒 花了1年的算法问题?

五一后的第一周,由于搬家腰扭伤了,没注意导致压迫神经,躺在床上休息了好几天。所以没事就挂 QQ,一个网友突然问了我一个算法问题。所以有了这篇文章。感触很深,所以特发此文,以纪念和写给新朋友,以及那些热爱编程的非专业人事。本人可能技术含量很低,但都很真实。虽然我只花了很少的时间,但解决了这个网友困惑了1年的问题,这个网友倒是特别感激,而我倒是感觉特别心塞。那大家喝杯茶,看看这个过程吧。

编程语言 算法优化 编程语言算法

特别注意:本文的算法问题对很多专业计算机的人来说,很简单,但是注意看文章的人物背景。

五一后的第一周,由于搬家腰扭伤了,没注意导致压迫神经,躺在床上休息了好几天。所以没事就挂 QQ,一个网友突然问了我一个算法问题。所以有了这篇文章。感触很深,所以特发此文,以纪念和写给新朋友,以及那些热爱编程的非专业人事。本人可能技术含量很低,但都很真实。虽然我只花了很少的时间,但解决了这个网友困惑了1年的问题,这个网友倒是特别感激,而我倒是感觉特别心塞。那大家喝杯茶,看看这个过程吧。

1.人物背景

这个网友我也是后来聊天才了解到他的情况。他是1个1977年出生的湖北网民,为了分析相关数据,自学了VB.NET,这个年龄的人还学了这个,真的不容易,而且能够用VB.NET开发比较复杂的数据分析界面。其实后来了解到这些,自愧不如啊。所以对算法问题,这个朋友遇到困难,也可以理解。

其实这个朋友很早就是我的QQ好友,也知道都是做数据分析,所有我有新的算法方面的文章会发给他看,偶尔聊一下,但没有问过我问题。上个月发表了一篇文章:机器学习之PageRank算法应用与C#实现(1)算法介绍,发表之后,他看到后,才问我这个问题。

我:其实我也是个半吊子,对算法也不精通,只是业余研究感兴趣而已。。说实话你要我写个二分搜索,我一时半会还搞不定,但我看看论文和资料,可以写个马尔可夫链或者贝叶斯之类的。。。这个东西怎么说呢,在很多问题中,空间效率和时间效率,特别是在硬件条件如此富裕的情况下,可以考虑得更少一点。。当然这里绝对不是说算法是没有用的,只是对很多非常普通的人来说,研究的规模太小,而且由于经验和特殊原因,没有算法和数据结构基础,只能不考虑了,以解决实际问题为主吧。

2.原始问题

该网友的原始问题是这样的,我从QQ聊天记录里直接Copy过来:

有两组随机生成的(0~99999)Int32数据A和B,将A按顺序判断在B中是否存在并记录在Boolean型的C中,我分别尝试了Array与List(Of T),在VS2010下以我的破电脑的速度Array大概需要4秒,而List(Of T)则要24秒,以下是我用Array和List(of T)的代码,请高手指点, 顺便问下有无秒杀的方法。(注:他的VB代码我就不贴了,思路知道就可以了)

帮我看看用什么方法解决,谢谢

有人说用哈希,可惜我不会,也没百度到

他的开发环境是VS2010 + VB.NET

我收到他的消息的时候是正在用手机QQ上的,他还贴了段VB的代码,我是比较反感直接贴代码的人。不过当时躺在床上,也没啥事,好奇嘛,就仔细看了一下这个问题,代码真的没看。

3.解决问题的过程

由于是手机上的,所以也没开电脑敲代码。就想了一下。

网友的原始代码中的比较都是使用Array.IndexOf,可以想象7万的数组,速度慢也正常 。

1.首先我是把哈希给否定了的。其实后来想起来,是我错了,我以为他说的哈希是把每个元素求哈希值后对比,这不是多此一举么。。本来计算哈希就要时间,还是要比较。。。那何必呢。。。后来我才想到,他说的可能是“哈希表”,这是后话,不提了,哈希表这个方法怎么样不知道,应该也还可以吧;但还是先看看我的方法。

2.我当时先给了他一个初步的方案,解决问题有时候不是一步到位的,先试试看咯。我的想法是使用IndexOf查找会浪费很多时间。所以,你先把B排序,或者B在实际构造过程中就可以进行排序存储,然后A依次对比的时候,采用二分法搜索,甚至有条件,A也可以先排序,然后搜索的时候记录起点,二分法搜索,这样可以节省不少时间。A和B排序的问题,其实根据他的情况,是可以在实际过程中就排序好的,而不是生成后排序,这样就更费时间了。

这个网友也很迅速,过了大概1个小时,测试出来说:“我用的随机数测试了下,速度提升相当明显,比Array.indexof要快多了”

3.上面手机沟通不方便,也就随便说了一下,没想到他很快做出来了。虽然快了很多,但具体时间我也没问。然后我洗澡的时候,感觉这个问题不是那么回事,我以前貌似也做过类似的,应该还有更快的方法。然后洗澡过程中,思考了若干秒。。。一个思路也有了,虽然这个想法我感觉很土,但我想实际效果应该很好,所以洗完澡,马上开电脑,跟网友说了一下思路,考虑到他有可能无法理解算法的伪代码或者比较严格的表述(实际上我也不知道该怎么严格表述),所以就直接打了一个比方,在这里为了方便大家理解,我先大概写了个思路,应该会看得懂吧。至于问题中的记录在C中,我具体没问他怎么记录,其实这和问题关系不大,核心在前面如何确定是否包括:

编程语言 算法优化 编程语言算法

我给那位网友是这么打比方的(原始有点乱,我写博客的时候稍微整理了下),不知道大家有没有歧义,感觉还是上面的伪代码容易理解,但是开心的是,这个网友还是理解了 :

A数组:不管,随意,也不用排序, B数组:[5,2,4,1],假设最大为5,注意没有3 初始化一个长度为5(最大数)的布尔数组:a[1],[2],[3],[4],[5] 循环B,将B中值作为a的下标,对应位置标记为true,例如 a[5]= true; a[2]= true; a[4]= true; a[1]= true; 注意a[3]没有,为false 最后循环A,直接对比下标,如果A={2,3},那么: a[2]=true,说明存在,则C[2]=true,到C中标记true a[3]=false,则没有。C中标记为false 如果你最大为99999,那么这个数组要这么长你可以直接设置为99999,浪费一点空间; 如果你业务中可以直接求出最大值,那是最好的了。自己试一试。

这个思路理解了非常简单。这个网友也很快理解了,过了一会就把他的结果告诉我了。

下降到10毫秒左右,他把数据扩大到10万,速度也挺快的。

4.后记与C#实现

解决他的问题后,第二天我们又聊了一会,他表示很感谢,说这个方法速度非常快。说这1年来,他问过很多人,也找过很多计算机方面的人,但效果都不好。。。

据说还问过一个拿过什么微软认证的人。。。说他的电脑不行,要去换一下。。。这个有点过份操蛋了。。才几万的数组,能耗多少内存,都是简单的比较计算,需要很好的CPU么。。。

后来我也给他分析过说,其他人可能没有完全理解你的问题,都一根筋考虑效率和速度的问题了,所以考虑的东西多了,给你的建议也不一定合适。对这些小问题,牺牲一点空间,何况又不多,而且内存也便宜,现在动不动2G,4G。。换时间也是够划算的。我这里说的空间,是直接初始化数组C的长度包括所有的数字个数,因为我也不了解他实际的数据怎么来的,当然如果能计算最大值,肯定最好了。这样稍微计算一下时间复杂度,循环2遍就能解决问题。至于我第一次提到的排序和二分法的问题,也只是刚开始想到的,没有更深入的思考,因为也是考虑到他的数据是可以在生成的时候就进行排序的,这样也可以省时间,而不是所有的都IndexOf,不慢才怪。

4.1 C#代码实现原始方法

闲的没事,我用C#实现了一下网友原始的方法,代码如下:

static void ValidateArrayElement2() { Stopwatch sp = new Stopwatch(); sp.Start(); //开始计时 Random rand = new Random(); Int32 maxValue = 120000; //元素最大值,是一个假定值 Int32 length = 70000; // A,B的长度 Int32[] A = new Int32[length]; Int32[] B = new Int32[length]; Boolean[] C = new Boolean[length]; //随机初始化A,B数组 for (int i = 0; i < length; i++) { A[i] = rand.Next(maxValue); B[i] = rand.Next(maxValue); } //循环A,验证是否存在,将C对应位置标记为true for (int i = 0; i < A.Length; i++) if (B.Contains(A[i])) C[i] = true; sp.Stop(); Console.WriteLine(sp.ElapsedMilliseconds); }

测试了下,我机器是X200+T9400,3G内存。加上数据初始化总共时间是4.3秒,所以实际的时间是4秒左右,和网友的结论是差不多的。看看我下面的方法:

4.2 C#代码实现上述算法

使用第3节提出的方法,我测试一下时间:

static void ValidateArrayElement() { Stopwatch sp = new Stopwatch(); sp.Start(); Random rand = new Random(); Int32 maxValue = 120000; //元素最大值,是一个假定值 Int32 length = 70000; // A,B的长度 Int32[] A = new Int32[length]; Int32[] B = new Int32[length]; Boolean[] C = new Boolean[length]; Boolean[] Atemp = new Boolean[maxValue]; //临时的辅助变量 //随机初始化A,B数组 for (int i = 0; i < length; i++) { A[i] = rand.Next(maxValue); B[i] = rand.Next(maxValue); } //循环B,验证元素是否存在 foreach (var item in B) Atemp[item] = true; //循环A,验证是否存在,将C对应位置标记为true for (int i = 0; i < A.Length; i++) if (Atemp[A[i]]) C[i] = true; sp.Stop(); //停止计时 Console.WriteLine(sp.ElapsedMilliseconds); }

实际时间只有5ms左右,如果不算数据初始化的时间,基本只有1ms,和网友的10ms有点差别,可能和机器有关吧。总的来说,速度的确是提高了不少。

至于所谓的哈希表方法,这里就不实现了,已经够快了。

最后感谢那些和我一样,热爱编程的业余人事。。。虽然我们不是正规军,虽然我们没有学过数据结构,也没有系统学习过专业的算法课程,没有接受过专业的编程培训,但只要细心和动脑筋,解决一些小规模的问题,还是可以的。至于那些大量数据的效率问题,算法问题就交给大牛吧。

剩下的时间交给网友,这个问题简单吗?你会怎么解决?期待评论有更好更佳的答案。。。如果是喷,说问题简单那就算了吧,没必要,何苦为难我呢。。。

4.3 HashSet测试

感谢passer.net网友,说用HashSet,这个类以前知道,但很少用,既然提出来了,就测试一下,代码如下:

Stopwatch sp = new Stopwatch(); sp.Start(); Random rand = new Random(); Int32 length = 70000; // A,B的长度 Int32[] A = new Int32[length]; Int32[] B = new Int32[length]; Boolean[] C = new Boolean[length]; var tmp = new HashSet<int>(); //随机初始化A,B数组 for (int i = 0; i < length; i++) { A[i] = rand.Next(); B[i] = rand.Next(); if (!tmp.Contains(B[i])) tmp.Add(B[i]); } //循环A,验证是否存在,将C对应位置标记为true for (int i = 0; i < A.Length; i++) C[i] = tmp.Contains(A[i]); sp.Stop(); //停止计时 Console.WriteLine(sp.ElapsedMilliseconds);

测试了一下,大约17ms,比文章的方法稍微慢了一点,但也非常快了,在一个数量级水平吧。可能哈希表对其他复杂的类似数据或者大数据量更管用。不过无所谓了,都是方法,都能解决问题,不必纠结这些细节。

 

  • 相关专题

免责声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,也不承认相关法律责任。如果您发现本社区中有涉嫌抄袭的内容,请发送邮件至:operations@xinnet.com进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。

免费咨询获取折扣

Loading