NO IMAGE
目錄

導航

定位
概述
出發
0與1
原子資料
   字元
   整數
   字串
   布林
   十六進位制
   變數
   常量
   初始化
   地址
   指標
原子控制
   指令
   彙編
   拷貝與位運算
   編譯器與程式語言
資料與控制
編碼
小結
第一站-初識結構
基本資料結構
   陣列
   連結串列
  
   佇列
   聯合
   元組
   點陣圖
   列表
   集合
   對映
   變體
   巢狀
   圖示
   小結
基本控制結構
   程式碼塊
   分支
   選擇
   迴圈
   函式
小結
第二站-中級結構
中級資料結構
   多維陣列
   二叉樹
   模板
   快取
中級控制結構
   迭代
   遍歷
   遞迴
   中斷
   回撥
   回滾
   流計算
   閉包
   Curry
小結
第三站-高階結構
高階資料結構
  
   正則
   物件
高階控制結構
   設計模式
   非同步
   併發
通訊協議
小結
第四站-應用
應用資料結構
   JSON
   XML
   記錄文字
   關係型資料庫
   key-value型資料庫
應用控制結構
   API
   應用框架
元件
控制元件
分散式
網際網路
小結
軟體之道的思考
效能與效率
健壯性
可擴充套件性
儲存設計與請求構造
配置式的軟體通用框架
程式設計之道
資料-結構-控制-流
路線圖
結語

定位

本文適合於有基本的教育經歷、對程式設計世界瞭解很少、希望從事程式設計開發工作或者需要與技術GGJJDDMM們進行溝通的筒鞋。

讀完本文,你只需要一點做人的基礎:
1. 具備軟體使用經歷;
2. 數學四則運算能力;
3. 舉一反三的悟性;
4. 耐心。

本文不是論述程式設計知識或技能或技術的專著,而是會提綱挈領、點到為止地談及程式設計的基本知識和主要思想,—— 所以說要求有舉一反三的悟性嘛!O(∩_∩)O 。此外,文章比較長,特別需要耐心噢!

概述

嘗數思程式設計及程式設計活動之根本,不得其解。經過仔細思考,結合學習與工作中的程式設計開發實踐,我逐漸意識到,程式設計的根本和精髓在於結構程式設計。這裡的結構程式設計並不是指常見的三種結構(順序、條件、迴圈)以及過程化程式設計,也不是指狹義的資料結構與演算法程式設計,而是指標對任何具有結構的可計算物件的程式設計。正如萬物皆由不計其數的原子通過多樣的結構和方式奇蹟般地創造,計算世界則是由不計其數的0和1通過多樣的結構和方式奇妙地構建。我們將從0和1出發,在結構之神的指引下,經過且行且停的旅程,直至欣賞到瑰麗華美的現代網際網路大廈。

合抱之木,生於毫末;九層之臺,起於累土; 千里之行,始於足下。

出發

Are you ready ? Go !

0與1

在可預見的很長一段時間,計算世界仍然是由 0 和 1 組成的。 無論是字母、數字、圖表、網頁、動畫、超酷炫的特效等,在計算底層看來,都是流暢的一系列01數字串,就像硬體只會看到一團極其壯麗的電子流一樣。我們的旅程從這裡出發。

原子資料

計算世界的原子資料通常包括字元、整數、字串、布林量、浮點數。 開啟某種程式語言的入門書籍,第二章通常都會是變數,以及變數的若干基本型別。

字元

最先映入眼簾的,大概就是字母表。大小寫的 ABCDEFG, HIJKLMN,OPQRST,UVWXYZ。 咋看上去,似乎沒有什麼結構,都是單個的字母。實際上,在計算機內部,任何字母都是一個位元組8位的01串編碼而成的,通過ASCII 碼錶來進行對映。比如A,ASCII碼值是65,對應的01串是 01000001。 單個數字以及其他控制字元,也是通過 ASCII 碼錶來標識的。可以百度或谷歌 ASCII 瞭解詳情。由此認識到: 字元是 8 位01串。後面會知道,這裡的“串”可以理解為一種“陣列”。

整數

接著為人所熟知的,便是整數。 同字元類似,整數也是01串。不過由於整數比較大,一個位元組8位可能存不下,因此需要多個位元組。Java程式語言裡,整數是4個位元組32位01串,可以表示的數值是 -2^31 ~ 2^31-1. 還有長整數 8 個位元組 64 位 01 串,可以表示的數值是 -2^63 ~ 2^63-1 . 拿整數 10000 來說,可以表示為 00000000 00000000 00100111 00010000 , 可以使用 python 的 bin(10000) 方法來獲取10000的二進位制表示,也可以使用python 的 int(‘00000000000000000010011100010000’, 2) 來獲取二進位制表示的整數。關於二進位制如何表示整數,有一套模2取餘的演算法;而如何表示負整數,則要涉及到反碼和補碼計算。詳情可百度或谷歌。由此認識到,整數,實際上也是若干位01串。

字串

字串大概是計算世界裡處理得最最多的原子資料了。任何文字都是字串。字串其實是由字元組成的序列,比如 “ABC” 就是 [“A”, “B”, “C”]。因此字串編碼為01串,就是把字串中的每個字元都編碼為01串,然後串聯起來:010000010100001001000011.

布林

布林型別就是 True 和 False , 真與假。 用於各種條件判斷中。

十六進位制

寫成01串實在太痛苦啦,也不直觀。因此先輩們發明了十六進位制。實際上,二進位制,十進位制,十六進位制,都是表示計數的一種方法。 N 進位制,就是用 0~N-1的數字(N<=10)或0-9, N-10個字母(N>10)來表示所有的整數。十進位制,就是用 0-9 來表示整數; 十六進位制,就是用 0-9, A-F 來表示整數。 N 表示進位數,逢N進一。十進位制轉十六進位制,採用模N取餘的方法來確定各個位的數字。比如 24, 可以表示 2*10 4; 也可以表示成 1*16 8, 即0x18 , 0x 表示使用十六進位制計數法。使用python的hex(24)即可獲得24的十六進位制表示。 有了十六進位制,表示大量的01串,媽媽再也不用為我擔心啦!

變數

前面講了原子資料字元、整數、字串、布林,那麼在程式裡怎麼使用這些原子資料呢?變數是用於儲存這些值並引用的。 比如 x = “i am java programmer” , x 就是個變數。 給變數指定某個值的動作叫“賦值”。變數在程式的不同地方可以重新賦值,比如 x = “now i am mixed coder. haha!”

常量

常量也是可以指定和儲存原子資料值的地方,不過常量在初始化完成後就不能改變了。比如光速在真空中的速度、圓周率PI 、自然常數、預設引數配置等。

初始化

變數與常量都是資料引用。初始化是指為一個資料引用第一次賦值的過程。int x; 這只是宣告瞭一個整數變數 x,而沒有初始化這個變數; 而 int x = 1 就為 x 完成了初始化工作,賦予初始值 1 。初始化也稱為“宣告並定義了”。

地址

“賦值”是個邏輯意義的操作,比如 x = “i am java programmer”, 是將字串賦值給變數 x , 這是從自然語言的角度理解; 從計算機儲存和執行的角度來理解,必然要為這個字串分配一個記憶體來存放,這就存在變數的記憶體地址 d = 0xb708a410。使用python的id(x)可以列印x的地址。現在我們知道變數有雙重身份啦: 一個是變數指代的值 v ,一個是儲存變數值使用的記憶體地址 d。

指標

上面講了地址的概念。指標就是用來存放地址 d 的資料引用 p, 可以通過指標來操作變數的值。 比如說,x = “i am java programmer” , x 的地址是 d = 0xb708a410 ,那麼 p = 0xb708a410 ; 如果想將 x 的值變成 “i am mixed now.” , 那麼可以使用 x = “i am mixed now.”; 也可以使用指標 (*p) = “i am mixed now.”. *p 的含義就是取出變數 p 所存放的變數地址所指代的變數的值。是不是有點拐彎抹角? 別擔心,很多中高階程式yuan 都在指標上栽了很多次的跟頭 ~~

