優秀程式設計師必備的四項能力
- 2020 年 2 月 13 日
- 筆記
前言
一個優秀的程式設計師具備挺多特質的，比如好奇心，學習能力等，但在我看來一個優秀的程式設計師必須具備四項核心能力，哪四項，先賣個關子，程式設計師最喜歡說的話是「Talk is Cheap, show me your code」,那我們先來看一道很常見的面試題
如何快速定位IP對應的省份地址？
我們知道，每個省市都分配了一個 ip 段，如下
[202.102.133.0, 202.102.133.255] 山東東營市 [202.102.135.0, 202.102.136.255] 山東煙台 [202.102.156.34, 202.102.157.255] 山東青島 [202.102.48.0, 202.102.48.255] 江蘇宿遷 [202.102.49.15, 202.102.51.251] 江蘇泰州 [202.102.56.0, 202.102.56.255] 江蘇連雲港
輸入一個 ip 地址怎麼做到秒級定位此 ip 所在的省市呢?
如圖示：在百度上輸入一個 ip 地址,能做到秒級展示其所屬地,怎麼做到的呢，背後用到了什麼原理
這就引入了我們要談的程式設計師需要具備的第一項能力: 抽象問題或者說數據建模的能力
抽象問題能力
所謂抽象問題或者說數據建模的能力，即能把一個問題抽象或歸類為某種方案來解決，比如要實現負載均衡， 會想到一致性哈希演算法，要實現最短路徑，想到使用動態規劃, 微服務下要保證服務可用引入降級機制等等,一句話就是把具體的問題抽象成到解決此問題背後的方法論，進而用相關的技術方案得以解決。
回歸到如何快速定位 IP 對應的省份地址這道題來看，如果我們不具備抽象問題的能力，硬著頭皮從頭到尾把輸入的ip 與所有區間段的 ip 都遍歷對比一遍，然後判斷它落到哪個區間，那麼 ip 地址有 32 位，共有 2^32 個，約有 42.9 億個，用暴力遍曆法每查找一個 ip 最壞情況下要遍歷約 42 億次，這種方法顯然是不可行的。
所以我們必須得把這個問題抽象為另一種可行的方法，即：二分查找, ip 地址查找怎麼就跟二分查找扯上關係了，背後的邏輯是什麼，我們一起來看看。
ip 地址不容易比較，那我們首先把 ip 地址轉成整數，於是每個省市對應的 ip 地址區間就變成了整數區間,假設為如下區間
[1, 5] [11, 15] [16, 20] [6, 10] ....
再以每個整數區間的起始數字對這些區間進行排序，排序後的區間如下
[1, 5] [6, 10] [11, 15] [16, 20] ...
看到這些排序後的區間，想到了啥，二分查找就是在一組有序的數字中進行查找！是不是找到相似點了?
這裡給沒聽過二分查找的讀者簡單普及下啥是二分查找，小時候可能我們都玩過猜字遊戲，在紙面上寫一個 1 到 100 的數字，比如 70，讓對方猜，怎樣猜才能猜最快。
- 首先猜 1 和 100 的中間數字 (1+ 100) / 2 = 50（取整）
- 50 < 70, 於是我們繼續猜 50 和 100 的中間數字 (50+100) / 2 = 75
- 75 > 70，於是我們繼續猜 50 和 75 的中間數字 (50+75) / 2 = 62
- 依次持續類似以上的步驟，不斷地縮小範圍，直至找到 70
總共只猜了 7 次，比起我們從 1 猜到 100 效率高了十幾倍，如果被猜字的範圍從一擴大到成百上千萬，提升的效率是指數級的！二分查找也叫折半查找（注意上文中加粗的中間數字），仔細看上圖，每查找一次，問題規模縮小一半，整體時間複雜度是O(logn)，即使我們要在 42 億的數字中查找數字，最多也只要查 32 次，所以採用二分查找對查找性能的提升無疑是巨大的！
二分查找是要在一堆有序的數字中精準地查找所要查找的數是否存在，而回過頭來看已經排序好的以下 ip 段
[1, 5] [6, 10] [11, 15] [16, 20] ...
我們要查找的是某個整數是否在一個有序數組的相鄰兩個數字的區間里，例如：取這些 ip 區間的起始地址組成一個數組 （1,6,11,16,….）（有序數組）,如果我們要找的 ip 對應的整型為 14， 由於它在 [11,16) (11是閉區間，16是開區間) 之間，所以這個 ip 就落在 [11, 15] 這個 ip 區間，這樣就找到了這個 ip 對應的省市了。
所以就由二分查找某個值是否存在轉變成了查找某個值是否在有序數組中相鄰的兩個值之間了，這就引入了程式設計師要具備的第二層能力：舉一反三或者說修改模型的能力
修改模型的能力
就像機器學習，現在其實有很多現成的模型可用，比如識別物的模型等等，我們需要的話可以直接拿來用，但是現有模型的準確率可能不是那麼理想（比如只有80%），如果我們需要進一步地提升識別準確率，可能就需要對其參數進行進一步的調優，以進一步地優化模型，達到我們預期的值。
再比如噹噹網基於 Dubbo 的擴展版本開發的 Dubbox 也是由於原來的 Dubbo 功能不滿足其團隊需求而在其基礎上修改擴展的。
回過頭來看以上說的原來二分查找只是查找某個值是否存在，而我們現在要解決的問題是查找某個值是否在相鄰的兩個值之間,這本質是也是對模型的調優或修改，以進一步滿足我們的要求。於是我們寫下了如下程式碼
public static int bsearch(int[] a, int length, int value) { int low = 0; int high = length - 1; while (low <= high) { int mid = (low + high) / 2; if (a[mid] > value) { if (mid == 0) { return -1; } if (a[mid-1] <= value) { return mid-1; } else { high = mid-1; } }else { low = mid + 1; } } return -1; }
那這段程式碼有啥問題嗎，或者說有哪些可以優化的空間，這就引入了程式設計師需要具備的第三項能力: 程式碼要有足夠的健壯。
程式碼要足夠的健壯
仔細看上文的程式碼，有兩個地方有潛在隱患，一個是 length 可能是負數，而顯然數組的長度不可能是負數，也就是說對這種異常數據應該拋異常。另外 (low + higth) / 2 這段程式碼中的 low+high 如果在數組很大的情況下比較容易造成溢出，所以可以改造成 low + (high – low) / 2, 另外為了提升性能可以把除以 2 改成位運算，即 low + ((high – low) >> 1)，於是程式碼變成了
public static int bsearch(int[] a, int length, int value) throws Exception { if (length < 0) { // 實際應該拋出一個繼續自Exception的異常，這裡為了方便直接拋出Exception throw new Exception("數據長度不合法"); } int low = 0; int high = length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] > value) { if (mid == 0) { return -1; } if (a[mid-1] <= value) { return mid-1; } else { high = mid-1; } }else { low = mid + 1; } } return -1; }
有人可能覺得判斷數組長度小於 0 過於嚴苛了，但是是人就會犯錯誤，這裡也是為了強調我們對異常情況的處理要到位，說到程式碼的健壯性，這裡再多說幾句,在創業初期我司主要用的是 php，主要是創業團隊追求快，用 PHP 這種弱類型語言開發確實效率高，不過不安全，線上多次出現因為變數可以隨意賦值造成的多次線上故障，而 Java 這種強類型語言雖然開發效率上比 PHP 慢了不少，但強類型語言的特徵保證了它的穩定，足夠安全，所以後期隨著人員的擴充，為了保證線上足夠安全，我司去年把大部分的服務都 Java 化了，近年來有不少人唱衰 Java，但 Java 的安全，穩定性以及強大的生態能力註定了它的長久生命力。
程式碼寫成這樣看起來確實完美了，還能再優化嗎，注意上文中的程式碼只適用於 int 的數組，如果用二分查找法進行區間查找具有通用性，比如我們想針對 short 或 long 型等類型的數組進行查找就無能為力了，所以這就引入了程式設計師需要具備的第四項能力: 程式碼要有足夠的可擴展性
程式碼要有足夠的可擴展性
怎麼讓 bsearch 這個二分查找也支援 long 型或 short 型數組呢，Java 支援重載，再針對 bsearch 進行多個函數的重載是一種方式，不過會造成程式碼的大量冗餘，所以另一種更合適的方式是利用 Java 語言中的泛型，於是我們的程式碼改造如下
public static <T extends Comparable> int bsearch(T[] a, int length, T value) throws Exception { if (length < 0) { // 實際應該拋出一個繼承自Exception的異常，這裡為了方便直接拋出Exception throw new Exception("數據長度不合法"); } int low = 0; int high = length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid].compareTo(value) > 0) { if (mid == 0) { return -1; } if (a[mid-1].compareTo(value) <= 0) { return mid-1; } else { high = mid-1; } }else { low = mid + 1; } } return -1; }
寫成這樣，可以說我們的程式碼具有足夠的健壯性與可擴展性了。
總結
本文通過一個常見的面試題來詳細闡述了優秀程式設計師必須具備的四項核心能力：抽象問題，修改模型，寫出健壯性，可擴展性的程式碼！所以為什麼面試中大廠喜歡考演算法，主要是想詳細地了解你是否具備解決此演算法題背後的思想，即抽象問題的能力，面試官還喜歡對相應演算法題進行各種變形，其實也是為了考察你是否具有修改模型的能力（比如一個翻轉鏈表，可以引申出順序每 k 個一組翻轉，逆序每 k 個一組翻轉），所以為了同時具備這兩項能力，我們需要提前掌握大量的理論知識，做大量的刻意練習。共勉！
