首页 > 语言 > 关键词 > 编程语言最新资讯 > 正文

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

2015-08-31 14:41 · 稿源:cnblogs

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

五一后的第一周,由于搬家腰扭伤了,没注意导致压迫神经,躺在床上休息了好几天。所以没事就挂 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,比文章的方法稍微慢了一点,但也非常快了,在一个数量级水平吧。可能哈希表对其他复杂的类似数据或者大数据量更管用。不过无所谓了,都是方法,都能解决问题,不必纠结这些细节。

  • 相关推荐
  • 大家在看
  • 编程语言最新排名:Java最受欢迎、JS用户最多

    IDE工具开发商JetBrains基于2万名开发者,对编程语言的最新情况进行了统计描摹。就受欢迎程度而言,Java高居第一位,但在使用人数上,JavaScript则名列榜首。欢迎程度的统计方法是,让参与的

  • 报告:JavaScript为最常用整体编程语言 Python超过Java

    在过去的 12 个月中,Python在使用的编程语言列表中已经超过了Java,它也是被研究最多的语言。报告称,在过去的 12 个月里,30%的受访者开始或继续学习Python,甚至比去年还要多。

  • 风变编程:两会丁磊提议将编程纳入考试,编程学习是否已是大势所趋?

    最近,关于编程教育是否纳入教学的讨论再次在网络上发酵,引发了全民大讨论。在5月21日举行的第十三届全国人民代表大会第三次会议上,全国政协委员、网易CEO丁磊在《关于稳步推动编程教育纳入我国基础教学体系,着力培养数字化人才的提案》中建议:加快区域试点,形成从高中向小学、从东部向全国的推广格局;创新教学模式,形成中国特色的少儿编程课程体系;教企共建少儿编程学习资源库,提供实践平台;将少儿编程纳入学业水平考试

  • Java已被超越?Python当道,风变编程带你化身编程高手

    在程序员中,一直流传着“Python除了不会生孩子,什么都会”的传说。作为人工智能时代最重要的脚本语言之一,Python现在已经逐步占领统计学、机器学习、爬虫、图形处理、软件和游戏开发、人工智能等多个领域,且都有突出表现。可以说,在众多编程语言中,python如今已经杀出重围,从容超越Java和Javascript,化身程序员必备的编程利器之一。目前,国内外许多公司都已使用Python,如:YouTube、豆瓣、知乎、Google、百度、腾讯、美?

  • 读懂生命的“语言” 有孚专有云为基因行业提速

    基因图谱被称为"上帝用以创造生命的语言"。世界各国的科学家们都在倾尽全力读懂“生命的语言”,破解每一个未知基因的奥秘。读懂“生命的语言”,对于提高公众健康水平,降低沉重的医疗费用具有非常重要的意义。读懂生命的"语言",实现科学的价值基因技术听起来很神秘,但其实早已经在多个领域中得到应用。例如基因测序技术能够用于疾病的预防、疾病的诊断、指导个体化用药,还能够帮助病毒基因研究所研发病毒诊断试剂,监控病毒疫

  • 用算法寻找肿瘤的分子弱点,代码真的能治愈癌症?

    ruxolitinib试验是哥伦比亚大学系统生物学家Andrea Califano历时十年的追求的产物。通过复杂的计算,他对催化癌细胞的分子网络进行建模,并精确定位到转录因子蛋白作为关键因子,从而控制细胞内许多基因表达。

  • 包装出来的「国标」等级考试,编程猫们收割了谁?

    ​一位一线儿童编程教育工作者称,细数市场十余种等级标准与考试,鱼龙混杂、质量参差不齐,一些感觉不是在推进青少年编程教育,而是在抢占编程教育市场制高点。

  • 极客晨星讲解:火爆的少儿编程有着怎样的发展史?

    未来的世界是人工智能的时代,这个已经成为了不争的事实。而国内近几年来对少儿编程的关注也说明了不少家长也希望孩子能够学习少儿编程,从而适应未来的人工智能。那么少儿编程到底是什么发展起来的呢?国内少儿编程培训的现状又是什么样的?下面极客晨星就为您来详细讲解一下。2000 年以色列编程兴起; 2012 年日本改课推广编程; 2013 年奥巴马呼吁全国学编程; 2014 年英国把编程纳入必修课; 2015 年美国政府出资 40 亿强化中小学?

  • Python取代Excel?风变编程带你了解如何更好地学Python!

    当前最简单、最流行的编程语言是什么?是Python。最近,谷歌公布的编程语言流行指数显示,Python目前仍然是全球范围内最受欢迎的技术语言。而得益于简洁、易读、易维护等特点,Python可广泛运用于数据分析、人工智能、爬虫、运维、测试、图像识别、机器学习等领域,在日常数据分析方面,甚至已有“Python取代Excel”的说法。那么,Python是否真的有这么牛?接下来,风变编程就带你了解一波。“Python已经取代了Excel”今年3月,日?

  • 去赛马克算法被指歧视黑人 AI学术大牛被喷:退网不玩了

    美国愈演愈烈的BLM黑命贵运动不断扩大,学术圈也不可避免地要被影响到了,前不久某个AI算法将美国前总统奥巴马算成了白人,AI大牛Yann Lecun纯粹从技术角度解释了下这个问题,结果被喷了很久,现

  • 极客晨星实力撩姐,叶一茜大呼:我想给儿子报编程课!

    6 月 20 日晚上,明星辣妈&全能女神叶一茜淘宝直播带货,极力推荐极客晨星编程课。直播当晚,人气爆棚,引起家长共鸣,回响强烈,掀起了一波购课热潮。就连叶一茜也大呼:我想给儿子报编程课!极客晨星实力撩姐,它究竟有什么魅力呢?“早就想给我家儿子报名编程课了,没找到合适的机构,今天推荐一家在线少儿编程——极客晨星。”直播一开始,森蝶妈妈叶一茜就在直播间力推极客晨星。同时,她也谈到了作为一名家长的烦恼。“线下?

  • 张朝阳首次直播推荐亲测好物,少儿编程这个“知识点”亮了

    6 月 8 日晚 7 点,搜狐公司董事局主席兼CEO、搜狐视频CEO张朝阳将首次直播带货。届时,在搜狐视频APP“关注流”中搜索“张朝阳”,即可进入直播间看直播,秒杀亲选限量好物。“想带个货,顺便聊聊生活”。据了解,此次张朝阳在《Charles的好物分享》直播中推荐的物品,都是他生活中长期使用,觉得还不错的东西,同时也是个人的生活方式的一次展示。他强调这次直播带货是“抛砖引玉”,“希望未来带动更多名人来搜狐视频直播。”直

  • 华为全球最大旗舰店上海开业 可提供近10门语言服务

    今日上午10点8分,上海南京东路华为全球最大旗舰店开业,有粉丝表示自己8点多就已过来排队。据悉,该旗舰店坐落于 “中华商业第一街”南京东路的南京大楼,具体位置为上海市南京东路 233 号,占地面积超过了 5000 平方米。

  • 编程猫CEO李天驰谈人工智能如何赋能教育

    【TechWeb】6月29日消息,编程猫创始人兼CEO李天驰受邀参加人民网联合全国高等学校计算机教育研究会举办的“共创智慧教育新生态”在线研讨会,就后疫情时代智慧教育建设分享了自己的观点。在谈及智慧教育如何落地、人工智能如何赋能教育方面,李天驰表示编程猫在普及人工智能教育以及编程教育上,发现在线教育在全国中小学落地,遇到的最大问题是缺少好的老师,为了解决在人工智能教育以及编程教育领域师资不匹配的问题,编程猫以

  • 微软开发恢复严重退化老照片新算法:瞬间清晰、还原原汁原味的美

    对于那些严重退化的老照片,微软也是给出了新的解决办法。微软研究院研究团队Ziyu Wan、Zhang Bo等人开发了一种基于人工智能的新算法,其可以通过深度学习的方法恢复严重退化的老照片。跟可以

  • 微软研究院开发出旧照片还原算法 AI和深度学习立功

    据外媒WindowsUnited消息,微软研究院使用人工智能和深度学习开发出了一种新的算法来还原旧照片。此前恢复旧的和损坏的照片的方法主要是深度学习。但是,对于较旧的照片,其衰减过程非常复杂。

  • 世界名校、大厂人才汇聚,"马栏山杯"算法大赛打造AI视频竞技场

    2009 年,李飞飞等研究者在CVPR2009 上发表了一篇名为《ImageNet: A Large-Scale Hierarchical Image Database》的论文,拉开了ImageNet大规模视觉识别挑战赛的序幕。在之后八年的时间里,来自世界各地的研究者不断刷新纪录,将分类错误率缩小到最初发布时的1/10。与此同时,计算机视觉领域也取得了显著进展。虽然 2017 年ImageNet挑战赛就已停办,但在AI领域,更多的挑战赛如雨后春笋般成长起来。Kaggle数据挑战赛吸引了国内外大?

  • 最新通知!关于东方极客杯青少年编程挑战活动报名有新变化!

    Hello,大家好!端午节即将来临,小星在这里预祝大家端午安康!在过去加长版的假期中,很多孩子变得越来越优秀,当然也需要一个可以施展才华的平台。这也难怪 2020 东方极客杯青少年编程挑战活动自 6 月 10 日起开始报名后,孩子们参与的热情一点都不亚于小升初和中高考。小星和万千爸爸妈妈们期待孩子们的同场竞技。此外,本活动在日程安排上出现了重要的变化,家长和孩子们一定要注意!同时,关于活动报名的事项也整理了下,希望会?

  • 美国杜克大学开发全新算法:AI去马赛克 毛孔、头发都能给你还原了

    AI人工智能技术近年来大热,尤其是在图像识别领域,大家很期待的一个功能就是AI去马赛克。美国杜克大学的研究人员日前发明了一种新的PULSE算法,它可以将低分辨图片变成高清图片,细致到毛孔、头

  • 腾讯视频组织调整:短视频部门撤销重组 将更注重算法推荐

    近日,腾讯总办对PCG(平台与内容事业群)进行了部分组织架构调整。腾讯本次调整内容涉及两个层面:更加重视技术和算法、腾讯视频将采用全平台全品类内容运营。

  • 参与评论
文明上网理性发言,请遵守新闻评论服务协议