如何以計算機的方式去思考

2019-10-03 13:30:05

(給演算法愛好者加星標,修煉程式設計內功

作者:ChaosYang1987

https://www.cnblogs.com/chaosyang/p/11189445.html

從上大學第一天開始接觸程式設計,老師便給我們講過各式各樣的演算法。從各種查詢、排序,到遞迴、貪心等演算法,大一的時候一直在和這些演算法搏鬥。直到工作後,為了應付面試,仍不得不回過頭去啃演算法書或者去刷一些演算法習題,才能夠拾回一些上學時的記憶。為什麼演算法就這麼難以記住呢?或者說,為何計算機的演算法不能更直觀一些呢?

因為計算機的演算法就是反人性的,從本質上來說,這是計算機的思維方式和人腦思維方式的區別而造成的。


人腦思維的機制至今沒有一個確定的理論,暫時認為是化學物質和電訊號的作用。雖然沒有科學的解釋,但是我們每個人都有一顆大腦,我們每個人都可以感受到自己的思維方式。


而計算機則是人類創造的,從設計之初它便不是以模擬人腦為目的,因此它有其獨特的工作方式,只有理解了計算機的工作方式,才可以學會以它的方式去思考, 才可以寫出最適合計算機執行的程式程式碼。


在排序陣列中尋找特定數字 —— 人腦 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的優點也是人腦所無法比擬的:


  1. 雖然CPU只會幹簡單的事情(幾百種指令),但是它可以在固定的時間(指令執行時間)內保證正確的運算出正確的結果。而人腦不可能保證在固定的時間內一定產生“同樣”的思維結果。

  2. 現代化的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需要做三件事才可以完成這工作:


  1. 通過ADD指令,根據array的地址(r2)和i(r4)的數字,計算需要讀取的記憶體地址

  2. 通過LOAD指令將記憶體地址對應的數載入到暫存器(r3)

  3. 通過CMP指令比較num(r1)和r3的值,結果儲存在結果儲存器中


而根據操作3的結果,如果結果不相等,則CPU需要將迴圈計數器i加上1存入暫存器r4,再次進行上面的計算。所不同的是,第二到第N次的步驟二會比第一次要快很多,因為整個陣列的內容已經被快取記憶體所捕獲。


所以,我們可以看出為何計算機在解決這個問題上顯得如此愚笨:


  1. 計算機的輸入收到限制。計算機一次只能讀入單個值(有快取記憶體的幫助這並不太糟糕),且在暫存器中放有限的幾個值,而人類可以通過視覺等一次性讀入多個值儲存在腦海中。

  2. 計算機的指令有限制,只能支援基本的運算指令。而人腦可以有豐富的指令,比如直接通過一堆剛剛看到的數字中視覺模式匹配出13這個數字。


在排序陣列中尋找特定數字 —— 人腦 vs 計算機 round 2


計算機在上一輪和人腦的PK中敗下陣來,然而這並不是很公平,因為陣列的數量只有短短的幾個,而計算機可以儲存的上限遠不止於如此。於是我們開始第二次的比拼。這次我們將輸入擴大


1 2 3 5 7 13 34 67 90 127 308 502 ... 2341245 ... (100萬個

查詢的數變成了2341245。


這次人腦和計算機的表現又如何呢?


對於一個普通人,我們假設這100萬個數字是列印在一本字典裡的,那麼他如何找出100萬個有序陣列中的某個數字呢?


這時人類引以自豪的“一目十行”的能力已經微乎其微,當數字的位數增大時,且不說一眼比較一個數字是否和目標數字相同已經困難,即使真的有一目十行的本事,在100萬這樣的數字面前也是微乎其微。


於是乎,我們老老實實的去從頭到尾比較數字,一頁一頁的翻開,去看當前的頁中有沒有數字,沒有的話就去翻下一頁。


這個思路是不是很熟悉?沒錯,這就是計算機的思維,和我們上一節中所描述的計算機編碼幾乎是一樣的,除了人可以一眼多看幾個資料外。


然而,人類在比較大數是否相等的速度,以及翻字典的速度可遠遠比不上計算機去讀完這100萬個數的速度,同樣是“笨鳥”,計算機每秒百萬次的運算能力幾乎可以在瞬間就完成這樣的任務。


也就是說,在大規模輸入的情況下,人腦的思維方式“退化”成和計算機近似,但是被計算機壓倒性的效能優勢給擊敗。


在排序陣列中尋找特定數字 —— 人腦 vs 計算機 round 3


在第二輪中,人腦敗給了計算機,但這樣的比拼無疑於兩隻笨鳥比誰更快。有沒有聰明一些的方法呢?


沒錯,我們學過二分查詢(Binary Search)的演算法可以派上用場了。


步驟一:有這麼有一本列印了100萬個數字的字典擺在我們的面前,我們不知道要找的數字會在哪裡,那麼我們先折半開啟字典(不用那麼精確也沒關係),看當前頁的第一個數字和最後一個數字,我們要找的數字是否在這個範圍內,如果在那麼我們可以繼續在當前頁找這個數字。


步驟二:如果當前頁的第一個數字還是比我們要找的數字大,那麼我們可以將字典的後半部分撕了(因為我們要找的數字不可能在後半部分了),繼續上面的步驟。


步驟三:如果當前頁的最後一個數字比我們要找的數字小,那麼我們可以將字典的前半部分撕了(理由同上),繼續步驟一。


這樣我們會講這本字典越撕越薄,最壞的情況下我們會撕到最後一頁,這一頁要麼有這個數字,要麼沒有這個數字,但是我們保證按照上面的步驟進行我們不會錯過任何可能含有這個數字一頁。


這個邏輯和計算機演算法中的二分查詢原理是一樣的,我們來看看實際的演算法程式碼是如何實現的


boolean isNumInArray(int num, int[] array, int start, int end) {        if(num  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]         return isNumInArray(arr, key, middle + 1, end); //撕掉前一半    }else {        return middle;    }   }


我們可以看出,和人類的思維方式比,計算機不會翻“一頁”,它只會翻看一個數字,但是其他的思維方式是一模一樣的。利用這樣的演算法,人類雖然從結果上還是比計算機要慢,但是雙方都找到了最適合的方法,達到自我效率的最大提升。

在排序陣列中尋找特定數字 —— 更多的思考

那麼我們回過頭來看,為什麼我要假設這100萬數字列印在字典上呢?因為字典和計算機記憶體的模型很像。

計算機可以通過記憶體地址來直接訪問記憶體,這一點和通過字典的頁碼來翻到某一頁,這一點是近似的。

在計算機編碼中我們可以知道陣列的長度,而通過折半的方法找到中間的數,字典有厚度,我們可以通過厚度減半來找到中間的頁碼,這一點也是相似的。

試想一樣,如果100萬的數字不是列印在字典,而是印在一條公路上,我們是否還可以用上一節的演算法來人肉二分查詢?答案是不可以,因為跑到公路的一半會消耗你很多的體力,如果採用二分法查詢比起round 1中的最笨辦法只會讓你耗費更多的體力。因為公路這一儲存的概念,對應的便不是記憶體的模型,而是磁帶(Tape)的模型,那麼對於這樣的模型,我相信不論是人或者是計算機, 都需要調整演算法,來達到最高的效率。

總結

通過以上的例子,我們可以看到,計算機的演算法反人性,是因為計算機不是一個“正常人”,它有自己的缺陷,也有自己的長處。很多時候我們覺的演算法不直觀,不是因為我們的思維能力比計算機差,而恰恰是因為作為人類我們同時接觸的資訊太多,所會的東西也太多而阻塞了我們的思維。那麼這種時候,不妨將自己“墮落”成一臺“鼠目寸光”和“所知甚少”的計算機,這時可能會有更清晰的思路。


推薦閱讀

(點選標題可跳轉閱讀)

計算機如何感知大資料——聚類演算法

那些計算機界的偉大女性



覺得本文有幫助?請分享給更多人

關注「演算法愛好者」加星標,修煉程式設計內功

好文章,我在看❤️

已同步到看一看



熱點新聞