原子控制

指令

指令由操作碼和運算元組成。運算元就是前面所說的各種原子資料;操作碼是預先定義好的01串。比如在8位系統上,定義: 10000000 表示加法, 11000000 表示減法。最高2位表示操作碼,其他位表示運算元。 那麼, 10000000 00000001 00000010 就表示 1 2 , 11000000 00000010 00000001 表示 2-1。實際指令可以比這更復雜,但原理是一樣的。指令由CPU來執行完成。

彙編

程式yuan,或者碼農就是靠編寫指令為生的。不過要編寫這麼多01串,恐怕吃飯都要吐出來的。於是,程式猿中的先驅們發明了彙編。 彙編對指令並沒有實質性的改變,僅僅是對指令做了個助記符或者說是命名,不過這個命名產生的意義卻是非凡的!比如 10000000 簡記為 ADD,11000000 簡記為 SUB, 那麼上面的指令就可以寫成, ADD 0x01 0x02 , SUB 0x02 0x01 ,是不是更直觀了?

拷貝與位運算

別看計算機能勝任超級廣泛的任務,其實它只會兩件事:拷貝與位運算。拷貝,就是將一個值從一個地方挪到另一個地方:我只是大自然的搬運工,哈哈!位運算,就是將指定的運算元的各個位進行運算(與或非)得到新的值。要問計算機為什麼能勝任各種各樣的事情,其實都是可以拆解為拷貝與位運算。比如我們使用手機聊天,其實就是把資料資訊從一個手機拷貝到另一個手機上而已。當然,為了安全的考慮,需要對資料資訊進行加密。而加密則無非是一大串的數學計算。任何數學計算都可以通過位運算來完成。就這麼簡單! 是不是很神奇?

編譯器與程式語言

使用匯編寫程式,仍然是很困難的,稍微大點的程式就讓人頭髮掉光光。如果 ADD 0x01 0x02 能夠直接寫成 1 2 豈不是更好? 於是,編譯器和程式語言發明出來了。 程式語言,就是用自然人容易懂的語言來編寫程式,而編譯器則負責將其翻譯成機器能懂的二進位制指令;這樣,只要我能編寫出編譯器認得的程式,一樣能夠在計算機上執行, 而要讓編譯器認得寫出的程式,就要符合程式語言指定的語法規則。這其實跟自然語言很類似,只是程式語言更精確嚴謹些,比自然語言的容錯能力更低一些。為什麼猿媛們這麼愛細節呢?是因為計算機太太認真啦!

有了編譯器和程式語言,現在我們終於能用人話來談論程式設計了!

資料與控制

處理什麼資料? 怎樣處理資料?如何組織大量指令來完成指定目標? 這三個問題構成了程式設計的中心問題。
* 處理什麼資料,是程式設計需求所決定的, 也是由觀察世界的角度來產生的;
* 怎麼處理資料,包括如何採集、容納、傳輸、儲存、組織、加工、展示資料; 這一步產生出許多技術手段;
* 怎麼組織指令,涉及到指令的組織結構,控制指令的執行路徑;

因此,程式設計的中心問題,轉化為“資料結構”與“控制結構”的問題。值得提及的一點是,資料的含義,也包括資料之間的關聯。

編碼

將字元、整數、字串、指令轉換成01串,實際上就是編碼了。編碼是指將現實中的萬事萬物編碼成01串的操作。神乎其技兮!

現在,讓我們來一次“物件程式設計”。假設我們要對物件編碼(這是要逆天麼)。物件有很多特徵,身高、體重、愛好等等,不過我們很難全部覆蓋。那麼就針對身高、體重和最愛的菜吧。這就是抽象。抽象就是從現實事物的諸多特徵中萃取出真正要研究的那些特徵。

確定要編碼身高、體重和最愛的菜之後,就可以思考如何表示了。可以使用變數 height 表示身高,使用變數 weight 表示體重, 使用變數 favorite 表示最愛。假設身高是 168cm, 體重是 100 kg, 最愛的是番茄炒雞蛋。 那麼,身高和體重, 可以使用整數, 最愛可以使用字串。比如 int height = 168 , weight = 100 , String favorite = “番茄炒雞蛋”。 int 是Java語言中表示整數的型別, String 是 Java 語言中表示字串的型別。使用十六進位制表示 height = 0xa8 ; weight = 0x64;favorite=0x795aae88c84e78292e9b8a1e89b8b。十進位制轉十六進位制,使用 python 的 hex 函式。計算機在執行的時候,必定要為這三個變數分配記憶體空間,比如 d_height = 0x08cce04c, d_weight = 0x08ccdbc4 , d_favorite=0xb708fd90。

各種原子資料的編碼:

恭喜你!一下子掌握了程式設計的兩個最精髓的概念: 抽象與編碼。

小結

在這一站裡,我們瞭解了程式裡的原子資料和原子控制。這些是我們理解程式如何執行的基礎。事實上, 無論多麼複雜的程式或軟體,資料都將被編碼成01串,程式碼都將被編譯器翻譯成01串,從而被計算機識別和執行。當然,要編寫和理解大型程式,僅僅有這些基本知識和思想是不夠的。但是,我們已經很勇敢地邁出了第一步,就像人類探索浩瀚宇宙的登月之旅。

稍稍休息,接著,我們將正式踏上旅途。

第一站-初識結構

基本資料結構

原子型別的變數就像非正規的散兵,雖然有初步的戰鬥力,可是這戰鬥力是很弱的。假設你有十個蘋果要發給某人,很難說一個一個蘋果發過去,多半是把十個蘋果打包成一箱後一起發過去。這個“箱”就是結構。結構是任何可以容納多個事物的事物。被容納的事物,稱為元素, 既可以是原子型別的值,也可以是結構本身。嗯,這裡面就包含了遞迴的思想。

陣列

陣列是最基本的資料結構。往連續的固定空間連續儲存一系列相同型別的值,就構成了陣列。比如 [1,2,3], [‘A’,’B’, ‘C’] 或者 [“I”, “have”, “a”, “dream”] 。 陣列的操作也很簡單直接:設定或取出指定位置的值,指定位置使用下標來表示。比如 [1,2,3],取出下標為 0 的值是1。如果設定下標為2的值為10,那麼陣列就變成[1,2,10]。最大的下標是2,也就是陣列長度減去一。注意,下標是從0開始算起的,第一個這麼設計的程式設計師一定是天才,思維與常人如此不同!這個傳統被沿襲下來,從此所有程式yuan都與普通人的思維有所不同~~~

連結串列

假設有若干人站成一列玩遊戲,每個人用雙手搭在前面人的肩膀上,就形成了連結串列。當我們要找到某個人時,可以從最後那個手搭著別人肩的人開始,根據手到肩的指向數過來,直到找到那個人為止。

相同型別的值使用指標相互連線起來,就組成了連結串列。比如 1 -> 2 -> 3 -> 4 。 連結串列不能像陣列那樣指定位置來設定或取值,而是要通過指標遍歷一個個數過去。但連結串列是容易高效擴充套件的,比如要把 5 插入到 3 與 4 之間, 只要把3指向5,5指向4,就OK 了: 1->2->3->5->4 。

連結串列是元素通過指標指向來形成關聯的結構。

假設我們要把東西一件件放置在冰箱裡。這個冰箱每次僅容放置或取出一件物品,每次放置物品都要放置在最裡層,要取出最裡層的東西,必須先取出最外層的東西,那麼,冰箱的這種結構就構成了“棧”。棧是先存後取型的結構

佇列

佇列應該是中國人最熟悉的結構了。你可以不懂陣列、連結串列、棧,但你一定知道佇列,—— “萬惡”的排隊。若干個人站成一隊等待著, 先到者先得之。

佇列是先進先出型的結構

