关于javascript:数学离一个程序员有多近

45次阅读

共计 5428 个字符,预计需要花费 14 分钟才能阅读完成。

一、前言

数学离程序员有多近?

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

那数学不好就写不了代码吗?????不,一样能够写代码,能够写出更多的 CRUD 进去。那你不要总感觉是产品需要简略所以你的实现过程才变成了增删改查,往往也是因为你还不具备可扩大、易保护、高性能的代码实现计划落地能力,才使得你小小年纪写出了更多的CRUD

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

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) 线性筛选法 的应用。感兴趣的小伙伴能够用代码实现下。

二、把代码写好的四步

业务提需要、产品定计划、研发做实现。最终这个零碎开发的怎么样是由三方独特决定的!

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

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

  • 数据结构:高矮胖瘦、长宽扁细,数据的寄存形式,是一套程序开发的外围根底。不合理的设计往往是从数据结构开始,哪怕你仅仅是应用数据库寄存业务信息,也一样会影响到未来各类数据的查问、汇总等实现逻辑的难易。
  • 算法逻辑:是对数据结构的应用,适合的数据结构会让算法实现过程升高工夫复杂度。可能你当初的多层 for 循环在适合的算法过程下,能被优化为更简略的形式获取数据。_留神:算法逻辑实现,并不一定就是排序、归并,还有你理论业务的解决流程。_
  • 设计模式:能够这么说,不应用设计模式你一样能写代码。但你违心看到满屏幕的 ifelse 判断调用,还是喜爱像膏药一样的代码,粘贴来复制去?那么设计模式这套通用场景的解决方案,就是为你剔除掉代码实现过程中的恶心局部,让整套程序更加易保护、易扩大。_就是开发完一个月,你看它你还意识!_
  • 零碎架构:形容的是三层 MVC,还是四层 DDD。我对这个的了解就是家里的三居还是四局格局,MVC 是咱们常常用的大家都相熟,DDD 无非就是家里多了个书房,把各自属于哪一个屋子的摆件规整到各自屋子里。_那么乱放是什么成果呢,就是主动洗屁屁马桶???? 给按到厨房了,再贵也格楞子!_ 好,那么咱们在延展下,如果你的卫生间没有流出下水道咋办?是不这个中央的数据结构就是设计缺失的,而到前面再想扩大就难了吧!

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

没有正当的数据结构、没有优化的算法逻辑、没有使用的设计模式,最终都会影响到整个零碎架构变得臃肿不堪,调用凌乱。在当前附加、迭代、新增的需要下,会让整个零碎问题一直的放大,当你想用重构时,就有着千头万绪般调用关系。重构就不如重写了!

三、for 循环没算法快

在《编程之美》一书中,有这样一道题。求:1n 中,1 呈现的次数。比方:110,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 的个数在 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 呈现的次数,看看两种形式的耗时曲线。

  • 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)散列法 + 凋谢寻址。之所以应用斐波那契数列,是为了让数据更加散列,缩小哈希碰撞。具体来自数学公式的计算求值, 公式f(k) = ((k * 2654435769) >> X) << Y 对于常见的 32 位整数而言,也就是 f(k) = (k * 2654435769) >> 28
  • 作用:与 HashMap 相比,ThreadLocal 的数据结构只有数组,并没有链表和红黑树局部。而且通过咱们测试验证,斐波那契散列的成果更好,也更适宜 ThreadLocal。
  • 用处 :如果你的代码逻辑中须要存储相似 ThreadLocal 的数据结构,又不想有重大哈希碰撞,那么就能够应用 斐波那契(Fibonacci)散列法。其实除此之外还有, 除法散列法 平方散列法 随机数法 等。

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

// 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 < N; mti++) {mt[mti] = (MAGIC_FACTOR1 * (mt[mti-1] ^ (mt[mti-1] >>> 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 年工夫,写成一本书 《程序员数学入门》

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

作者示意,如果你本迷信过一些数学知识,那么本书还是挺适宜你的,不会有什么难度。书中的前三章是根底数学内容,往后的难度顺次递增。

六、总结

  • 单纯的只会数学写不了代码,能写代码的不懂数学只能是 CRUD 码农。数学知识帮忙你设计数据结构和实现算法逻辑,代码能力帮你驾驭设计模式和架构模型。多方面的常识联合和应用才是码农和工程师的次要区别,也是是否领有外围竞争力的关键点。
  • 学习常识有时候看不到后面的路有多远,但哪怕是个泥坑,只有你不停的蠕动、折腾、翻滚,也能抓出一条泥鳅。常识的路上是发现常识的高兴,还学会常识的成就感,一直的促使你前行

零根底学习 Java 编程,能够退出我的十年 Java 学习园地,技术交换,资源共享,开发经验总结。

正文完
 0