作為程序員的你(或者即將成為程序員)何時意識到數學的重要性?

最近琢磨的一個問題,歡迎大家說說自己的故事。還有可以推薦經典計算機數學書嗎。


我印象很深的一個例子,是當年學WordPress的時候,接觸到一個函數 wp_nonce_tick

有時候HTTP請求需要在特定周期過後失效,也就是時間敏感的請求籤名,這是後台自我保護的一種機制。

怎麼樣讓一個請求在一定時間後過期呢?按照web後台程序員習慣的方法,是在資料庫或者session里存一個值,相應請求到達後端的時候就去檢查這個值是否還匹配。但是只是存放一個值並不能關聯到時間,所有就要設計相應的機制去poll/update這個值。如果這樣搞,開銷會很大。

Nonce的基本原理就是一個算式:

ceil(time() / ( life / 2 ))

你有興趣可以打開瀏覽器控制台用Javascript來試試,比如一分鐘內有效期的Nonce

Math.ceil(Math.ceil(new Date().getTime() / 1000) / (60 / 2))

用這個值來給請求籤名,伺服器端只需要計算一個同周期的Nonce,看看兩者是否相等就可以判斷請求是否仍然有效。

不用存什麼中間值,不用poll。只是簡單的數學規律。

談不上多高深,但你知道了這個工具以後,會覺得太強大,太美。數學家真牛逼。

加密學上有很多讓不懂數學的人,懂了以後覺得毛骨悚然的例子,你可以買本書來看看,我數學差,就不混充很懂了。


很多時候,數學帶給我們的不光是「知識」,更是「思維方式」,去有意識運用這個「知識」的能力。和考試不同的是,在寫程序的時候,幾乎不會有一個地方標明「這裡需要用某某數學公式」,儘管你可能知道這些公式,但是要有能力想起來用,才是本事。

記得我在UCSB上課的時候,給新生入門的第一個程序往往喜歡用IsPrime(題外話,每次我問什麼是素數的時候都有一半人一臉懵地看著我,這時候我真的覺得數學很重要)。而教了這麼多學生,只有一個人在寫的時候用到了 i &<= sqrt(n) 這個優化。這個優化是純數學意義上的,和編程沒啥關係,每個人在看到了之後其實都明白這是在做什麼,為什麼好,但是有人就是想不到。

同樣是在UCSB上課的時候,我曾經問過一句,你們知道sin函數,在硬體不支持的情況下,是怎麼實現的么?這次一個答上來的都沒有了。不過這也正常,恐怕看客們也少有思考這個問題的。在幾乎所有語言里,sin函數都作為math庫的一部分被實現了(哪怕是C),但是這個sin究竟是怎麼實現的?在很多情況下,是用Taylor Series(泰勒展開)實現的。它把一個複雜函數求值的問題轉換成多項式的加減乘。如果你不知道這是啥,你就沒法去寫庫了。

我記得我在我的答案里多次提到了一個快速sqrt函數 x_bits = (x_bits &>&> 1) + 532369198; 這個和網路上更被人熟知的inverse sqrt函數 i = 0x5f3759df - ( i &>&> 1 ); 是同源的。他們長得這麼像,有沒有原因?他們是如何利用IEEE的浮點數規則來進行平方運算的?這幾個Magic Number到底是怎麼回事?有沒有理由?能不能換?如果你不會數學,你就完全沒法解釋。(在這裡不做證明,但是證明的一部分是同樣可以利用泰勒展開去計算誤差的)

上學期在講課的時候,我提到過兩個概念,一個是數學歸納法,一個是Big O。這兩個東西,前者是高中數學內容,後者是課上剛講過的知識。我當時問有沒有人能把這兩個東西的定義寫下來,沒有人會。其實這也不怪他們,即便是已經工作多年的程序員,你要問他,f(n) ~ O(g(n))的數學定義是什麼,他也未必答得上來。可是如果你知道定義,你就不會問「這個演算法為什麼是n而不是2n」這種問題了。