聯合

聯合,其實就是“大雜燴”的意思。為了方便計算,陣列、連結串列、棧、佇列通常都是存放相同型別的值,俗稱“清一色”。聯合則比較多樣化,什麼都可以往裡塞。比如說小書架,既可以放幾本書,也可以放小飾品,遙控器等。 聯合是物件的雛形。

元組

元組,也是一種“大雜燴”。不同之處在於,元組儲存的資料通過彼此的邏輯關聯共同表達一種概念。比如三維空間裡點的直角座標 (x,y,z) ,一件事情的起始結束時間 (start_time, end_time)。元組的值初始化後就不能改變。

點陣圖

點陣圖,就是一串01。前面講到原子型別的值時已經提到。現在你明白了,在計算世界裡,真正的原子只有0與1,其他的都是位串,都是結構。陣列、連結串列等是位串的結構。點陣圖操作就是置位(指定位置為1)、清零(指定位置零)與測試位(判斷指定位是0還是1)。點陣圖用於任何事物的編碼結果,亦可以用於任意稠密的不重複整數陣列的排序。

列表

列表與陣列極為相似,不同之處在於,陣列是固定長度的,而列表是長度可變的。實際上,Java 的列表是以陣列為基礎來實現的(當然並不是所有列表都是以陣列來實現的,譬如Scala, Lisp的列表是以連結串列來實現的)。初始化列表時,會為列表分配一個指定長度的陣列,當原來的容量不夠存放時,就會申請更大的陣列,並將原來陣列的元素拷貝到新的陣列。如此而已。

集合

集合,是若干個不重複值的可變長結構。集合與列表非常相似,不同之處在於,集合裡不存在重複的值,而列表中可能存在重複的值;集合是無序的,而列表是有序的。集合,比方天氣的幾種型別,有 Set(晴,雨,雪,陰,霧,霾) , 那麼一週的天氣就能構成列表: [晴,晴,霾,雨,雪,陰,霧]

對映

對映,就是鍵與值的一對一或多對一的關係。比如一個人的身高體重, map = { ‘height’: 168, ‘weight’: ‘100’ }。這裡 height, weight 是鍵, 而 168, 100 分別是鍵 height, weight 對應的值。可以根據鍵快速獲取和設定對應的值,是對映的主要操作。對映在計算機中使用雜湊表來實現,可實現快速查詢、中斷處理等。

變體

變體是在現有結構基礎上作出某種改動從而能夠適應特殊需要的結構。比如優先順序佇列,就是在普通佇列的基礎上新增了優先順序的概念,允許高優先順序的元素“插隊”。佇列還有三種變體: 雙端佇列、迴圈佇列、多重佇列。 雙端佇列,允許在一端進行插入和刪除,一端只允許插入,從而具有棧和佇列的用途;迴圈佇列將佇列首尾相連,可高效使用儲存空間;多重佇列可建立多個同時進行的佇列,通常用於多工所需要的程序掛起/就緒等待佇列。棧也有“雙棧”的變體,允許從兩端進行插入和刪除,適合於需要兩個棧的場景。

變體是基本結構的微創新

巢狀

基本資料結構的真正威力在於可以任意的巢狀。巢狀 是指結構中可以包含任意的子結構,子結構又可以包含子結構,一直這樣包含下去(能夠無窮無盡地包含下去麼?)。比如一個公司的職工的資訊, persons = [ { ‘name’: ‘qin’, ‘address’: { ‘prov’: ‘zhejiang’, ‘city’: ‘hangzhou’ } , ‘hobby’ : [‘writing’, ‘walking’, ‘riding’],’features’: ‘01001001’ } , { ‘name’: ‘ni’, … } ]

圖示

小結

現在我們已經瞭解了陣列、連結串列、棧、佇列、聯合、元組、點陣圖、列表、集合、對映這些基本資料結構,也知道可以通過巢狀的方法創造任意複雜的新結構。使用基本資料結構,就能批量存放更多的資料,批量操作更多的資料,組建正規化軍隊,形成更強的戰鬥力。這些基本資料結構是構建中大型程式的結構基礎。其中,列表和對映是最最常用的兩種結構。在Java裡稱為容器,容納東東的器物,是不是很形象?

基本控制結構

存放更多的資料有了基本資料結構及其巢狀結構,那麼,如何組織超級多的指令呢? 根據現實中的邏輯需求以及數學家、科學家的不懈思考,結合工程師的實踐經驗,就形成了“順序、分支、迴圈”三種最基本的控制結構; 並且可以證明,任意程式碼結構都可以使用這三種控制結構來表示。嗯,數學家就是這個用處:將萬事萬物統一為簡潔而基本的模型。

程式碼塊

單木不成林,單掌不成鳴。單條指令沒法做什麼事情,只有組合多條指令才能完成具體的功能。就比如乘法運算,也需要拷貝運算元、對運算元移位和相加、拷貝新得到結果。程式碼塊就是將多條指令順序組織起來進行執行從而實現具體的功能。程式碼塊一般用大括號括起來, 指令之間用分號隔開。

/* 早上的例程 */
{
聽到鬧鐘響關掉鬧鐘; 繼續躺床上20-30分鐘; 
看到快8點時起床; 洗漱; 收拾全身; 出門;
}

分支

分支就是當條件A發生時做某事,當條件B發生時做某事。比如週末如果天晴就出去逛,下雨就宅家裡,或者如果心情好的話,去看場電影,或者去找個人一起玩。就是這樣了。

/* How to waste a weekend */
if (天晴) { 出去逛; } 
else { 
if (心情好) {
看電影 or 找人玩;
}
else { 宅家裡; }  
}

選擇

選擇是在多個相同型別的選項中選擇匹配的一項並執行相應的操作。

# /* Talk with an intelligent workmate */
switch fruit:
case 'apple': suggest 'a apple a day keeps the doctor away' 
case 'banana': suggest 'a banana a day keeps your skin delicious'
case 'tomato': suggest 'oh, my favorite '
default: suggest 'i dont recognize it ' 

迴圈

迴圈就是把一件事重複做多次。過程必有終結之時。此之結束,彼之開端。

/* The life */
while (人生還在繼續 && 沒有意外發生 ) {
晨起洗漱;  
一日三餐維持生命;
程式設計; 寫作;
感受美好;
睡覺;
}

跳轉

當一條路走不下去,或者發現要及時掉頭時,就會使用跳轉語句。break 是終止整個迴圈;continue 是跳過後面的操作進入下次迴圈。GOTO是萬能跳轉語句,曾經盛行一時,但當今高階語言只作為保留關鍵字,不再推薦使用它了。從底層看來,分支、選擇、迴圈、跳轉應該是採用GOTO來實現的。

/* The life */
for (;;) {
工作;娛樂;養家;生活;
if (badHealth || bedying) {
print 'go to hospital.' 
break;
}
if (tired) {
print 'go to rest for some days'
rest(somedays)
continue;
}
}

函式

函式,就是把一系列指令組織起來實現一個具體通用的功能,並對其命名的過程。 比如前面早上的例程就可以寫成函式。

def doInMorning(delay=20,time=7:45):
聽到鬧鐘響關掉鬧鐘; 繼續躺床上 delay 指定的分鐘; 
看到快到 time 指定的時間就起床; 洗漱; 收拾全身; 出門;

相比程式碼塊,函式可以帶有引數,比如上面的 delay, time , 根據引數來調節實際的動作。就像電飯煲可以調節溫度、時間、鬧鐘可以設定鈴聲一樣。引數可能帶有預設值。以後就可以根據不同的引數執行 doInMorning 行為了。

此外,函式比程式碼塊多了命名。別看只是多了命名,其意義猶如編碼一樣非凡! 從此,程式設計邁入了“堆積木”時代。只要你花時間編寫了一個可靠的函式,成千上萬的人就可以在數秒內數千萬次甚至上億次地反覆使用這個函式,—— 你能找到第二個行業做到這一點嗎? 這就是軟體行業能夠一日千里、日新月異、天天刷屏的根本原因。

