天天看點
傳回

數學，離一個程式員有多近？

數學，離一個程式員有多近？

作者：小傅哥

部落格：https://bugstack.cn

沉澱、分享、成長，讓自己和他人都能有所收獲！😄

一、前言

數學離程式員有多近？

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部分還包括了抽象代數、離散數學、傅裡葉分析和拓撲學等。

數學，離一個程式員有多近？

作者表示，如果你大學學過一些數學知識，那麼本書還是挺适合你的，不會有什麼難度。書中的前三章是基礎數學内容，往後的難度依次遞增。

  • 書籍擷取：關注公衆号：bugstack蟲洞棧，回複：

    程式員數學

     ，下載下傳這本書
  • 線上Wiki：https://jeremykun.com/primers/

六、總結

  • 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碼農。數學知識幫助你設計資料結構和實作算法邏輯，代碼能力幫你駕馭設計模式和架構模型。多方面的知識結合和使用才是碼農和工程師的主要差別，也是是否擁有核心競争力的關鍵點。
  • 學習知識有時候看不到前面的路有多遠，但哪怕是個泥坑，隻要你不停的蠕動、折騰、翻滾，也能抓出一條泥鳅。

    知識的路上是發現知識的快樂，還學會知識的成就感，不斷的促使你前行

     。

七、系列推薦

  • 網際網路大廠，線上研發事故總結！
  • 碼德，這不就是産品給我留的數學作業！
  • HashMap核心知識，擾動函數、負載因子、擴容連結清單拆分，深度學習
  • Netty實戰，1比1仿桌面版微信聊天

公衆号：bugstack蟲洞棧 | 作者小傅哥多年從事一線網際網路 Java 開發的學習曆程技術彙總，旨在為大家提供一個清晰詳細的學習教程，側重點更傾向編寫Java核心内容。如果能為您提供幫助，請給予支援(關注、點贊、分享)！

數學程式設計 梅森旋轉算法 斐波那契（Fibonacci）散列法 程式員數學入門 算法邏輯 java
上一篇: 年紀輕輕，為什麼要搞中間件開發？“路怎麼走，讓你們自己挑”
下一篇: 組内分享，畫架構圖的一些知識整理

繼續閱讀