依然是上課的內容,我講Fibonacci的求值作為經典遞歸演算法的開頭。我說這個演算法太慢了,他是一個接近2^n的複雜度,如果用for loop直接算,是n的複雜度。但是大家知道Fibonacci可以到log n嗎?然後我開始給他們講log n的解法,當中出現了一個非常簡單的矩陣(Fibonacci number 中Matrix form章節),大家表示,好了看不懂了。但是到了學AI和ML的時候,滿地都是矩陣,看不懂怎麼辦咧?

不過現狀就是,絕大部分管自己叫「程序員」的工作者們,其實是不太用得到數學的。畢竟庫只需要一丁點人寫,大部分人都是調用API的。這麼多人用RSA加密,又有多少人會去研究這演算法數學上為什麼安全呢?

所以呀,也不用太惶恐,畫畫網頁,挺好。


1. 數據挖掘或分析上需要用上一些數學知識,比如說回歸、分類以及接下來的主成分分析、奇異值分解、文本挖掘等等。

2. 計算機圖形方面,比如說3D的數據在二維平面上的投影。

3. 演算法方面就是時間複雜度和空間複雜度等。

數學知識主要是:

1. 中學數學裡有關的概率統計知識,比如方差極差等,以及微積分基礎。

2 大學數學線性代數相關,包括行列式、矩陣的加減乘、轉置矩陣、逆、秩、特徵值特徵向量、正交矩陣及其性質。

3 概率論相關,比如(樸素)貝葉斯公式(先驗後驗概率、極大似然估計等)、協方差和協方差矩陣。

4 離散數學

純手打

6.30 更新

實際上我跑題了,因為這裡的問題是問何時認識到數學的重要性。我就在此說說我的心得吧。我現在在美國讀碩士,我是在學數據挖掘的時候開始認識到數學的重要性的。我們學校的數據挖掘是一個據說學術上非常productive的台灣籍教授,選她的課前必須要通過一次她舉辦的數學考試,考察前面所說的中國中學和大學的數學內容,否則就要先上學院的數學基礎課。結果我身邊的中國學生就有不少人沒通過,包括一些諸如北郵之類的名校畢業生,我雖然過了但也是考前惡補了一下矩陣和概率論相關的知識點才會做一些題,而且因為題目是英文的,所以有時候就算是大體看得懂裡面的公式也會有些不懂的辭彙,如z-score(標準分數)、eigenvalue(特徵值)、eigenvector(特徵向量)、rank(秩)等,最後還是混過去了。

在上課的過程中,學習了諸如回歸方程,貝葉斯公式,SVM之類的回歸和分類演算法,記住了相關公式,算一算概率還是很簡單的,後來學了主成分分析、奇異值分解之後就開始有些難度了,因為這裡面涉及到比較複雜的矩陣計算,同時還引入了特徵向量和正交矩陣的概念,使得我花了很多的精力才大體了解了些。

後來我在矽谷一家醫療器械公司實習,主要負責處理3D掃描的數據(例如人體內部的器官),使其能在任意方向上被投影並利用演算法快速生成圖像,顯示在屏幕上供醫生參考。這其中涉及到諸多矩陣方面的計算如轉置、逆等,還有圖像的插值技術(相當於把一張圖片放大一定倍數,然後通過演算法把新增加的像素點填充上去,在提高圖片像素的同時保證其不失真)。在這過程中除了要實現演算法還要優化代碼保證演算法運行的高效。

因為時差的緣故,我30號早上起來就有了30多贊,超出了我之前15贊的預期,但由於我白天要上班所以沒能及時補充新內容,還被某位知友以誘導投票為由把我舉報了。在此我表示道歉!同時我也注意到我的回答已經有了16次收藏,說明很到知友把我的回答作為乾貨看待,所以我也會在後面繼續補充相應的知識點以充實幹貨。此外,知乎一直不缺少機器學習或圖像處理以及計算機諸多領域的博士生和業界大牛,而我只是個普通的master,所以如果內容有誤也請多多指正!

=============

1. 數據挖掘相關

1.1 線性回歸

這個不難理解,就是輸入一系列樣本,每個樣本都只有一個自變數和因變數,然後通過尋找一條最合適的直線來代表其中的關係,用y=ax+b表示。