九層之臺,起於累土。正如我們可以從四則運算開始,經過代數、方程式、函式、數列、複數、平面幾何、解析幾何, 直到微積分、卷積、級數等非常高階的數學運算,也可以從實現1 1=2的簡單函式開始,一層層地累加,直到構建起超大規模網際網路軟體系統。

如果你要程式設計師造一座巴比倫城市,那麼,程式設計師會寫一個函式去創造一個城市,然後傳入引數名為巴比倫。

小結

到現在為止,真值得為自己慶祝一下: 我們已經走過一段路了。 熟悉了基本資料結構和基本控制結構,已經可以編寫小型程式了。不過, 如果要以登山作比方的話,那麼,我們現在正處於山腳下,望著巍峨高山,是否有一種登高望遠的衝動呢?O(∩_∩)O

請多休息一會,補充充沛的體力和精力。接下來, 我們將開始真正的登山之旅。

第二站-中級結構

中級結構通常是一種或多種基本結構通過某種組合形式而實現的更復雜一點的結構,亦稱為“複合結構”。組合蘊藏的威力是非常強大的。現實中的事物幾乎都是由基本元素和基本事物組合而形成的。巢狀是組合的一種形式。

中級資料結構

多維陣列

多維陣列是一維陣列在多維空間的擴充套件,是陣列(…的陣列)。比較常用的是二維陣列。比如 [[1,2,3], [4,5,6], [7,8,9]] 是二維陣列; [ [ [1,2,3], [4,5,6], [7,8,9]], [ [11,22,33], [44,55,66], [77,88,99] ] ] 是三維陣列。 訪問 N 維陣列的元素需要 N個對應的下標,可以根據指定位置隨機存取。 比如訪問二維陣列需要 [row][col] 下標, 訪問三維陣列需要 [N][row][col]。 二維陣列可用於點陣圖表示、曲線模擬、矩陣表示;三維陣列可用於立體圖形的模擬。

二叉樹

從一個起點出發,每次選擇向左或向右進行探索;如果不想在一個方向走下去了,那麼回退到上一個地方向另一個方向進行探索,如此反覆,最終形成的結構就是二叉樹。二叉樹實際上可以看成是多個連結串列的組合。字典查詢就使用到了二叉樹。處理二叉樹通常會用到遞迴的方法。

二叉樹是程式設計中第一個不太容易掌握的資料結構,其原因是,人們更習慣於以線性的方式思考問題,然後二叉樹告訴我們:要分叉,要多向探索,世界有更多可能。

模板

模板是含有固定不變內容和待填充內容(稱為佔位符)的混合體。當實際執行時,將具體的內容替換佔位符,即可得到動態內容。常用於生成動態頁面,自動生成程式碼等。

比如 I have a dream that dream.就是個模板,{dream}. 就是個模板, {dream} 是佔位符。當使用具體內容“someday i will teach kids programming”替換時,就生成了最終內容: I have a dream that someday i will teach kids programming.

快取

我們來做個遊戲:有一個教官和一隊順序編號的十名學員。教官與學員相距 10 米。現在,教官要點到名的學員來到跟前敬禮然後回去。教官的記性和視力不太好,容易點到重複的名字,且如果有不超過5名學員都站在離教官5米遠的距離,教官是分辨不出來的。學員怎麼走才能更少距離到達教官呢?

當然,所有學員可以來到教官面前,然後敬禮歸隊,這樣每位點到名的學員都得往返 20米。但有些淘氣的學員故意離得近一點,站在離教官5米的距離,這樣教官點到名的時候,就只要往返 10 米。當然,如果點到名的學員站在10米遠的地方,就不得不往返20米了。現在的問題是,學員得找到教官點名的規律,並及時讓相應的學員站到5米遠的地方,從而使得全部點名後,所有學員的往返距離最小?

這5個離教官5米遠的位置,就是快取。快取是計算世界中僅次於編碼的極為重要的程式設計思想之一。計算世界的快取幾乎無處不在:CPU與記憶體之間有快取,磁碟、網路與作業系統之間有快取,應用程式與資料庫之間訪問有快取。你與我之間也有快取。快取能夠讓獲取資料更快,從而運算更快,效率更高,但快取也更貴。快取的兩大指標是:快取容量和命中率。如果相同成本下的快取容量更大,就能使用快取來替代原來的儲存,然後製造更近的快取;如果快取容量難以提高,就要琢磨資料存取的規律,儘可能讓每次的命中率更大。快取容量就是有多少個離教官5米遠的位置;命中率就是有總共的點名次數中多大的比率教官點到了離教官5米遠位置的學員。

中級控制結構

迭代

迭代是使用固定的計算規則集合不斷用新值取代舊值趨向真實值的控制結構。比如牛頓迭代法求N的平方根 X(k 1) = (X(k) N/X(k))/2 (k>=0) 就是一個迭代過程。可以指定初始值和終結迭代過程的迭代次數。迭代的重要指標是收斂性和收斂速度。

遍歷

遍歷是從結構中的某個初始節點出發,使用某種控制演算法直至訪問結構中的所有節點。遍歷有深度遍歷和廣度遍歷。深度遍歷是一直往一個方向走,直到無路可走,然後回退到上一個可選擇路徑的節點,選擇另一個沒有遍歷的路徑。依次直至所有節點都訪問完畢。深度遍歷上述的數結構,得到的節點順序依次是 { 9,6,3,8,7,12,15,18,13} ; 廣度遍歷是首先訪問初始節點的所有鄰接節點,然後訪問這些鄰接節點的鄰接節點,這樣一層層地輻射般的鋪開,得到的節點順序依次是 { 9,6,12,3,8,15,7,13,18 } 。

常見的遍歷操作有列表遍歷、物件遍歷和合並操作。列表遍歷主要有對映、過濾和查詢(匹配)。 對映即是對列表的所有元素依次應用一個函式得到另一個列表,比如 [1,2,3,4,5] 應用 f(x) = x*2 得到 [2,4,6,8,10]; 過濾即是對列表的所有元素依次應用一個函式得到另一個列表,這個函式根據某種條件返回 true or false , 比如 [1,2,3,4,5] 應用 f(x) = { return x > 2; } 返回 [3,4,5]; 查詢操作是在列表中找到指定元素的第一次出現位置或所有出現位置;實際中的列表遍歷往往兩者兼之,在遍歷列表的時候判斷是否滿足某種條件,如果滿足,對列表元素做一定處理,然後新增到結果列表中。Traverse(list) = list.filter(condition).map(listElemHandler)

物件遍歷是遍歷物件的所有狀態以及遞迴遍歷物件引用的物件,由此形成了物件遍歷圖。

合併是通過遍歷將兩個資料結構的對應元素通過某種方式合併成一個列表的過程。比如摺疊操作 zip([1,2,3,4], [6,7,8,9]) = [(1, 6), (2, 7), (3, 8), (4, 9)]; 比如 Map 合併 merge ({‘name’:’qin’, ‘address’: ‘hubei’}, { ‘hobby’: [‘writing’, ‘programming, ‘walking’] } ) = {‘name’:’qin’, ‘address’: ‘hubei’, ‘hobby’: [‘writing’, ‘programming, ‘walking’]}.

對於巢狀的資料結構的遍歷,需要使用遞迴的方法來完成。

遞迴

資料有巢狀的結構,控制也有巢狀的結構。遞迴就是在函式F以不同的引數呼叫它自身。比如計算 1 2 3 , 既可以順序迴圈地計算,也可以遞迴地計算: 1 (2 (3)) , 1-3 的和,就是 1 與 (2-3) 的和,而 2-3 的和,是 2 與 (3) 的和,(3)的和就是它本身。這裡有三個要素: 1. 一個可以以不同引數重複呼叫自身的過程,這些不同引數通常是要處理的總結構以某種方式依次去掉一些元素的子結構; 2. 一個原子的操作,比如這裡兩個數的和; 3. 終止條件: 在某一次呼叫時傳入引數的子結構只有一個值的情況。

