不能忘记!数据科学家面试时应该掌握的3个编程概念
算法是数据科学不可分割的一部分。虽然很多数据科学家在学习的时候没有选修合适的算法课程,但它确实很重要。
比如说,许多公司在面试数据科学家时,都会问到数据结构和算法。
那么,现在问题是,问数据科学家这样的问题到底有什么用。
对于这个问题,我的答案是,数据结构问题可以被当作是对编码能力的测试。
我们都在人生的不同阶段接受过能力测试,但是这些测试并不能完美地评判一个人,几乎没有什么测试能做到这一点。
那么,为什么不用一个标准算法测试来评判一个人的编码能力呢?
因为算法和测试都并非死板,你总能在前者总结的基础上不断改进、创新,总能运用不同的算法来回应这些测试。
但这也并不意味着你可以不掌握基础就可以肆意动摇算法的地基。
牢固掌握基础算法的概念和运用,永远是一个优秀数据科学家必备的素质。
本文将以一种容易理解的方式帮助数据科学家快速回顾相关研究并介绍一些基本算法概念。
1. 递归/记忆化
递归是将定义的函数应用到自己的定义中。简而言之,递归是函数的自身调用。当你用谷歌搜索递归时,会遇到点小插曲。
刚开始学习数据科学的人可能会觉得递归有点难,但其实它很容易理解。一旦理解了,就会发现这是一个很棒的概念。
解释递归的最好例子就是计算一个数的阶乘。
- def factorial(n):
- if n==0:
- return 1
- return n*factorial(n-1)
可以很容易地看出阶乘是一个递归函数。
- Factorial(n) = n*Factorial(n-1)
那么如何将它转化为编程呢?
递归调用的函数通常由两部分组成:
- 基线条件——终止递归的条件。
- 递归公式——向基线条件发展的公式。
许多问题解决到最后,就是递归问题。这也适用于数据科学。
例如,一棵决策树是二叉树,树算法通常是递归的。或者,以我们经常使用的排序为例。排序的算法称为归并排序(mergesort),它本身就是一种递归算法。另一种是对分查找 (binary search),包括在数组中查找元素。
现在我们了解了递归的基本知识,接下来试着找到第n个斐波那契数。斐波那契数列是一系列数字,其中每个数字(斐波那契数)都是前面两个数字之和。最简单的数列是1、1、2、3、5、8等。要找到第n个斐波那契数,可以用如下代码:
- def fib(n):
- if n<=1:
- return 1
- return fib(n-1) + fib(n-2)
但是,发现问题了吗?
如果试图计算fib(n=7)要运行两次fib(5) ,运行三次 fib(4) ,运行5次 fib(3)。随着n越来越大,对同一数字进行了多次调用,递归函数对其进行了一次又一次的计算。
稍微改变我们的执行,添加一个词典来为这个方法添加一些存储。现在,每次计算出一个数字,这个备忘录词典就会更新。如果再出现同样的数字,就不需要再对它进行计算,而是可以直接从备忘录字典中得出结果。这种增加存储的方式被称为记忆化。
- memo = {}def fib_memo(n): if n in memo: return memo[n] if n<=1: memo[n]=1 return 1 memo[n] = fib_memo(n-1) +fib_memo(n-2) return memo[n]
通常,我会先写递归代码,如果它重复调用相同的参数,我会再添加一个词典来进行记忆化。
这帮助大吗?
图中是不同n值的运行时间的比较。可以看到:没有记忆化的斐波那契函数运行时间呈指数性增长,而记忆化函数的运行时间则是线性的。
2. 动态规划
递归本质就是一种自上而下的方法。比如在计算斐波那契数n时,就是从n开始,然后对n-2和n-1进行递归调用,依此类推。
在动态规划中,我们采取自下而上的方法。这本质上是一种迭代编写递归的方法。首先计算fib(0)和fib(1),然后使用前面的结果生成新的结果。
- def fib_dp(n):
- dp_sols = {0:1,1:1}
- for i in range(2,n+1):
- dp_sols[i] = dp_sols[i-1] +dp_sols[i-2]
- return dp_sols[n]
上图是“动态规划”和“记忆化”运行时间的比较。可以看出它们都是线性的,但动态规划更快一点。
为什么呢?因为在这种情况下,动态规划只对每个子问题进行一次调用。
关于开发动态规划的贝尔曼是如何选定“动态规划”这个名字的,有一个很有趣的故事:
“动态规划”这个名字是从哪里来的呢?20世纪50年代的数学研究情况并不是很好。当时,华盛顿有一位非常有趣的绅士,名叫威尔逊,他是国防部长。实际上,他对研究这个词怀有病态的恐惧和仇恨。那我能起个什么名字呢?首先,我考虑了“计划”、“决策”、“思考”。但是出于各种原因,“计划”并不是一个好词。于是,我决定使用“规划”一词。我想传递的概念是,这是动态的,多级的,并且是时变的。因此,我认为动态规划是个好名字,这可以一举两得。这是连国会议员都不会反对的。所以我决定采用这个名字。
3. 二进制搜索
假设有一个排序了的数字组合,要从这个数组中找出一个数字。我们可以采用线性搜索,挨个地检查每一个数字,直到找到特定数字。问题是,如果数组包含数百万个元素,这种方法就需要花费很长时间。这种情况下,可以采用二进制搜索方法。
来源:发现37-海洋中有3.7万亿条鱼,他们正在寻找其中的1条
- # Returns index of target innums array if present, else -1
- def binary_search(nums, left, right, target):
- # Base case
- if right >= left:
- mid = int((left + right)/2)
- # If target is present at themid, return
- if nums[mid] == target:
- return mid
- # Target is smaller than midsearch the elements in left
- elif nums[mid] > target:
- return binary_search(nums,left, mid-1, target)
- # Target is larger than mid,search the elements in right
- else:
- return binary_search(nums,mid+1, right, target)
- else:
- # Target is not in nums
- return -1nums =[1,2,3,4,5,6,7,8,9]
- print(binary_search(nums, 0, len(nums)-1,7))
这是一个基于递归算法的高级例子。利用数组被排序的事实,递归地查看中间元素,看看是想在中间元素的左边还是右边搜索。这使得每一步的搜索空间减少2倍。
因此,二进制搜索算法的运行时间是O(logn),而不是线性搜索的O(n)。
这有什么作用呢?下面是运行时间的比较。我们可以看到二进制搜索与线性搜索相比是相当快。
当n=10000时, 二进制搜索需要大约13步,线性搜索需要10000步。
结论
本文谈到了一些构成编程基础的算法,虽然是基础,但也同样令人兴奋。
数据科学家在面试时会经常被问到这些算法,深入理解它们可能会帮助你找到理想的工作哦。
尽管你不学习这些算法也可以在数据科学中取得进步,但你可以把学习它们当作一种乐趣,培养兴趣的同时还可以顺便提高编程技能。
一举两得,何乐而不为呢?
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
从“红帽杯”网络安全攻防大赛看安全人才培养与企业安全防护
【51CTO.com原创稿件】“网络空间的竞争,归根到底是人才的竞争”,如何培养高素质的网络安全队伍,引发行业乃至国家的高度关注。近年来,为了进一步加强网络安全人才建设,以赛促学、以赛代练的网络安全攻防大赛此起彼伏。 11月23日,第三届“红帽杯”网络安全攻防大赛总决赛在广州大学城体育中心圆满落幕。作为广东“红帽先锋”人才培养计划中的重要一环,“红帽杯”网络安全攻防大赛对发掘、锻炼、培养网络安全人才有重要意义。(所谓红帽,是指那些拥有正义感、热爱祖国,会为维护国家利益而施展网络攻防技能的一部分黑客。) 大赛更公平、更科学、更精细 本届大赛共历时20多天,吸引了1600多支队伍参赛。比赛从多方面的考验参赛队员计算机理论和实践技能,其中涉及到的范围包括:逆向、漏洞挖掘与利用、Web渗透、密码、取证、隐写、安全编程等等。 采访中,广东省计算机信息网络安全协会会长陆以勤表示,相较于前两届,本次红帽杯大赛的组织单位更多,参赛队伍是上一届的4.75倍,达到4800多人,外省队伍也在增加,知名高校参赛人员也越来越多,规模在扩大,影响力也在增加,与往年相比,有一个质的飞跃。 另一方面,从比赛环境和赛题...
- 下一篇
12 月 DB-Engines 数据库排行:SQLite 角逐前 10
12 月份的 DB-Engines 数据库排行榜公布了,先整体看看前 20 名: 前 20 名排位相比上个月基本不变,只有 SAP Adaptive Server 与 FileMaker 调换了位置。 在具体获得的分数上,上个月前 3 名 Oracle、MySQL 与 Microsoft SQL Server全线大幅度下降,本月都恢复了过来。而除去这 3 者,前 5 名中剩下的PostgreSQL 与 MongoDB 则稳步上涨。 Cassandra 分值下降了 2.52(上月涨了 0.01),下降幅度在前 20 中还比较显眼,并且可以看到,排在它之后的 SQLite 目前与它的分值仅相差 0.35(相比上个月下降 1.60,本月 SQLite 仅下降 0.66),简单看二者的小趋势,下个月可能Cassandra 的第 10 名会被 SQLite 取代。 接下来看一下前 10 名的趋势图: 最后分类看看每种数据库的前 10 名: 关系型 DBMS K-V 存储 文档型存储 图 DBMS 时序 DBMS 完整榜单查看:https://db-engines.com/en/ranking D...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Hadoop3单机部署,实现最简伪集群
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果