一个从四秒到10毫秒 花了1年的算法题目?语言&工具

来源:互联网 / 作者:SKY / 2017-12-01 05:44 / 点击:
五一后的第一周,因为搬迁腰扭伤了,没留意导致压制神经,躺在床上苏息了好几天。以是没事就挂 QQ,一个网友溘然问了我一个算法题目。以是有了这篇文章。感伤很

五一后的第一周,因为搬迁腰扭伤了,没留意导致压制神经,躺在床上苏息了好几天。以是没事就挂 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#代码实现原始要领

阅读延展

1
3