遞迴是計算世界中與快取思想同等重要的程式設計思想。

中斷

當你正投入工作狀態的時候,領導發話了:開會開會! 於是你不得不放下手頭心愛的事情,跑去聽一段@#¥@#%@¥%@%#¥%#的講話,講話回來後再以莫名的心緒重新干活。當然,人是有記憶的,當你去開會前,實際上已經記憶了當時做的事情的一些重要細節和程序,這樣在回來時就能從這些細節和程序逐漸恢復到當時狀態繼續幹活,就像講話似乎發生過一樣。這就是中斷:做某件事,更高優先順序事情插入,儲存現場,完成更高優先順序的事情,恢復現場,繼續做原來的事情

中斷是計算世界中與遞迴思想同等重要的程式設計思想。

回撥

回撥是常規邏輯的一種變體。通常程式碼會順序地執行A -> B -> C ->D 等,但在某些情況下,我們希望在 B 處做不同的處理,比如 A 生成一個列表 [1,2,3] , 而在 B 處既可能去對列表元素做乘法運算,也可能做加法運算。這時候,可以在B 處提供一個回撥 callback(list),允許傳入不同的函式 add(list) 或 multi(list) 對列表做不同的處理。再比如前端傳送一個ajax非同步請求,當成功的時候顯示錶格資料,當失敗的時候列印友好的錯誤資訊,就需要提供兩個回撥: success(response) 和 fail(response) ,分別處理成功和錯誤時的情況。回撥通常用於模板設計模式中。

回滾

當我們在編輯器裡編輯錯誤時,就會使用 Ctrl z 快捷鍵回退到上一個編輯狀態,即“撤銷”操作。回退到某個指定狀態的操作叫做回滾。比如釋出程式碼到線上後,發現有重要BUG,就需要回滾釋出程式碼到上一個可靠的狀態。在軟體中,回滾有兩個應用領域:一個是事務管理,一個是GUI程式設計。事務管理中,比如處理入賬匯款的功能,當你向家人匯款一筆錢時,通常需要在你的賬戶里扣減這筆錢且同時在家人的賬戶裡增加一筆錢,兩者必須同時成功才構成一次正確的匯款操作。如果在你賬戶里扣減款項之後,裝置出故障了,那麼就必須回滾到未扣減的初始狀態,以確保你的財產不受損失。在GUI程式設計中,常常存放使用者的編輯操作序列,以便於在使用者操作出錯時可以撤銷,從某個狀態重新開始編輯。

流計算

假設有個列表 [1,2,3,4,5] , 你想先對列表中所有元素依次乘以10,再依次加上4,再依次除以2,最後依次過濾掉結果少於20的元素。那麼有兩種方式。一種方式是按照指定計算順序地進行,每次都遍歷列表對所有元素計算,先得到 [10,20,30,40,50],然後得到[14,24,34,44,54], 然後得到 [7,12,17,22,27],最後過濾後的元素是 [22,27] ; 很簡單,不過要對列表遍歷4次。如果指定運算更多一些,就要遍歷更多次。另外一種計算方式是,先收集相關資訊,比如所有的計算要求及順序,然後進行聚合,對於上述計算而言,實際上就是把列表中的每個元素乘以5再加上2,然後保留大於或等於20的元素。即將 5x 2 >=20 應用於列表中的每個元素得到新的列表 。這樣就只需要對列表進行一次遍歷。這就是流計算。流計算不同於普通計算之處,在於它把待處理資料看成流,將要做的運算聚合成一次運算,然後在真正需要結果的時候才進行計算。

一次流計算的基本組成元素有列表遍歷和列表聚合操作。列表遍歷見遍歷部分,列表聚合主要指求和、求平均、最大最小值等。流計算可以是序列的,也可以是並行的。詳見 Java8 Stream API.

閉包

閉包是一個從學院流傳到工程界的思想,歷來眾說紛紜,莫衷一是。既然如此,不妨從其溯源、本質和形式來理解。

為什麼有閉包呢?這是變數為了突破函式的限制而產生的。假設函式F裡定義了一個區域性變數 x,那麼當函式執行完成退出後,x 就會自動被銷燬。這就像寄生於宿主中的寄生者一樣,宿主滅亡就會導致寄生者滅亡;又像古代陪葬,做奴的要隨主子的入葬而陪葬。閉包,就是為了建立能夠突破這一限制的變數。當在函式F中定義了閉包 C 來訪問變數 x, 那麼在函式F退出後 x 並不會被銷燬,而是以當前狀態存留並長眠,等待函式F的下一次執行的時候復甦過來。嗯,是不是像在看科幻小說?這就是閉包的溯源。

閉包就是為了建立函式中的自由變數。在不同程式語言中的實現形式有所不同。C語言中,在函式中的變數使用 static 修飾,就可以成為不隨函式退出而滅亡的自由之身,不過這並不算是閉包;Python 語言中,閉包使用在函式內被定義的巢狀函式來實現;Groovy 語言中,是一段自由出現的用括號括起來的程式碼塊,可以賦值給變數和傳遞給函式;Java語言中,是含有引數和函式體但沒有函式宣告的程式碼塊。

Curry

在學習數學時,常常會遇到這樣的函式,f(n, x) = 1^x 2^x … n^x , 其中 n^x 是 n 的x 次方。當 x 取不同值時, f(n,x) 就退變為一元函式,比如 x=1 時, f(n,1) = 1 2 … n, 是求n個數的和;x=2 時,f(n,2) = 1^2 2^2 … n^2 是求n個數的平方和等。將 f(n,x) Curry 化,就得到了 f(n)(x) = 1^x 2^x … n^x; 那麼 f(n)(1) 就是 n 個數的和, f(n)(2) 就是 n個數的平方和,依然是函式。這對計算世界裡的傳統函式是一個創新:傳統函式得到的結果總是具體的值。運用 Curry 化,程式語言就有表達數學公式的抽象能力而不僅僅只是計算值了。功力又見長了!

Curry 將多元函式逐層拆解,可以批量生產出大量的低元函式,簡直就是個“函式工廠”!運用Curry很容易做出可擴充套件的微框架,組合基礎函式來完成大量資料處理的功能。Scala 語言提供了 Curry 的支援。

小結

在這一站裡,我們學到了新的資料結構(二叉樹、模板、快取)以及新的控制結構(迭代、遍歷、遞迴、中斷、回撥、回滾、流計算、閉包、Curry)。熟悉這些結構會略有點難度,因為其特徵與人類的順序、線性的日常思維不太適配。

迭代在科學計算與軟體工程中廣泛使用,體現了“逐步求精”的思想;遍歷是開發中最常用的控制結構,很多程式碼都需要對一個列表或對映進行遍歷和操作;遞迴需要思維隨著結構逐層遞進深入,甚至超越思維能夠承受的範圍(當結構可能巢狀任意有限的任意結構時);中斷相對容易接受,與日常場景比較相似;回撥則類似在程式碼路徑中做了個多路分叉,在不同情況下可以選擇不同的演算法來處理;回滾則可回退到歷史存在的某個狀態重新操作,提供了出錯處理的機制;流計算體現了對源資料流的聚合與延遲的計算特性;閉包建立了函式裡的自由變數,從而擴充套件了函式的能力;Curry 將多元函式拆解為多個低元函式的層層呼叫,批量生產大量函式,能夠以最大靈活性組合程式碼邏輯,有時甚至以簡短的幾行程式碼就能做出一個簡易微框架。

學習這些結構,需要思維能夠更加靈活,突破順序、線性思維的侷限性,甚至需要深入思考和練習;學會這些結構,基本可以應對軟體開發中的普通難度的業務程式設計了。

現在我們已經站在山腰了,可以看到一點點壯觀的風景了!那麼,繼續向上,還是返航? 由你決定。