例如我們有一組成年男子的身高體重數據,我們可以根據這些數據找到體重(公斤)和身高(公分)的關係,生成一個線性方程,同時可以用下面公式來計算誤差均值和均方根誤差RMSE

ME=frac{1}{m}sum_{m}^{i=1}left ( yi - widehat{yi} 
ight)RMSE=sqrt{frac{1}{m}sum_{m}^{i=1}left ( yi - widehat{yi} 
ight)^{^{2}}}

當然這個公式並不能準確無誤得根據體重來推測出一個人的身高,畢竟現實中相同體重的人可能會對應截然不同的身高。如果想找到更合適的擬合公式,可以用留一交叉驗證法,即輪流取出其中一個樣本點,對餘下部分計算出擬合公式,找到誤差最小的公式。

同時針對多個自變數屬性,還可以把擬合函數擴展成

y=alpha +sum_{i=1}^{n}eta _{n}x_ {n}

假設再引入成年女子的數據,那麼設x1為身高,x2為體重,然後找到合適的 alphaeta 值就能使得當y大於(小於)0的時候為男性,小於(大於)0的時候為女性。這樣就成了最簡單的二分類問題了。

1.2 高階線性回歸

然而實際上並不是所有的數據點都一定能比較完美的擬合到一條直線上的,比如北京一年365天從1月1日到12月31日(用1-365表示)的平均氣溫就大體呈拋物線形態。因此我們可以很自然想到二階函數,即

y=a_{0}+a_{1}x_ {1}^{1}+a_ {2}x_ {2}^{2}

圖像大概呈這樣,揭示了氣溫隨天數變化的大致規律,儘管並不是和所有點都吻合。

進一步我們可以升級到n階方程

y=sum_{i=0}^{n}a_{n}x^{n}

實際上對於所有的樣本,只要樣本點足夠多,無論是體重-身高樣本還是日期-氣溫樣本,都可以用n階以上的方程進行擬合。比如日期-氣溫樣本如果用n階方程擬合,其圖像會呈下圖(只是簡單失意,並非嚴格的圖象輸出)。

這樣看似乎更加準確了,因為在現實中就算是短短几天也會有很大的氣溫波動,而不是單純的上升或下降,公式擬合出來後只要代入天數就可以近乎準確推出當天的平均氣溫。表面上看好像比2階函數好得多,但這樣做並無太多意義,因為不同年份的氣溫變化曲線都是不同的。同樣是7月1日,今年可能是40℃高溫,明年可能就是22℃的雷雨天氣。所以這個擬合結果如果用來預測明年乃至後年的氣溫,就容易和實際結果出現很大的誤差。這也就是機器學習里的過擬合問題。

這也就說明了預測模型並非越複雜越好,當然如果簡化預測模型,比如將上述數據擬合成一階函數,也不是合適的選擇。所以為了找到一個最合適的模型複雜度,我們需要引入驗證機制,也就是將樣本划出一小部分作為測試集,其餘作為訓練集,用訓練集數據進行擬合然後用測試集驗證預測準確率。最常用的方法是十折交叉驗證,即選取十分之一的樣本做測試集,其餘做訓練集進行擬合。然後再選取另十分之一的樣本做測試集,以此類推重複十次操作,獲得10個擬合模型。然後選取最佳擬合模型或者所有擬合模型的平均值。下圖表示模型複雜度的增加對訓練集和測試集誤差的影響。

(Overfitting - ML Wiki)

在上述例子中,假設手頭上有2007-2016年北京每日的平均氣溫數據,那麼我們可以取2007年的數據做測試集,剩下的用來擬合得出預測模型,然後再分別取2008年-2016年數據做同樣的操作,得出十個預測模型,從中選取最合適的模型。

1.3 從線性回歸到邏輯斯締回歸

1.1中講到了簡單的線性二分類的例子,在此引入邏輯斯締回歸概念,把簡單判斷樣本屬於某個類別升級為推測某個樣本被分到某個類別的概率。因此推測的結果永遠都在0和1之間。

線性二分類公式是這樣的

y=alpha +sum_{i=1}^{n}eta _{n}x_ {n}

