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