第三站-高階結構

高階資料結構

圖是多個事物相互關聯形成的複合結構。國家鐵路交通網,公司所有成員的社交關係網,都是圖的例子。圖是資料結構中最難掌握的BOSS級結構。圖程式設計的難點在於事物之間的多向關聯,讓線性思維的人們無所適從。事物的關聯蘊藏著驚人的價值。Google是利用網頁之間的關聯權重發跡的,Facebook則更直接利用人們的社交關係來成就的。大部分程式yuan寫不出像樣的處理圖的基本程式,工作一年後絕大部分程式yuan幾乎不會表示圖了。圖是資料結構領域的金字塔頂。可以說,掌握了圖結構程式設計,就意味著資料結構最終通關成功,程式設計領域裡幾乎沒有可以難倒你的資料結構了。

圖可以使用二維陣列來表示, 也可以使用陣列和鄰接連結串列組合起來表示。這充分說明:最基本資料結構的組合,就可以建立最複雜的BOSS級資料結構

正規表示式

正規表示式是一種非典型資料結構,用於描述資料文字的特徵。比如 0571-8888888, 027-6666666 都是電話號碼,是由連字元 – 分隔的兩數字串,可以使用正規表示式來描述這樣的文字: [0-9]{3,4}-[0-9]{7}。[0-9]表示匹配0-9的任意某個數字,{m,n}表示位數為[m,n]之間,{m}表示位數就是m。[0-9]通常也簡寫為\d. 正規表示式廣泛用於文字匹配和替換工作。

物件

到現在為止,資料與控制都是分開發展的。分久必合。在物件這裡,資料與控制合為一體。物件是具有狀態和行為的統一體。正如人具有身體結構、精力、體力等狀態,並能夠運用這些結構和狀態來完成實際行動一樣。資料通過複雜結構構成實體,實體具備影響資料變化的能力;資料與控制成為相互影響密不可分的整體。物件是程式yuan對現實世界的事物的抽象。

高階控制結構

設計模式

設計模式是物件程式設計的技藝。要完成一件事情,通常要很多人一起來配合協作,充分發揮每個人的專長。那麼職責任務分配就非常重要了。設計模式即解決物件的職責以及物件之間怎麼協作的問題。比如程式yuanA程式碼寫得特別溜,就是不喜歡跟人交流,那麼就需要一個和TA合得來的yuanB來傳達yuanA思想。這個合得來的yuanB就是yuanA對於外界的介面卡。介面卡模式並不完成新的事情,只是將一件事轉換一種形式來完成。設計模式能夠讓軟體的柔性更強。

Class A {
public void writeNBCode(HardTalking hardTalking) {
// HardTalking 是非常難以使用的引數 
//  balabalabalabala
}  
}
Class B {
public void goodSpeaking(GoodTalking goodTalking) {
//  GoodTalking 是非常容易使用的引數
hardTalking = transfer(goodTalking)
A.writeNBCode(hardTalking);
}
}
B.goodSpeaking(talking);   // 人要使用到A的牛逼能力,只需要與 B 溝通就行; 這裡 goodSpeaking 就是個介面卡介面。

親愛的猿媛們,你希望別人因為自己不善言談而把自己晾在一邊,讓別人來取代你的發言權麼?

非同步

在順序的模型下,當你執行計算時,需要等待計算完成後獲得結果。如果執行計算的時間會比較長,那麼顯然不能幹等著吧。這時候,就需要採用非同步模型。非同步與在餐館點菜很相似。當你付款後,由於菜餚要準備一段時間不能立即獲得,這時候,你會得到一個類似令牌的東西,代表你的一次請求和要獲取的菜餚。在菜餚準備期間,你可以去做任何事情,除了不能掛掉。當菜餚準備好後,就會通知你使用令牌來獲取相應的菜餚。這也有兩種方式,要麼服務員直接把飯菜端上你的桌(推),要麼你拿著令牌去取(拉)。非同步廣泛用於請求不能立即完成和獲得結果的場合。

token = 點菜(選單列表);
// 立即返回,不阻塞在服務檯那裡,體現非同步流程
做其他的事情,比如看看手機聊聊天;
吃飯流程: 
while (飯菜沒吃完) {
token.getResult(菜已上桌) {
吃飯,聊天,...  ;
}
token.getResult(菜無法供應) {
if (飯菜不夠吃) {
token = 重新點菜(選單列表);
goto 吃飯;
}
else {
放棄點的這盤菜;
}
}
}
token.pay()

併發

一邊燒開水,一邊看報紙。這大概是併發的最經典比方了。不過對於現代人來說,看報紙大概要換成“追劇”了。不錯,併發就是同時做兩件事了。這個“同時”可以有兩種理解:(1) 兩個人在同一個時刻各做了兩件事; (2) 一個人在一段時間內同時做了兩件事。(1)是嚴格的併發,也稱為“並行”。一邊燒開水,一邊看報紙,實際上是壺在燒水,人在看報紙。可以說壺與人是並行工作的;(2) 稱為“分時切換”,是廣義的併發,比如單CPU在IO操作時執行其他的計算,此時稱CPU也是併發的,實際上是因為CPU與IO裝置同時在工作,但是以CPU為中心而言的緣故。 併發操作的原因,是因為一個事物由多個部分組成,而每個部分都能獨立地做一件事。比如千手觀音,假如人真的有千手,那麼真的可以同時吃飯、看報紙、寫字等(量子化的世界,是否可能實現一個事物在一個時刻點同時做多件事?)。

別看併發理解起來比較容易,在軟體開發中,併發是最本質的難題。併發會導致多個事情的執行順序和結果的不確定,導致資料訪問死鎖,加上大規模資料流,大規模的邏輯併發,基本超過了人類理解力能夠承受的極限。併發是導致極難排查的BUG的根本原因(很難復現,但它又會不請自來,像軟體中的幽靈)。現有的大多數應用,還僅僅只是使用多臺伺服器並行提供服務,使用多執行緒或多程序來執行相互獨立的子任務,併發在應用中只是區域性使用,也就是順序為主、併發為輔的。

併發的實現方式主要有: 多執行緒(Java)、多程序(C)、多協程(GO)、Actor(Scala).

通訊協議

到目前為止,我們討論的範圍還僅限於單機範圍。可是絕大多數人是無法忍受孤獨的,人亦非孤島般存在。讓計算機能夠彼此通訊,讓人們能夠跨時空互聯深入交流,才是網際網路的最大夢想。通訊協議就是解決計算機中間如何可靠通訊的問題,而為了可靠通訊,就必須制定好協議。比如一次5個人的聚會吧,首先大家肯定要事先約定什麼時候什麼地點碰頭,好各自安排行程;這是靜態協議; 不過計劃總趕不上變化。當實際去赴會時,會發現因為某位明星的到來導致路上特堵,結果2個人不能如約到達;這時候,就必須重新調整計劃另約時間和地點,甚至還可能改變原來的遊玩計劃;或者在原計劃中留下充分的緩衝餘地。這就是協議要做的事情:約定與標準(碰頭時間地點)、緩衝餘地(容錯)、動態調整(靈活性)。實際的通訊協議可能更復雜,依據不同的應用而設定,不過原理是相同的。

通訊協議是網際網路誕生和發展的基礎軟體設施。最為人所熟知的莫過於 HTTP, TCP 和 IP 協議了。

小結

很有勇氣!你已經抵達山上大約 2/3 的地方,可以看到更加壯美的風景!高階資料結構和高階控制結構,理解起來比較容易,大規模實踐起來,卻是件很有難度的事情,需要紮實的功底、多年的經驗、出色的悟性和直覺, 就像習武一樣,起初的進步是飛快的,隨著功力的提升,以及事情固有的難度(或許是因為我們還沒有真正理解事情,沒有找到有效的方法),會遇到一個瓶頸。在這一層中,大量的努力和實踐可能只帶來少量的收穫,但仍然要不懈攀登。當能夠掌握這些高階結構時,就程式設計功底而言,已經沒有什麼程式設計難題是無法跨越的了。