引入邏輯斯締之後就是這樣:

p=P(y=1|X)=frac{e^{alpha +sum_{i=1}^{n}eta _{n}x_ {n}}}{1+e^{alpha +sum_{i=1}^{n}eta _{n}x_ {n}}}

或者

ln (frac{p}{1-p})=alpha +sum_{i=1}^{n}eta _{n}x_ {n}

在上例中,假設y=1代表男性,y=0代表女性,那麼如果根據擬合的函數,代入某個樣本的數據得出結果為0.2,那麼就意味著此人為男性的概率為e^0.2/(1+e^0.2)=54.98%.

如果要用邏輯斯締做分類,由於e^0/(1+e^0)=50%,因此多數情況下只要結果大於0.5就可以分類到y=1否則y=0。但這個分界值不一定合適,有時可以視情況稍作調整。

未完待續


我給你講個我講了快5年的真事。

以前有一次,我們在公司加班,晚了,就得點外賣。一團人,大概10幾個程序員,上到架構師下到實習生,圍著一張外賣單點餐,點完,半小時,快遞小哥送餐來了。1個實習生和兩個程序員就下去拿,我們坐餐廳等吃的。

10分鐘沒來,又下去一個人看看。

10分鐘沒來,又下去一個人看看。

還沒來,我們就全下去了,因為發生過快遞小哥襲擊保安,我們怕五個程序員打起來打不過一個快遞小哥。

好嗎,下去一看,4個程序員加一個架構師正跟快小哥那算帳呢,死活沒算出來,加入更多的人以後,採取了更多的演算法,導致更算不清楚,最後快遞小哥一揮手,震住全場:

一個個來拿!一個個交錢!

此時,我意識到了數學的重要性

然後開發了一個內部網站,專門計算外賣訂單 LOL

這沒什麼好覺得不對的,你試試算帳的時候同時有4個人在你耳邊要用不同的演算法算。


跟不懂數學的人討論問題就有點像下面這個感覺:

A:我們現在想討論一下,1有沒有可能是無理數?

B:所有的整數都是有理數,不是無理數,所以1不是無理數

A:哦,這樣啊,那看來1的確不是無理數了。那我們再重想一下,2有沒有可能是無理數?

B:不不我說了所有的整數都不是無理數了……

A:我們剛才不是在說1嘛,好了好了現在我懂了,2也不是無理數。那3呢?

B:……

很多人之所以會提出最後失敗的方案,並不是所謂「想的不夠全面」,是壓根就沒有用一種類似於數學證明的方法去考慮可行性,所以會得到「1不是無理數,2也不是,3好像也不是,但4好像是無理數」這樣的奇怪結果。


計算機圖形學 機器學習。看論文的時候。


我做應用開發10來年,有兩次覺得數學比較重要。

第一次是在Android上繪製一種類似蝌蚪尾巴的曲線,曲線會慢慢變細慢慢透明,類似這樣:

沒有現成的類庫可用,我只好跟蹤手指軌跡,自己計算路徑,這時候就用到向量什麼的……我忘完了啊,頭疼,意識到數學的重要性。

第二次是做一個射擊類的小遊戲,類似經典的泡泡龍那種,發射台可以調整方向,然後你發射子彈時,就要計算,你這顆子彈會不會射中目標。這個時候,就會用到初中還是高中學到的點斜式、三角函數之類的,我都忘光了,在網上查了半天,才明白怎麼回事。這時我意識到,即便是高中數學,對編程也是有幫助的。

即便你是做應用層面的開發,很少涉及演算法,數學的重要性也會在不經意間顯現出來。如果你是演算法研究和開發,那數學就是第一重要的,比編程語言、技術框架還要重要。


不懂數學的程序員,寫邏輯代碼是一點問題都沒有的。

但有些問題,知道其背後的數學本質,就可以把邏輯代碼寫得既簡單又全面,不知道的話,就會寫得繞來繞去的還解決不全面。這個道理我在做程序員之前就知道了。。。


高一下學期的時候想寫一個jpeg的解碼,看到dct的公式

我就知道,學好數學還是挺重要的,要不這都看不懂了。

