如何以計算機的方式去思考
點擊上方藍色字體，選擇“標星公眾號”
優(yōu)質(zhì)文章，第一時間送達
作者 | ChaosYang1987
來源 | urlify.cn/eamqQz
從上大學第一天開始接觸編程，老師便給我們講過各式各樣的算法。從各種查找、排序，到遞歸、貪心等算法，大一的時候一直在和這些算法搏斗。直到工作后，為了應付面試，仍不得不回過頭去啃算法書或者去刷一些算法習題，才能夠拾回一些上學時的記憶。為什么算法就這么難以記住呢？或者說，為何計算機的算法不能更直觀一些呢？
因為計算機的算法就是反人性的，從本質(zhì)上來說，這是計算機的思維方式和人腦思維方式的區(qū)別而造成的。
人腦思維的機制至今沒有一個確定的理論，暫時認為是化學物質(zhì)和電信號的作用。雖然沒有科學的解釋，但是我們每個人都有一顆大腦，我們每個人都可以感受到自己的思維方式。
而計算機則是人類創(chuàng)造的，從設計之初它便不是以模擬人腦為目的，因此它有其獨特的工作方式，只有理解了計算機的工作方式，才可以學會以它的方式去思考， 才可以寫出最適合計算機運行的程序代碼。
在排序數(shù)組中尋找特定數(shù)字 —— 人腦 vs 計算機 round 1
我們通過一個具體的例子，來說明人腦和計算機的思維方式不同，假設我們想要從一個已經(jīng)排好序的數(shù)組中找出一個特定的數(shù)字。
已知排序好的數(shù)組是1 2 3 5 7 13 34 67 90 127 308，我們希望找到是否13這個數(shù)在數(shù)組內(nèi)。
人腦是如何去完成任務的呢？
人腦處理這樣的問題幾乎是“作弊”的，我們可以一目十行，我們在眼鏡一掃視的情況下就發(fā)現(xiàn)了13，所以如果我問自己我是如何找到13的，我只能說我“看見”了。
而計算機是如何來完成這個任務呢？
最簡單也是最笨的算法就是從數(shù)組開始一個一個的讀入數(shù)組，我相信每個學習過編程基礎的同學都可以寫出類似下面的代碼。
boolean isNumInArray(int num, int[] array) {
for (int i = 0; i < array.length; i++) {
if (array[i] == num) {
return true;
}
}
return false;
}
計算機需要從數(shù)組的第一個元素開始，一個一個的去查當前的數(shù)組的元素，和13相比，看看是不是相等。為了找出13這個數(shù)，計算機要做6次循環(huán)操作，而人幾乎是瞬間就看到了答案。
為何計算機解決問題的方式這么“笨”呢？我們先得從計算機的工作原理說起。
CPU的工作方式
CPU作為計算機的最核心的部件，也是算法的主要運載體。
CPU并不會像人一樣思考，它只懂得一些基本的指令。每一個CPU都有其指令集，指令集是存儲在CPU內(nèi)部，對CPU運算進行指導和優(yōu)化的硬程序。通俗一點說，指令集就是CPU的所有思維方式。比如常見的指令集中都會有ADD指令，這個指令可以將兩個寄存器中的值相加，并將存儲到另一個寄存器中；與此相對應的也會有SUB指令，用于將兩個寄存器值相減。如果你去查閱各種CPU指令集的手冊，會發(fā)現(xiàn)基本上都會包含基本的加減乘除指令，以及向內(nèi)存中存、取數(shù)據(jù)的指令。而常見的CPU指令集，最多也就是幾百條指令。也就是說CPU只會這幾百個命令。
而人腦相對于CPU，有強大的記憶和聯(lián)想能力，比如你看到1+1，就想到2，看到紅燈，就會想到停下來，看到門，就知道去開門把手，這些都是你不假思索可以立刻反映出來的東西。
所以，CPU會的東西（指令）比人少多了，那CPU豈不是很笨？沒錯，CPU就是很笨，但是CPU的優(yōu)點也是人腦所無法比擬的：
雖然CPU只會干簡單的事情（幾百種指令），但是它可以在固定的時間（指令執(zhí)行時間）內(nèi)保證正確的運算出正確的結(jié)果。而人腦不可能保證在固定的時間內(nèi)一定產(chǎn)生“同樣”的思維結(jié)果。
現(xiàn)代化的CPU工藝可以在一秒鐘內(nèi)執(zhí)行百萬次以上的指令，而人腦的思維速度則比不上，我們一個“念頭”最短也需要零點零幾秒的反應時間。
綜上所述，CPU是一個既笨又快的家伙。
計算機存儲
計算機的常見存儲有寄存器、高速緩存、內(nèi)存、硬盤等。
寄存器就相當于人腦中立刻可以想起來的東西，CPU所做的一切運算都是針對于在寄存器中的數(shù)據(jù)進行的。寄存器存儲了計算機當前要做什么計算（指令寄存器），要計算的數(shù)據(jù)（數(shù)據(jù)寄存器），計算到哪一步了（段寄存器）等信息。無論是最早的有寄存器的CPU還是最新最強的的CPU，它們的寄存器數(shù)量最多也只有幾十個（特殊情況有幾百個），也就是說CPU同一時刻能夠立刻使用過的信息也就是這幾十個數(shù)字。
內(nèi)存則是計算機的主力存儲設施，它可以存儲運行中的程序的信息，內(nèi)存相當于圖書館的書架，CPU需要用某一段內(nèi)存中的數(shù)據(jù)是，需要通過LOAD指令，同時附上一個書架編號（內(nèi)存地址），然后內(nèi)存控制器可以將對應的地址的數(shù)據(jù)通過總線傳輸給CPU，CPU則將載入的結(jié)果放入寄存器中使用。內(nèi)存存取的速度遠小于寄存器，但是訪問分布在內(nèi)存各個區(qū)間的數(shù)據(jù)的速度基本是相等的。
由于大部分時候CPU需要讀取連續(xù)的一段內(nèi)存來進行運算，因此通常CPU會有高速緩存將最近使用過的內(nèi)存整塊緩存起來，而使得CPU不必每執(zhí)行一步就需要去讀一次內(nèi)存。高速緩存的速度介于寄存器和內(nèi)存之間，但遠高于內(nèi)存。高速緩存的大小一般在幾兆到十幾兆之間。
硬盤屬于外部存儲，老式的機械硬盤中會有一個可轉(zhuǎn)的磁頭，在讀取磁盤文件的時候需要將磁頭轉(zhuǎn)到對應的位置，磁盤的速度遠低于內(nèi)存，并且如果磁盤的磁頭如果停留在某個位置時，隨機磁盤上不同位置的信息，會受到磁頭運動的物理速度限制而出現(xiàn)速度不均等的情況。新式的固態(tài)硬盤采用了和內(nèi)存相似的存儲介質(zhì)，在隨機訪問的性能上提升很大。
所以，計算機有一顆只能記得一點點事情的小腦袋（寄存器），但是能夠擁有相對較大的快速記憶（緩存），擁有遠超過人類的知識儲備（內(nèi)存），并且還隨身攜帶了巨大的移動圖書館（硬盤），所以從存儲上來看，計算機像是一個有先天缺陷的雨人（Rain Man）。
所以，我們來分析一下round 1中為何計算機到底做了怎樣的操作？
首先我們看我們函數(shù)的定義
boolean isNumInArray(int num, int[] array)
在調(diào)用函數(shù)的底層實現(xiàn)中，參數(shù)是被分配到兩個寄存器中。isNumInArray這個函數(shù)，在被調(diào)用時，第一個參數(shù)num的值13會被載入到寄存器（r1）， 的第二個參數(shù)array，傳入CPU的時候就只是array在內(nèi)存中的地址信息，被存儲在另一個寄存器（r2）。
而在第四行array[i] == num時，CPU需要做三件事才可以完成這工作：
通過ADD指令，根據(jù)array的地址（r2）和i（r4）的數(shù)字，計算需要讀取的內(nèi)存地址
通過LOAD指令將內(nèi)存地址對應的數(shù)載入到寄存器（r3）
通過CMP指令比較num（r1）和r3的值，結(jié)果存儲在結(jié)果存儲器中
而根據(jù)操作3的結(jié)果，如果結(jié)果不相等，則CPU需要將循環(huán)計數(shù)器i加上1存入寄存器r4，再次進行上面的計算。所不同的是，第二到第N次的步驟二會比第一次要快很多，因為整個數(shù)組的內(nèi)容已經(jīng)被高速緩存所捕獲。
所以，我們可以看出為何計算機在解決這個問題上顯得如此愚笨：
計算機的輸入收到限制。計算機一次只能讀入單個值（有高速緩存的幫助這并不太糟糕），且在寄存器中放有限的幾個值，而人類可以通過視覺等一次性讀入多個值存儲在腦海中。
計算機的指令有限制，只能支持基本的運算指令。而人腦可以有豐富的指令，比如直接通過一堆剛剛看到的數(shù)字中視覺模式匹配出13這個數(shù)字。
在排序數(shù)組中尋找特定數(shù)字 —— 人腦 vs 計算機 round 2
計算機在上一輪和人腦的PK中敗下陣來，然而這并不是很公平，因為數(shù)組的數(shù)量只有短短的幾個，而計算機可以存儲的上限遠不止于如此。于是我們開始第二次的比拼。這次我們將輸入擴大
1 2 3 5 7 13 34 67 90 127 308 502 ... 2341245 ... （100萬個
查找的數(shù)變成了2341245。
這次人腦和計算機的表現(xiàn)又如何呢？
對于一個普通人，我們假設這100萬個數(shù)字是打印在一本字典里的，那么他如何找出100萬個有序數(shù)組中的某個數(shù)字呢？
這時人類引以自豪的“一目十行”的能力已經(jīng)微乎其微，當數(shù)字的位數(shù)增大時，且不說一眼比較一個數(shù)字是否和目標數(shù)字相同已經(jīng)困難，即使真的有一目十行的本事，在100萬這樣的數(shù)字面前也是微乎其微。
于是乎，我們老老實實的去從頭到尾比較數(shù)字，一頁一頁的翻開，去看當前的頁中有沒有數(shù)字，沒有的話就去翻下一頁。
這個思路是不是很熟悉？沒錯，這就是計算機的思維，和我們上一節(jié)中所描述的計算機編碼幾乎是一樣的，除了人可以一眼多看幾個數(shù)據(jù)外。
然而，人類在比較大數(shù)是否相等的速度，以及翻字典的速度可遠遠比不上計算機去讀完這100萬個數(shù)的速度，同樣是“笨鳥”，計算機每秒百萬次的運算能力幾乎可以在瞬間就完成這樣的任務。
也就是說，在大規(guī)模輸入的情況下，人腦的思維方式“退化”成和計算機近似，但是被計算機壓倒性的性能優(yōu)勢給擊敗。
在排序數(shù)組中尋找特定數(shù)字 —— 人腦 vs 計算機 round 3
在第二輪中，人腦敗給了計算機，但這樣的比拼無疑于兩只笨鳥比誰更快。有沒有聰明一些的方法呢？
沒錯，我們學過二分查找（Binary Search）的算法可以派上用場了。
步驟一：有這么有一本打印了100萬個數(shù)字的字典擺在我們的面前，我們不知道要找的數(shù)字會在哪里，那么我們先折半打開字典（不用那么精確也沒關系），看當前頁的第一個數(shù)字和最后一個數(shù)字，我們要找的數(shù)字是否在這個范圍內(nèi)，如果在那么我們可以繼續(xù)在當前頁找這個數(shù)字。
步驟二：如果當前頁的第一個數(shù)字還是比我們要找的數(shù)字大，那么我們可以將字典的后半部分撕了（因為我們要找的數(shù)字不可能在后半部分了），繼續(xù)上面的步驟。
步驟三：如果當前頁的最后一個數(shù)字比我們要找的數(shù)字小，那么我們可以將字典的前半部分撕了（理由同上），繼續(xù)步驟一。
這樣我們會講這本字典越撕越薄，最壞的情況下我們會撕到最后一頁，這一頁要么有這個數(shù)字，要么沒有這個數(shù)字，但是我們保證按照上面的步驟進行我們不會錯過任何可能含有這個數(shù)字一頁。
這個邏輯和計算機算法中的二分查找原理是一樣的，我們來看看實際的算法代碼是如何實現(xiàn)的
boolean isNumInArray(int num, int[] array, int start, int end) {
if(num < arr[start] || key > arr[end] || start > end){
return false;
}
int middle = (start + end) / 2; //找到對折點
if(array[middle] > num) {
return isNumInArray(arr, key, start, middle - 1); //撕掉后一半
} else if(array[middle] < num){
return isNumInArray(arr, key, middle + 1, end); //撕掉前一半
}else {
return middle;
}
}
我們可以看出，和人類的思維方式比，計算機不會翻“一頁”，它只會翻看一個數(shù)字，但是其他的思維方式是一模一樣的。利用這樣的算法，人類雖然從結(jié)果上還是比計算機要慢，但是雙方都找到了最適合的方法，達到自我效率的最大提升。
在排序數(shù)組中尋找特定數(shù)字 —— 更多的思考
那么我們回過頭來看，為什么我要假設這100萬數(shù)字打印在字典上呢？因為字典和計算機內(nèi)存的模型很像。
計算機可以通過內(nèi)存地址來直接訪問內(nèi)存，這一點和通過字典的頁碼來翻到某一頁，這一點是近似的。
在計算機編碼中我們可以知道數(shù)組的長度，而通過折半的方法找到中間的數(shù)，字典有厚度，我們可以通過厚度減半來找到中間的頁碼，這一點也是相似的。
試想一樣，如果100萬的數(shù)字不是打印在字典，而是印在一條公路上，我們是否還可以用上一節(jié)的算法來人肉二分查找？答案是不可以，因為跑到公路的一半會消耗你很多的體力，如果采用二分法查找比起round 1中的最笨辦法只會讓你耗費更多的體力。因為公路這一存儲的概念，對應的便不是內(nèi)存的模型，而是磁帶（Tape）的模型，那么對于這樣的模型，我相信不論是人或者是計算機， 都需要調(diào)整算法，來達到最高的效率。
總結(jié)
通過以上的例子，我們可以看到，計算機的算法反人性，是因為計算機不是一個“正常人”，它有自己的缺陷，也有自己的長處。很多時候我們覺的算法不直觀，不是因為我們的思維能力比計算機差，而恰恰是因為作為人類我們同時接觸的信息太多，所會的東西也太多而阻塞了我們的思維。那么這種時候，不妨將自己“墮落”成一臺“鼠目寸光”和“所知甚少”的計算機，這時可能會有更清晰的思路。
鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布
??????
??長按上方微信二維碼 2 秒
感謝點贊支持下哈 