接下來的事情,就是最後的衝刺,真正的實戰與挑戰。

第四站-應用

應用中的資料結構和控制結構在程式設計領域不一定是最困難的,但由於要承載現實世界中的大規模流量,以及多人協作維護的大型工程,因此更多的是工程領域的難點和挑戰。大流量、併發使用者訪問、不可避免的髒資料和無規則資料、非法訪問程式碼等,都是應用資料結構和控制結構需要應對的問題。

應用資料結構

JSON

JSON是基本資料結構的巢狀而成的結構, 是廣泛應用於子系統之間的標準資料交換結構。比如服務端返回給前端的資料結構就是 JSON,服務A 呼叫服務 B 的 API 介面獲取的返回資料結構也是 JSON。 JSON 定義可參考網站:JSON.org



XML

XML是一種標記語言,通過 <標記含義>標記內容

<person>
<name>qin</name>
<hobby>
<list>
<value>programming</value><value>riding</value>   
</list>  
</hobby>
</preson>

記錄文字

記錄文字是每行以固定規律呈現的結構化文字。比如csv檔案是每行以逗號分隔的文字,properties配置每行是以key=value形式的文字。記錄文字格式簡單,容易解析,常用於Shell任務處理和應用配置檔案。

關係型資料庫

關係型資料庫是幾乎所有網際網路應用必不可少的資料結構元件。

關係型資料庫的基礎是二維表,就是一行一行的記錄,每行記錄都是由多條資料項組成的。為了支援大容量記錄以及方便地按照各種條件進行檢索,二維表採用了B 樹實現,並實現了一套資料庫管理系統,包括資料庫伺服器、資料庫語言SQL、以及資料庫客戶端。資料庫伺服器用於確保所有記錄能夠按照條件進行訪問(查詢、插入、更新、刪除,俗稱 CRUD),包括伺服器的正常運轉;資料庫語言SQL提供了要查詢什麼資料的表達方式;客戶端提供了編寫、執行SQL和檢視結果的操作介面。

關聯式資料庫適合儲存和檢索結構化的有規則的資料集,一個業務功能的詳細設計通常都會從資料庫設計著手。比如學生選課,可以設計四張表:學生表,每一行都是格式相同的記錄,資料項為(學號,姓名,學生的其他資訊欄位等); 課程表,每一行都是格式相同的記錄,資料項為(課程編號,課程名稱,課程的其他資訊欄位等);教師表,每一行都是格式相同的記錄,(教師編號,教師姓名,教師的其他資訊欄位等); 選課表,每一行都是格式相同的記錄,資料項為(學號,課程編號,教師編號),這裡學號會關聯學生表的學號來獲取對應學生的資訊,課程號會關聯課程表的課程編號欄位來獲取對應課程的資訊,教師編號會關聯教師表的教師編號來獲取對應教師的資訊,這種關聯稱為Join操作,在數學上稱作“笛卡爾乘積”。資料庫表的設計是有一套正規化可遵循的,儘可能保證資料的一致性、完整性和最小冗餘度。

key-value型資料庫

關聯式資料庫適合儲存和檢索結構化的有規則的資料集,但對於移動網際網路時代的應用所要承載的大規模資料流量來說,就很有點吃力了。隨著表記錄的大幅增多,資料庫的查詢響應時間會逐漸降低,資料庫也面臨著巨大的併發訪問壓力,因此出現了 key-value型資料庫,可以作為資料庫的輔助。 key-value 資料庫適合儲存非規則型的容量級別更大的資料,可以有效地作為應用與資料庫訪問之間的快取,從而大幅減少直接訪問資料庫產生的壓力。

應用控制結構

API

API的實質就是函式。API是被封裝可複用的函式在軟體工程語境中的正式稱謂,常用於表示一個子系統、子模組對外所能提供的服務,以及子系統、子模組之間的互動關係。封裝和複用,是軟體工程領域中最重要的思想。

API可以是作業系統提供的,比如檔案讀寫介面;可以是某種程式語言庫提供的,比如JDK; 可以是第三方平臺提供的,比如用於獲取商家使用者及交易資料的淘寶API,用於獲取位置資訊的谷歌地圖API等。

應用框架

當我們登入訪問網際網路網站時,需要填入使用者名稱或掃碼,提交請求後,請求就會傳送到伺服器後臺,後臺會對請求進行格式化、合法性校驗、許可權校驗、日誌記錄等,然後交給特定的服務程式處理,處理後的結果再經過格式化後返回頁面展示給使用者。這個過程中,“瀏覽器傳送請求給服務後臺,服務後臺做請求格式化、合法性校驗、許可權校驗、日誌記錄、提交特定程式處理、結果格式化等”其實都是通用的控制流程,跟網站業務只有一毛錢關係,於是,程式yuan就將這些通用流程抽離出來,形成應用框架。這樣,以後無論是搭小學生網站,還是搭大學生網站,都可以使用這個應用框架快速搭建起應用。除了網站應用框架,還有很多其他用途的成熟的應用框架。一位熟練的工程師完全可能在一週內獨立搭建起一個可演示的系統。

應用框架使得搭建應用可以從 40% 起步,甚至從 70% 起步。一個正式運營的網際網路應用軟體,使用的應用框架、複用的程式庫程式碼,佔比可能達到90%,真正由應用程式yuan寫的程式碼,可能只有10%左右。也就是1000行程式碼中,大約100行是應用相關程式碼。

元件

元件是用於特定用途的可複用的符合該元件型別約定標準的成品,可以在不同的應用系統中靈活地組裝使用。類似於標準化的汽車零部件。比如訊息中介軟體,可以可靠地在極短時間內接收和推送數億條訊息; 日誌元件可以根據應用指定的配置列印格式多樣化的不同級別的資訊到指定的輸出流中;工作流元件可以將業務流程(比如審批)抽象成一個個順序或分支節點來執行和完成。應用框架也是一種元件。元件使得初始應用系統可以從更大粒度進行組裝完成,在後續開發和維護中也可以靈活地進行去舊換新。

如果想了解更多元件型別,可參考網站: Java開源元件 。Java 語言中,元件採用 Jar 包的形式,使用開源元件 Maven 自動化管理。

控制元件

控制元件是指那些能夠容納資料和展示資料的客戶端介面。比如文字框、表格、圖片、圖表等。控制元件由資料模型、資料管理器和介面組成。資料模型是控制元件可以容納的資料結構的形式,比如字串、記錄列表、二維陣列等,介面就是用於展示資料模型容納的資料的視覺化的視覺子元件;而資料管理器則是可以用於搜尋、過濾、排序、下載等操作的子元件。資料模型是控制元件的資料部分,介面是控制元件的檢視部分,資料管理器是控制元件的控制部分,通常稱為“MVC”設計模式。

分散式

分散式是利用部署在不同伺服器上的大量子系統或子服務相互協作共同完成請求的。比如網站 W 給消費者提供行業諮詢服務,可能要使用到雲服務商 B 提供的大規模雲伺服器 E、負載均衡服務 L、關聯式資料庫服務 R、開放儲存服務 S、大資料離線計算服務 D,使用到 T 公司平臺提供的第三方API介面,使用到 C 公司的 CDN , 使用到 D 公司的域名解析服務, 使用到 E 網站提供的廣告推廣連結,而服務商 B 提供的伺服器叢集需要許多管理、監控、運維等內部系統 M 來維護,這些內部系統 M 可能使用 F 網站提供的連結和 G 網站提供的開源元件,使用到自身的雲服務叢集,而 F,G 網站也可能使用到 B 提供的雲服務叢集等。