不過之後也就是中學數學和大學計算機系的數學,沒有看特別的什麼數學教材。


恕我直言,部分答主的回答中用到的數學不過就是一些數學或者演算法層面的trick而已,並不是把真正複雜有深度的數學思維用在程序中。

想說的一個例子是,最近在搞的一個項目里正好用到了levelset(水平集),源代碼看不懂,目前只搞清楚這個演算法藉助了物理上氣球力的思想,最小化能量函數,其間各種泛函變分,老師講的時候我全程一臉懵逼。

講完以後,老師問我說:「你是工科出身沒學過變分,聽起來可能會有困難,怎麼樣你感覺能聽懂嗎?」

我:「額......」

老師一臉「我也很無奈啊我有什麼辦法」的表情:「因為......確實沒有什麼辦法......像曲線演化這些東西真的不是一天兩天的數學積累就可以學會的......只能辛苦你最近多研究研究了......」

我:


多數的程序員在工作中幾乎沒有用到高數,離散,線性代數等公式,但是數學思維與邏輯在編程中可是天天用到。

如何立刻知道兩個for循環要迭代多少次?如何立刻知道1000塊錢紅包應該要成功分10次100塊小紅包?

而不需要試運行程序。

數學首先是一種直覺,然後也是一種邏輯,數學好壞跟編程與否沒啥關係,但代碼效率的好壞可能就跟數學的邏輯思維有些關係。訓練對於大腦思維非常重要,恰恰數學是對思維最好的訓練,生活中各種場景都是要涉及到數學大大小小的計算、思考、直觀、推理等。看的出來,邏輯思維能力強的程序員,在接受學習《數據結構》的相關知識,一點都不覺得難。

所以編程語言只是「工具」,數學是最底層、核心的基礎東西,最終還是要回到原點上。


禮貌性謝邀。

當我發現用指數和對數計算演算法複雜度的時候,

當我發現級數可以用循環語句實現的時候,

當我發現斐波那契數列可以用動態規劃和分治演算法求解的時候,

當我發現 Hash 函數體現的是一種映射關係的時候,

當我發現用多項式時間複雜度來衡量P與NP的時候,

當我發現 與,或,異或,取反,取余,取模 是大部分編程語言都有的運算符的時候,

當我發現信息熵的公式里有對數也有級數的時候,

當我發現用積分做傅里葉變換的時候,

當我發現傅里葉變換可以做頻域分析,圖像增強的時候,

當我發現視頻編碼流程中的採樣,DCT,量化,編碼,每一步都是在做數學運算的時候,

當我發現計算 CRC 除數是生成多項式的時候,

當我發現 TensorFlow 中的張量為多維線性函數的時候,

當我翻開新買的那本機器學習,發現滿書的數學公式和數學概念的時候,

都在使我更加地堅信數學的重要性。

沒有哪個時刻讓我突然發覺數學的重要性,因為我從未懷疑過。


2015盞燈,一開始全部熄滅,序號分別是1-2015,
先把1的倍數序號的燈的開關全部按一次,
然後把2的倍數的燈的開關全部按一次,
然後把3的倍數的開關按一次,以此類推,
最後把2015的倍數燈的開關按一次。
問最後亮著的燈有多少盞?

——————————————————————————————————

按字面意思寫邏輯:

