数学,离一个程序员有多近?

作者:小傅哥 博客:https://bugstack.cn

沉淀、分享、成长,让自己和他人都能有所收获!

一、前言

数学离程序员有多近?

ifelse也好、for循环也罢,代码可以说就是对数学逻辑的具体实现。所以敲代码的程序员几乎就离不开数学,难易不同而已。

那数学不好就写不了代码吗?不,一样可以写代码,可以写出更多的CRUD出来。那你不要总觉得是产品需求简单所以你的实现过程才变成了增删改查,往往也是因为你还不具备可扩展、易维护、高性能的代码实现方案落地能力,才使得你小小年纪写出了更多的CRUD!

与一锥子买卖的小作坊相比,大厂和超级大厂更会注重数学能力。

first 10-digit prime found in consecutive digits of e

2004年,在硅谷的交通动脉 101 公路上突然出现一块巨大的广告牌,上面是一道数学题: {e 的连续数字中最先出现的 10 位质数}.com。

广告:这里的 e 是数学常数,自然对数的底数,无限不循环小数。这道题的意思就是,找出 e 中最先出现的 10 位质数,然后可以得出一个网址。进入这个网址会看到 Google 为你出的第二道数学题,成功解锁这步 Google 会告诉你,我们或许是”志同道合“的人,你可以将简历发到这个邮箱,我们一起做点改变世界的事情。

计算 e 值可以通过泰勒公式推导出来:e^x 1 + x + x^2/2! + x^3/3! +……+ x^n/n! (1) 推导计算过程还包括埃拉托色尼筛选法(the Sieve of Eratosthenes)、线性筛选法的使用。感兴趣的小伙伴可以用代码实现下。

二、把代码写好的四步

业务提需求、产品定方案、研发做实现。最终这个系统开发得怎么样是由三方共同决定的!

  • 地基挖得不好,楼就盖不高
  • 砖头摆放不巧,楼就容易倒
  • 水电走线不妙,楼就危险了
  • 格局设计不行,楼就卖不掉

这里的地基、砖头、水电、格局,对应的就是,数据结构、算法逻辑、设计模式、系统架构。从下到上相互依赖、相互配合,只有这一层做好,下一层才好做!

图 20-2 代码实现过程分层

  • 数据结构:高矮胖瘦、长宽扁细,数据的存放方式,是一套程序开发的核心基础。不合理的设计往往是从数据结构开始,哪怕你仅仅是使用数据库存放业务信息,也一样会影响到将来各类数据的查询、汇总等实现逻辑的难易。
  • 算法逻辑:是对数据结构的使用,合适的数据结构会让算法实现过程降低时间复杂度。可能你现在的多层for循环在合适的算法过程下,能被优化为更简单的方式获取数据。注意:算法逻辑实现,并不一定就是排序、归并,还有你实际业务的处理流程。
  • 设计模式:可以这么说,不使用设计模式你一样能写代码。但你愿意看到满屏幕的ifelse判断调用,还是喜欢像膏药一样的代码,粘贴来复制去?那么设计模式这套通用场景的解决方案,就是为你剔除掉代码实现过程中的恶心部分,让整套程序更加易维护、易扩展。就是开发完一个月,你看它你还认识!
  • 系统架构:描述的是三层MVC,还是四层DDD。我对这个的理解就是家里的三居还是四局格局,MVC是我们经常用的大家都熟悉,DDD无非就是家里多了个书房,把各自属于哪一个屋子的摆件规整到各自屋子里。那么乱放是什么效果呢,就是自动洗屁屁马桶给按到厨房了,再贵也格楞子! 好,那么我们在延展下,如果你的卫生间没有流出下水道咋办?是不这个地方的数据结构就是设计缺失的,而到后面再想扩展就难了吧!

所以,研发在承接业务需求、实现产品方案的时候。压根就不只是在一个房子的三居或者四居格局里,开始随意码砖。

没有合理的数据结构、没有优化的算法逻辑、没有运用的设计模式,最终都会影响到整个系统架构变得臃肿不堪,调用混乱。在以后附加、迭代、新增的需求下,会让整个系统问题不断地放大,当你想用重构时,就有着千丝万缕般调用关系。 重构就不如重写了!

三、for循环没算法快