再比如IAAS服務商 A ,為了提供可靠友好的雲伺服器服務介面 S ,需要前端控制檯應用 F 呼叫 OpenApi 介面應用 O, O 又呼叫後臺Dubbo服務應用 D, D 解析請求中的資訊轉發給對應地域的閘道器代理介面 P , P 將請求轉發給控制系統 C , C 進行計算排程後傳送虛擬機器相關指令(比如重啟)到指定的物理機 H 上執行相應的虛擬化、儲存、網路底層模組介面 M 。這些物理機 H 需要定時上報心跳給控制系統 C ,需要在底層模組處理成功或失敗的時候推送訊息給訊息中介軟體 N , N 需要推送訊息給控制系統 C 來更新其資料庫伺服器 R 上的虛擬機器狀態。 所有這些應用 F,O,D P, C, R 都是部署多臺伺服器來避免單點故障的, 而 H 則更是分佈在不同地域不同機房的數萬臺物理機中的某一臺。

簡單地理解,一個跨地域、通過多人並協作完成目標的組織機構,就是分散式的。分散式系統可以組合廉價伺服器來獲取高可靠高可用,可以通過多箇中小型應用併發、協作地完成高難度的計算目標(比如基因測序),其潛能非常巨大。不過分散式系統具有併發所帶來的難題,同時又增加了不同機器之間的時序同步、資料不一致性等疑難問題,具有相當高的複雜度。

網際網路

恭喜一直不懈前行的自己,即將登上山頂!

分散式的網際網路,或許是人類構建的最為恢弘壯麗而錯綜複雜的系統了,一個全新的虛擬世界,遠超過埃菲爾鐵塔和萬里長城,雖然後者也是令人震撼的傑作。數億的線上訪問使用者、部署在數千萬的伺服器上的不計其數的應用服務、相互依賴的子服務協作良好地穩定而不知疲倦地執行著,併發的不確定性、機器時序分散式同步等帶來的困擾,似乎並沒有影響網際網路正常秩序的運轉。如果說這是人類智慧的結晶,也間接證明了上帝奇蹟般的設計,—— 因為只要一個無規則的微小擾動,這些可能就根本不存在。

在山頂靜靜駐留一刻,或者在水的包圍中靜靜駐留一刻,將是生命中難得的記憶之一。

小結

在這一站中,我們領略了人們為了應對和攻克現實世界和實際工程中的難題所發明創造的具有實用性的可複用的資料結構和控制結構,感受到程式設計所創造的超級世界 —— 網際網路。或許,這就是《終結者》中天網的雛形,一個還不具備足夠智慧和思考能力的處於胚胎期的生命體。未來將會怎樣呢? 無法得知,唯有珍惜此刻。

軟體之道的思考

效能與效率

程式yuan永恆地追求著效能與效率。低效能幾乎總是由不必要的重複操作造成的。比如在多重迴圈中重複地取出相同的值,在迴圈中重複建立開銷很大的相同物件,在迴圈中一次次呼叫相同的網路服務介面(重複的網路傳輸開銷),重複呼叫相同的介面獲取相同的資料等。要達到高效能和高效率,就要聚焦熱點區域,設計優良的結構,精打細算,去除那些不必要的重複操作,儘可能減少不必要的網路操作。

健壯性

健壯性通常是對現實複雜性估計不足,沒有考慮到:
1. 各種可能的非法輸入:髒資料、不規則資料、格式合法但內容非法的資料、含惡意程式碼的資料等;
2. 執行環境的低概率的不穩定,比如偶爾的網路波動,讀取不到資源的URL等;
3. 難以覆蓋到所有場景的組合情況。

對於第一點,儘可能對輸入資料嚴苛地檢查並拒絕;對於第二點,及時捕獲異常列印日誌並返回友好的提示資訊;對於第三點,則要思慮周全,需要不斷積累功底和經驗才能做得更好(但永遠無法做到完美)。

可擴充套件性

可擴充套件性涉及到對控制結構的設計。簡單地使用順序、分支、迴圈語句來編寫程式碼實現需求總是可以的,畢竟這是數學家已經證明的事情; 不過,埋下的坑總有一天要讓人跌進去的,雖然不用上醫院,也要讓人灰了頭。

要達到良好的可擴充套件性,就要對控制結構進行仔細的設計。能夠通用化的控制流程要設法抽離出來進行復用;儘量做到“模型與業務”分離。建立穩定可擴充套件的模型(比如主從模型、訂閱-推送模型),將易變更的業務點抽離出來提供回撥,允許根據實際情況進行適當的變更調節。

儲存設計與請求構造

從多源頭解析和獲取資料、對資料進行變換處理、聚合資料【可選】、構造和傳送請求 或 儲存資料、從多源頭解析和獲得資料、對資料進行變換處理、聚合資料【可選】、構造和傳送請求 或 儲存資料、。。。, 大部分網際網路應用在不知疲倦無休無止地重複做著這些事情。資料的儲存設計,即存取和組織資料的結構設計,與請求流的構造, 是完成具體業務功能的兩大要素。

配置式的軟體通用框架

當仔細觀察和推敲軟體的構成和執行時會發現,軟體一直在做的事情就是:構造請求、傳送請求、獲取資料、聚合資料、儲存資料。或許我們可以做成一個可配置式的軟體通用框架:可配置的請求引數列表、可配置的服務名稱、可配置的資料獲取器、可配置的可靈活組合的資料聚合器、標準化的資料儲存設計,即服務模板的可配置化和服務呼叫的可配置化。這些都與具體的業務無關。就像規則引擎做的那樣,將業務邏輯以規則的形式進行動態配置,通過將物件匹配規則和觸發規則來完成實際功能。一旦服務可以實現可配置化,那麼,就像5分鐘搭建一個WordPress部落格一樣,或許我們也能在5分鐘內搭建起一個可以執行的實際系統,需要填充的只是具體的引數和流程配置。

程式設計之道

建立和使用結構來組織和容納資料,建立和使用相應的控制結構來遍歷結構處理資料,建立結構來聚合重組資料作為最終展示,這就是程式設計之道。程式設計是結構的藝術。

資料-結構-控制-流

從0和1出發到現在,似乎已經走過很長的一段路程。我們已經登上山頂。山頂上風光無限,山下的房屋像螞蟻一樣密密麻麻地排列著,河流蜿蜒地流淌在群山之間。現在,讓我們閉上眼,感受下軟體的生命靈動:大流量的資料在控制流的指引下,像水流一樣穿梭流動於形態各異的結構中,猶如車輛在道路的指引下川流不息。如果結構設計得不夠好,資料就會像水流撞在暗礁上那樣濺起水花,出現錯誤或不一致的資料;如果控制設計得不夠好,那麼資料就會在結構中堵塞滯留,導致系統出現各種問題甚至崩潰。資料-結構-控制-流,這就是執行中的軟體,亦即執行中的世界。

路線圖

結語

《旅行到宇宙邊緣》,是一部令我非常震撼而喜愛的紀錄片。在這部不亞於科幻大作的記錄片中,從我們的家園地球出發,遍訪太陽系九大行星以及太陽之神, 遍訪銀河系、河外星系、星系與星空、想象力延伸至宇宙之初。。。,在博大深邃而無邊無際的宇宙中,因為深明生命的脆弱和無情的星空,我的心顫慄著。當回到家園時,才明白地球是多麼美好而溫暖的港灣,藍天、白雲、大海、森林、岩石、土地、花木、生命,彷彿是經過數億年修煉而成的神佛般的存在。

我願這次程式設計之旅,也如探險般精彩。很幸運我們走過了這麼多路,即使彼此語言並不通暢,依然一步步構建起恢弘壯麗的網際網路天塔,通往與上帝對話的天堂。或許有一天發現再也無法回到出發點,那就繼續向前吧,旅程中永遠充滿著未知的新鮮感。未來猶如昨天,此刻亦即未來。

注: 本文所述的程式設計知識和思想並非原創,不過通過結構程式設計為中心來梳理和串聯程式設計基本知識和主要思想的寫作是原創的,轉載時請註明出處噢! 🙂