let run1 = (list:boolean[])=&>{
for(let i=1;i& {
_(list).forEach((record:boolean,k:number)=&>{
if( k % index === 0){
record = !record;
list[k] = record;
}
Times++;
})
}

——————————————————————————————————

優化一下邏輯:

let run4 = (list:boolean[])=&>{
let max = Math.ceil(list.length / 2);
for(let i=1;i&{
let Multiple = 1;
while(true){
Times++;
let targetIndex = Multiple * index;
if(targetIndex&>list.length){
break;
}
if(typeof list[targetIndex] !== "undefined"){
list[targetIndex] = !list[targetIndex];
}
Multiple++;
}
}

——————————————————————————————————

如果你懂數學:

當一個整數的因子數量為奇數,這個數一定是完全平方

let run5 = (num:number)=&>{
let count = 0;
for(let i=1;i&<=num;i++){ if(i*i&<=2015){ count++ }else{ break; } } console.log(count); }

————————————————————————————

第一個 4064255次

第二個 17684次

第三個 45次

完全是 數量級的優勢……

————————————————————————————


真實,用最優化數學方法,程序動態生成幾萬個變數方程,給個集團工廠解決原料優化問題,根據用量每年節省原料400到1000多萬元,浪費從人工的5%-9%降低到1%以下,用過貪心演算法,遺傳演算法,神經網路平均在3%以上不穩定,最優化數學方法己經到頂了再無優化空間。

數學是定式,是套路,是三十六計,是孫子兵法,數學是人類保存下來的最高智商,是個武器庫,不用白不用。

科學家時時刻刻想著把數學公式套在行業內使用,可能成為一代宗師,如果程序員把數學套在程序中使用,你的程序科學化程度智能化程度必定會提高很多,代碼如有神,會更有競爭力。


當你開始搞圖形學的時候。。。。


上大學時學演算法,老師留的作業都是ACM競賽難度的題,很多都是用數學公式就能解決的,數學並不好的我當時真的很頭疼。別人都能很快寫出代碼,簡潔且時間複雜度小,而我絞盡腦汁寫出的代碼還超時……

數學很重要,學習需認真!


意識到一個東西的重要性可能需要兩個條件:

1 你還不是很清楚其原理

2 這玩意對你有用,你需要它

就大部分編程需求來說(很多人寫業務代碼可能不會接觸到「演算法」),高中數學或者到大一大二的數學能力(指這些基礎教育培養出來的能力,實際具體東西好多人可能學了就忘)也夠了,如果這些數學已經成為你的已有知識,就可能給人一種「不重要」的印象

我第一次意識到或者說用到超出自己水平的數學知識,應該是初一學BASIC的時候,偶然發現一個Integer的平方結果不等於它乘以自身,用BASIC代碼說,就是n^2&<&>n*n,我們計算機老師當時也沒給我答案,後面過了一段時間才從不知道哪個雜誌看到原理:a^b=e^(b*lna),而e的冪和ln可以用機械的級數累加來做(別提上網搜,那時候google還沒成立( ̄▽ ̄)~*)


寫一個代碼從1加到100,當我寫for循環加的時候別人用高斯公式,我就知道寫代碼不是個簡簡單單擼的問題了,而是一個很嚴重的數學問題


程序員的「數學」和數學並不是同一個概念……我個人認為,對於程序員來說,數學最重要的意義不在於定義和解決各種複雜問題,而在於發現現實問題中的數學性質,從而能夠通過編程更好的解決問題(除非你對「程序員」的概念是那種只能在別人寫好的函數里填上不超過30行代碼的低端勞動力)

從我能夠區分開程序員和學計算機科學的人這兩個概念到我覺得程序員也需要數學之間,可能確實是有那麼一段時間間隔的。

當我意識到,更多的接觸的數學能讓人對現實有更明確的認識,比如意識到「程序員」三個字對不同人來說其實是不同的概念(語法和語義的分離);比如了解到我的某些檢索/瀏覽數據的行為其實完全可以由描述邏輯刻畫,進而明白什麼功能是可做的,什麼功能(在考慮成本的前提下)不能做。我就覺得程序員一樣是離不開數學的了。

業務邏輯中沒有數學?只不過是數學不好的人認不出隱藏在自己直覺背後的數學罷了。(當然從這個意義上說,數學很重要,學數學的性價比就要商榷了,你把自己當黑盒喂數據也算一種選擇,嘴上說不學,身體還是誠實的)


看了吳軍的數學之美,發現數學真的很強大,並完美的將數學應用到了計算機領域


推薦閱讀:

Rust中常量為什麼用let不用const,變數用let mut不用var?
c++現在有哪些GUI庫可以用?
計算機系學生的你,有哪些課程覺得自己沒有學明白?
為什麼函數能遞歸調用自己?
如何成長為一個優秀的C++程序員?

TAG:程序員 | 演算法 | 數學 | 編程 | 計算機科學 |