在《编程之美》一书中,有这样一道题。求:1~n中,1出现的次数。比如:1~10,1出现了两次。

1. for 循环实现

long startTime = System.currentTimeMillis();int count = 0;for (int i = 1; i <= 10000000; i++) {String str = String.valueOf(i);for (int j = 0; j < str.length(); j++) {if (str.charAt(j) == 49) {count++;}}}System.out.println("1的个数:" + count);System.out.println("计算耗时:" + (System.currentTimeMillis() – startTime) + "毫秒");

使用 for 循环的实现过程很好理解,就是往死了循环。之后把循环到的数字按照字符串拆解,判断每一位是不是数字,是就+1。这个过程很简单,但是时间复杂很高。

2. 算法逻辑实现

图 20-3 1的个数循环规则

如图 20-3 所示,其实我们能发现这个1的个数在100、1000、10000中是有规则的循环出现的。11、12、13、14或者21、31、41、51,以及单个的1出现。最终可以得出通用公式:abcd…=(abc+1)*1+(ab+1)*10+(a+1)*100+(1)*1000…,abcd代表位数。另外在实现的过程还需要考虑比如不足100等情况,例如98、1232等。

实现过程

long startTime = System.currentTimeMillis();int num = 10000000, saveNum = 1, countNum = 0, lastNum = 0;int copyNum = num;while (num != 0) {lastNum = num % 10;num /= 10;if (lastNum == 0) {// 如果是0那么正好是少了一次所以num不加1了countNum += num * saveNum;} else if (lastNum == 1) {// 如果是1说明当前数内少了一次所以num不加1,而且当前1所在位置// 有1的个数,就是去除当前1最高位,剩下位数,的个数。countNum += num * saveNum + copyNum % saveNum + 1;} else {// 如果非1非0.直接用公式计算// abcd…=(abc+1)*1+(ab+1)*10+(a+1)*100+(1)*1000…countNum += (num + 1) * saveNum;}saveNum *= 10;}System.out.println(“1的个数:” + countNum);System.out.println(“计算耗时:” + (System.currentTimeMillis() – startTime) + “毫秒”);

在《编程之美》一书中还不只这一种算法,感兴趣的小伙伴可以查阅。但自己折腾实现后的兴奋感更强哦!

3. 耗时曲线对比

按照两种不同方式的实现逻辑,我们来计算1000、10000、10000到一个亿,求1出现的次数,看看两种方式的耗时曲线。

图 20-4 耗时曲线对比

  • for循环随着数量的不断增大后,已经趋近于无法使用了。
  • 算法逻辑依靠的计算公式,所以无论增加多少基本都会在1~2毫秒内计算完成。

那么,你的代码中是否也有类似的地方。如果使用算法逻辑配合适合的数据结构,是否可以替代一些for循环的计算方式,来使整个实现过程的时间复杂度降低。

四、Java中的算法运用

在 Java 的 JDK 实现中有很多数学知识的运用,包括数组、链表、红黑树的数据结构以及相应的实现类ArrayList、Linkedlist、HashMap等。当你深入的了解这些类的实现后,会发现它们其实就是使用代码来实现数学逻辑而已。就像你使用数学公式来计算数学题一样

接下来小傅哥就给你介绍几个隐藏在我们代码中的数学知识。

1. HashMap的扰动函数

未使用扰动函数

未使用扰动函数,数据分布

已使用扰动函数

未使用扰动函数,数据分布

扰动函数公式

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

  • 描述:以上这段代码是HashMap中用于获取hash值的扰动函数实现代码。HashMap通过哈希值与桶定位坐标 那么直接获取哈希值就好了,这里为什么要做一次扰动呢?
  • 作用:为了证明扰动函数的作用,这里选取了10万单词计算哈希值分布在128个格子里。之后把这128个格子中的数据做图表展示。从实现数据可以看到,在使用扰动函数后,曲线更加平稳了。那么,也就是扰动后哈希碰撞会更小。
  • 用途:当你有需要把数据散列分散到不同格子或者空间时,又不希望有太严重的碰撞,那么使用扰动函数就非常有必要了。比如你做的一个数据库路由,在分库分表时也是尽可能的要做到散列的。

2. 斐波那契(Fibonacci)散列法

ThreadLocal 中 斐波那契(Fibonacci)散列法

  • 描述:在 ThreadLocal 类中的数据存放,使用的是斐波那契(Fibonacci)散列法 + 开放寻址。之所以使用斐波那契数列,是为了让数据更加散列,减少哈希碰撞。具体来自数学公式的计算求值,公式:f(k) = ((k * 2654435769) >> X) 28
  • 作用:与 HashMap 相比,ThreadLocal的数据结构只有数组,并没有链表和红黑树部分。而且经过我们测试验证,斐波那契散列的效果更好,也更适合 ThreadLocal。
  • 用途:如果你的代码逻辑中需要存储类似 ThreadLocal 的数据结构,又不想有严重哈希碰撞,那么就可以使用 斐波那契(Fibonacci)散列法。其实除此之外还有,除法散列法、平方散列法、随机数法等。

3. 梅森旋转算法(Mersenne twister)

梅森旋转算法的三个阶段,来自CSDN博客网图

// Initializes mt[N] with a simple integer seed. This method is// required as part of the Mersenne Twister algorithm but need// not be made public.private final void setSeed(int seed) {// Annoying runtime check for initialisation of internal data// caused by java.util.Random invoking setSeed() during init.// This is unavoidable because no fields in our instance will// have been initialised at this point, not even if the code// were placed at the declaration of the member variable.if (mt == null) mt = new int[N];// —- Begin Mersenne Twister Algorithm —-mt[0] = seed;for (mti = 1; mti >> 30)) + mti);}// —- End Mersenne Twister Algorithm —-}

梅森旋转算法(Mersenne twister)是一个伪随机数发生算法。由松本真和西村拓士在1997年开发,基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数,修正了古典随机数发生算法的很多缺陷。 最为广泛使用Mersenne Twister的一种变体是MT19937,可以产生32位整数序列。

  • 描述:梅森旋转算法分为三个阶段,获得基础的梅森旋转链、对于旋转链进行旋转算法、对于旋转算法所得的结果进行处理。
  • 用途:梅森旋转算法是R、Python、Ruby、IDL、Free Pascal、PHP、Maple、Matlab、GNU多重精度运算库和GSL的默认伪随机数产生器。从C++11开始,C++也可以使用这种算法。在Boost C++,Glib和NAG数值库中,作为插件提供。

五、程序员数学入门

与接触到一个有难度的知识点学起来辛苦相比,是自己不知道自己不会什么!就像上学时候老师说,你不会的就问我。我不会啥?我从哪问?一样一样的!

代码是对数学逻辑的实现,简单的逻辑调用关系是很容易看明白的。但还有那部分你可能不知道的数学逻辑时,就很难看懂了。比如:扰动函数、负载因子、斐波那契(Fibonacci)等,这些知识点的学习都需要对数学知识进行验证,否则也就学个概念,背个理论。

书到用时方恨少,在下还是个宝宝!

那如果你想深入的学习下程序员应该会的数学,推荐给你一位科技博主 Jeremy Kun 花了4年时间,写成一本书 《程序员数学入门》。

Jeremy Kun,《程序员数学入门》

这本书为程序员提供了大量精简后数学知识,包括:多项式、集合、图论、群论、微积分和线性代数等。同时在wiki部分还包括了抽象代数、离散数学、傅里叶分析和拓扑学等。

《程序员数学入门》书中插图

作者表示,如果你本科学过一些数学知识,那么本书还是挺适合你的,不会有什么难度。书中的前三章是基础数学内容,往后的难度依次递增。

  • 书籍获取:关注公众号:bugstack虫洞栈,回复:程序员数学,下载这本书
  • 在线Wiki:https://jeremykun.com/primers/
  • 数据结构:https://bugstack.cn/md/algorithm/data-structures/data-structures.html

六、总结

  • Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians. https://www.cs.utexas.edu/users/EWD/transcriptions/EWD04xx/EWD498.html
  • 单纯的只会数学写不了代码,能写代码的不懂数学只能是CRUD码农。数学知识帮助你设计数据结构和实现算法逻辑,代码能力帮你驾驭设计模式和架构模型。多方面的知识结合和使用才是码农和工程师的主要区别,也是是否拥有核心竞争力的关键点。
  • 学习知识有时候看不到前面的路有多远,但哪怕是个泥坑,只要你不停的蠕动、折腾、翻滚,也能抓出一条泥鳅。知识的路上是发现知识的快乐,还学会知识的成就感,不断的促使你前行。
郑重声明:本文内容及图片均整理自互联网,不代表本站立场,版权归原作者所有,如有侵权请联系管理员(admin#loooy.com)删除。
(0)
上一篇 2022年11月9日 18:19
下一篇 2022年11月9日 18:19

相关推荐

  • 赫尔松州因输电线被破坏而断电断水,俄乌双方各执一词

    极目新闻记者 屈旌 胡秀文 关于赫尔松州及多个地区停水断电,俄乌双方各执一词。 俄罗斯卫星通讯社报道截图 俄罗斯卫星通讯社11月6日报道称,在赫尔松州和该州的一些地区,由于乌军的恐…

    2022年11月10日
  • 未来几年什么行业前景好(未来10年最有发展潜力的行业)

    有一句话说得好,逆水行舟,不进则退。在这里我也送给你一句话,逆流而上,效率翻倍。在大环境不稳定的情况下,如果我们还能够抓住市场当中的机遇逆流而上的话,那我们和别人之间的差距就会加速…

    2022年11月4日
  • 婴幼儿湿疹总是反反复复?专家教你应对方法

    每年10月到次年4月,都是湿疹的多发时间,很多人听到“湿疹”两字,都以为是皮肤太湿导致的,但事实恰恰相反,“干”才是主要原因。众所周知,皮肤是人体的屏障,但空气、环境等多种原因导致…

    2022年11月13日
  • 老人睡觉的6种异常,可能是脑梗信号,家人护理要当心

    脑梗的信号 大家都知道,脑梗最常发生在休息或睡觉时,此时老人血压过低、血液流动缓慢,加大了血栓形成的风险,如果老人在睡觉的时候出现这6种异常,家人必须引起高度重视,可能是脑梗的信号…

    2023年4月13日
  • 不管腌什么酸菜,记住这3点,酸菜不烂不发霉,而且又酸又脆又香

    气温下降,全国各地的人们都开始忙着做酸菜了。冬天经常大鱼大肉,很容易吃不下饭。又酸又脆的酸菜,既爽口又开胃,还能解腻。天气冷了,买上十几斤大白菜,腌好以后,再也不用担心家里没菜。 …

    2022年11月13日
  • 输入订单编号查物流(订单编号怎么查询)

    网购是我们现在日常生活中最普遍的一件事,尤其是到了活动期间,快递越来越多,商家面对成千上万的单号,该如何查询到全部物流呢?下面随小编一起用这个新的技巧来试试,它能同时查询多个快递单…

    2022年11月5日
  • 比酷科技 酷比官方网站

    趣行天下今日召开战略发布会,宣布与酷狗游戏、酷我游戏达成战略合作,成立全新公司—北京趣酷科技有限公司。 趣酷科技CEO李威表示,这标志着趣行天下由游戏研发公司蜕变成一家集游戏研发与…

    2022年7月3日
  • 村民非法捕杀野生动物被查(破获非法猎捕野生动物案19起)

    这种壁虎叫无蹼壁虎,有相关的法律规定,私自捕捉一只无蹼壁虎就违法,捕捉20只以就构成了犯罪,捕捉50只以上就属于重大的刑事案件无蹼壁虎已经被列为濒危物种,主要分布在中国,无蹼壁虎是…

    2022年11月21日
  • 2002-2008看感动中国十大人物

      2008年度感动中国人物事迹及颁奖词   感动中国,2008年的壮美史诗。2008,仅这一年中,人们经历的悲歌和欢笑,经受的阵痛和新生,就足以抒写一部家、国壮美的史诗。   1…

    2023年2月3日
  • 辣妈路上的绊脚石-腹直肌分离,你了解多少?

    很多宝妈在怀孕晚期,增大的子宫会使腹壁扩张延伸,两侧的腹直肌会从腹中线,也就是腹白线的位置向两侧分离。如果产后半年腹直肌仍然不能回到原先位置,就叫腹直肌分离。 有没有腹直肌分离?自…

    2022年10月17日