本文為圖靈社區對劉新宇的專訪，專訪時間為2017年1月。
劉新宇，於1999年和2001年分別獲得清華大學自動化系學士和碩士學位，之後長期從事軟件研發工作。他關注基本算法和數據結構，尤其是函數式算法，目前就職於亞馬遜中國倉儲和物流技術團隊。
他七年磨一劍，筆耕不輟，寫成《算法新解》一書。
《算法新解》總共分4部分——樹、堆、隊列和序列、排列和搜索，用函數式和傳統方法介紹主要的基本算法和數據結構，數據結構部分包括二叉樹、紅黑樹、AVL樹、Trie、Patricia、後綴樹、B樹、二叉堆、二項式堆、斐波那契堆、配對堆、隊列、序列等；基本算法部分包括各種排序算法、序列搜索算法、字符串匹配算法（KMP等）、深度優先與廣度優先搜索算法、貪心算法以及動態規劃。
圖靈：新宇老師花費七年的業餘時間寫就這本《算法新解》，足見您對技術的這份執著！但在升職加薪、拼命加班的大環境下，怎麼做到“不盲從，有見解”？
劉新宇：我想分享自己的兩個想法。
第一個想法是關於變化的。面對劇烈變化的時代，飛速發展的技術，絕大多數個體都會感到壓力。出於自我保護的本能，我們需要在變化的大潮中找到相對不變的東西。什麼是不變的呢? 語言？框架？還是操作系統？在我上大學的時候，實驗室中還在廣泛使用Fortran語言用於科學計算。但是幾年之間，C語言就替代了Fortran成為了主流語言。今天，各種新語言更是層出不窮；框架也是如此，我還記得上學的時候，大家懷著很高的熱情學習微軟的MFC框架。可是今天，除了在個別場合，很少有人還在用MFC了。各種框架也是如雨後春筍一般出現在各種領域；操作系統呢？我曾經在諾基亞的Symbian操作系統上開發了近10年。在Tanenbaum的經典教科書《現代操作系統》的附錄中，Symbian被作為成功的嵌入式操作系統案例加以講解。可是2011年，Symbian幾乎在轉瞬之間就轟然倒塌。2014年，當我完成這本書的英文草稿的時候，正逢諾基亞解散。這些經歷使得我不斷思考這一問題。
如果我們觀察一個小孩的行為，會發現非常有趣的現象。大約在3到5歲間的孩子，不管父母怎麼向他推薦新鮮的公園，好吃的餐館和旅遊度假計劃，孩子卻往往拒絕。他堅持重複去自己熟悉的公園，到相同的地方吃飯，假期待在自己的家裡，甚至連講故事都要求不斷重複同一個故事。這是因為孩子通過重複相同的、不變的東西，獲得安全感。這個世界對他來說太複雜了。我們成人何嘗不是如此呢？所以害怕變化是很正常的，沒有什麼不好意思的。但是如果我們繼續觀察這個孩子，會發現隨著成長，在他逐漸掌握了身邊的世界後，那顆好奇心就會驅使他出去探險，去探索未知的世界。
第二個想法是關於求知的。拋開商業產品不算，人類真正在科學技術上的成就，沒有一次是功利性的。諾貝爾科學獎中沒有任何一位是為了獲獎而研究。2006年證明了龐加萊猜想的數學家佩雷爾曼乾脆拒絕去領菲爾茲獎。真正驅動我們長久進步的是好奇心。是像小孩子那樣的探索世界的慾望，我只是想打開那些黑盒子，看看裡面是什麼。並把它分享給別人：“嘿，快來看，盒子裡原來是這個樣子的！”。這就是我這些年來寫這本書時的情況。
最後，我用兩個例子結束這個問題：一個是數學家陳省身先生的例子，在抗日戰爭中最艱難的日子，大家朝不保夕，顛沛流離，他卻反而靜下心來學習研究微分幾何，發現陳類（陳省身示性類）。2016年的諾貝爾物理學獎中的一個發現，就是物質的拓撲相中的量子化整數是陳省身數。第二個例子是大學問家錢鍾書，他也是在抗日戰爭中的敵佔區上海，每天錙銖積累，寫的《圍城》。他們都是我的榜樣。
圖靈：您負責的倉儲和物流技術中，運用了哪些算法？
劉新宇：亞馬遜的倉儲和物流系統，是一個非常複雜的系統。其複雜程度會出一般人的想象。這是一個分佈在全球的倉儲網絡，面臨著巨大的技術挑戰。在每年的第四季度，連續放假、過節，新年、聖誕、感恩節、黑色星期五、雙十一時，消費者拼命購物，賣家和供應商拼命進貨，這在物理上和數據上都對倉儲和物流系統形成了巨大的衝擊。出於業務上的挑戰，我們把自己的技術架構在亞馬遜的雲計算平臺AWS上，處理大數據下的高可靠性、併發性和一致性的問題。這裡會用到很多的算法，包括最優化的算法和機器學習算法，等等。我們會根據庫房的容量對貨物在倉儲網絡中做優化的配置，我們會使用機器學習預測進出庫的時間，等等。正因如此，亞馬遜對於研發團隊工程師的算法能力有很高的要求。
在亞馬遜的面試中，算法與數據結構是一個必考的環節，甚至是一票否決的。圖靈：聽說，您曾經在去匈牙利出差的飛機上，居然看了一路的數學書，還是英文版的？這不免讓我們回到老生常談的問題——“算法跟數學的關係”。
劉新宇：其實我還看了一本中文的，名叫《斐波那契數列》。算法是數學的分支。
我想分享一下，“算法” 這個詞的來歷。公元9世紀，也就是中國的唐朝，在阿拉伯文明的中心——巴格達，有一位來自東方的大學者剛剛完成了一本著作，書名叫《還原與對消的科學》（Kitab al-Jabr wa-l-Muqabala），講述瞭如何解二次以內的方程。人們用這本書的拉丁文簡稱Al-Jab，創造了詞Algebra。1859年，李善蘭與英國傳教士偉列亞力創造性地將其翻譯為“代數”。
遺憾的是，沒有人知道這位僑居在巴格達的數學家的真正名字。人們只知道他來自一個名叫花剌子模的東方國家。金庸先生寫的《射鵰英雄傳》讓這個國家的名字在華人圈得以普及（就是郭靖與黃蓉幫助成吉思汗攻破的國家）。如今的烏茲別克斯坦的撒馬爾罕，至今仍立有這位數學家的雕像。於是來自（Al）花剌子模（Khwarimi）的人，Al-Khwarimi（阿爾-花剌子密）就成了這位數學家的名字。它的拉丁文譯法為Algorithm，中文譯作“算法”。
為什麼用這位數學家的名字來命名算法呢？這要談談花剌子密是怎樣描述解方程的。在著作中，他使用了詳細的文字來描述解方程的步驟。這和我們現在描述計算機算法的的方式幾乎一模一樣。其實，我們的前輩在發展代數時，大約經歷了三個階段：文辭代數、簡字代數、和符號代數。早期的各個文明，絕大多數都採用詳細的文字來記述解決問題的過程和步驟。我們中國的老祖先在很早以前就使用算籌，實現了多元線性方程組的求解。如果閱讀《九章算術》，就會發現它也是用文字描述，講解了方程組的解法（本質上就是高斯消元法）。直到16世紀，文辭代數仍然是主流的代數描述手段。後來古希臘的丟番圖，逐漸使用了一些符號簡記方法，發展了簡字代數。現代的符號代數在萊布尼茨時達到了頂峰。極大提高了數學語言的嚴謹性和表達能力。可是反觀我們現在的算法描述和很多計算機語言，似乎仍然停留在文辭代數階段。一段算法或者程序寫下來，更像一段文章，而不是一組簡約的符號化、形式化的公式或者圖形。這一想法也是我在寫這本書時逐漸形成的，我也一直在思考這個問題。
圖靈：《算法新解》裡的“新”字怎麼解釋？
劉新宇：新是相對的，新的東西可以變成舊的，舊的東西也會煥發新生。這本書中大量介紹的函數式算法，對於很多傳統程序員來說，也許比較陌生，是需要了解的新東西。其實它的歷史卻並不短。在20世紀30年代，人們就開始研究可計算性問題，這是一個關於數學基礎的問題。我們計算機行業的老祖師圖靈，和美國普林斯頓的丘奇（Alonzo Church）分別獨立地提出了各自的模型（同時代的其他研究者還包括哥德爾（Kurt Gödel）和克萊尼（Kleene），這一問題後來被稱為丘奇——圖靈論題）。其中圖靈使用了圖靈機的想法，而丘奇則使用了Lambda演算（波斯特還給出過遞歸函數的模型）。這些模型後來被證明都是等價的。
當然可計算性問題最終給出的是一個否定的答案，著名的圖靈停機就是一個反例。其中丘奇的Lambda演算，成為了後來函數式計算模型的理論基礎，直接孕育了Lisp語言，就是世界上第二早的高級語言。對於函數式編程和算法的研究也一直在學術領域進行。由於基於傳統的命令式的方法，包括我們熟知的面向對象方法在工業和商業上取得了巨大的成功，因此函數式方法對於大多數程序員比較陌生，屬於“新鮮事物”。但是最近這一情況正在改變，越來越多的主流編程語言開始加入一些函數式的特性，如C++、Java 8都加入了對lambda的支持。
圖靈獎獲得者，迪傑斯特拉（Dijsktra） 說過：“程序=數據結構+算法”。使用函數式編程，如果不瞭解函數式算法就只能停留在表面，寫出像“hello world”這樣的簡單程序。 這也是《算法新解》這本書希望能夠幫助讀者的一點。
這本書的章節安排和傳統的大多數算法書不同，這也算是“新”的一個體現吧。按照函數式的思維，許多在命令式算法中比較複雜、困難的東西，一下子變得簡單了，“紅黑樹”就是這樣一個例子。使用函數式算法後，紅黑樹的實現只需要16行。這樣按照難度來算，紅黑樹就排在了前面 。相反，有些看似容易的東西，想用函數式的方式實現卻並不簡單，例如隊列和序列。我把這些比較難的內容安排在了後面。如果講解完一個函數式的數據結構後，我們發現能立即用來實現某個算法，就穿插著講一章算法。例如插入排序被安排在二叉樹後，選擇排序被安排在堆的後面就是這個原因。函數式算法的最底層、最基礎的數據結構是鏈表，反覆斟酌後，我把它作為附錄列在書後。有一些函數式編程基礎的讀者可以隨時參考，而零基礎的讀者可以先集中看一下。
圖靈：命令式編程中的算法多使用狀態記錄，對於無狀態的函數式編程該怎樣找到對應的算法？
劉新宇：對這個問題，我想打個比方。這就好比代數和幾何的關係。大家在上學時一定有這樣的體會：有些代數問題，一旦轉化成幾何問題，就變得特別簡單直觀。一個簡單的圖形，加上一條輔助線，瞬間就解決一個複雜的問題。相反，有些特別難的幾何問題，一旦用解析幾何轉換成方程，一下子就變得很簡單了。
命令式編程和函數式編程也是如此。我們並非說一種方法就一定比另一種方法好，而是說某些問題，一旦轉換思路反而比較容易。有時是函數式算法容易一些（例如紅黑樹），有時是命令式算法直觀容易一些（例如KMP匹配算法）。
其實函數式的方法並不那麼難理解。我是在中學接觸到計算機編程的，當我第一次看到x=x+1這樣式子時，著實花費了很大的功夫來理解。因為按照數學課上的思維，我會不自覺地想要把等式兩邊的x消去，這樣不就成了0=1了麼？當然，按照命令式的思維，我們是把一個盒子裡的東西取出來，加上1後再裝進去。所以函數式的思維，強調不變性，也許更加符合我們長久以來形成的解決問題的習慣呢。當然，也有一些地方是命令式思維更加自然。例如一位同學繞著操場跑步，手裡拿著計數器，每跑完一圈就按一下使得計數器加一。這樣用命令式的方式思考就更加自然。因此，我們不要強求一定找到一個對應的函數式算法或者命令式算法，而是不斷地轉換思維，用最有效的方法來解決問題。
圖靈：設計算法時，通常使用順序模型，很少考慮算法的並行化擴展。但是在實際應用中，很多難以並行擴展的算法由於時間上不能滿足要求而被放棄。您認為設計算法時是不是應該考慮並行擴展的因素？
劉新宇：是的，我們要考慮並行。由於摩爾定律不再適用，人們不得不發展並行計算。而函數式方法具有一些特點，如強調不變性，無副作用。對於任何一個函數，在相同的時間、地點、用相同的參數調用，總是能得到同樣的結果。這些特性特別有利於並行計算，因為現代編譯器和運行系統，可以方便地對這種無副作用的計算進行並行。這也是為何近年來Erlang、Scala等函數式編程語言流行的一個原因。
圖靈：市面上大部分的算法書雖然給出了具體算法和效率分析，但很少對算法的正確性給出證明。您認為證明算法的過程在算法學習中是否重要？
劉新宇：我想從更寬泛的角度談談證明的意義。證明不在於確認或者推翻一個結論，而在於在證明過程中發展出來的方法和工具。例如，人們探求5次以上的方程是否存在根式解的過程中，這裡有兩個非常感人和值得我們深思的故事，一個是丹麥的阿貝爾，一位是法國的伽羅瓦。在他們之前，人們雖然攻克了4次以下方程的求根公式，但是在5次方程上持續了幾百年都沒有進展。阿貝爾和伽羅瓦獨立發展出了群論，最終證明了5次以上方程沒有根式解。雖然這是個否定的結論，但是在這一證明過程中發展出的群論和抽象代數，成為了特別強大的工具，可以幫助我們解決更多的問題。現代計算機科學的前沿：設計安全的編程語言，就在使用範疇論，而範疇論正式從抽象代數的基礎上進一步發展出來的。 另一個例子是著名的費馬大定理，證明採用了橢圓函數論，現在我們知道，這是現代密碼學的理論前沿。
證明對於算法學習有促進作用，證明迫使我們更加深入思考，甚至從不同視角看待一個問題。例如，我們熟知的喝醉酒的獄卒問題。典獄長第一次將所有燈的開關板動一次；第二次把第2、4、6……這樣的偶數開關板動一次；第三次把所有被三整除的開關扳動一次……問最後哪些燈亮著？當解決這個問題後，觀察答案，就會發現它們都是完全平方數？為什麼是這樣的結論呢？有沒有可能證明這個結論呢？深入思考就會發現這個問題的本質是思考哪些數有奇數個因子。這樣就加深了我們的理解。因此，證明的過程對於學習算法是非常有幫助的。
圖靈：對於初學者來說，學習算法很枯燥。有哪些方法可以發現算法的樂趣？
劉新宇：我想做一個類比，在學校學習數學和物理時，你覺得哪一門不那麼枯燥呢？是數學還是物理？我想可能選物理的同學會更多一些。這是因為物理老師很會講故事，就是現在我們網絡上常說的“段子手”。物理中有太多精彩的故事了，伽利略的比薩斜塔實驗故事，阿基米德和王冠的故事，牛頓的蘋果和萬有引力的故事（雖然有人說是牛頓侄女杜撰的），法拉第發現電磁感應的故事，居里夫人發現鐳的故事，愛因斯坦的故事和逸聞趣事就更多了。可是相比起來，數學教科書的故事就少的可憐。印象中只有神童高斯解決1加到100的故事。其實數學裡面也有很多精彩的故事，例如希帕索斯發現了無理數被謀殺的故事， 阿基米德死前還在地上繪圖的故事，牛頓和萊布尼茨爭論誰先發明瞭微積分的故事，希爾伯特講的無窮旅館的故事。還有伽羅瓦死於決鬥的悲劇故事。
學習算法時，我們同樣需要有趣的故事。有許多算法來自歷史上的著名趣題。例如約瑟夫環問題，講述的是猶太——羅馬戰爭中約瑟夫和其他總共41人被困後，每間隔一人就自殺，問想倖存下來，要站在哪個位置上的問題。又比如五猴分桃問題，講述五隻猴子採桃後，每隻猴子都偷偷醒來，吃掉自己的一份，然後在平分桃子，問一共有多少桃子的問題。還有漢諾塔問題、野人修道士問題、嫉妒的三對夫妻問題、華容道問題，等等。思考和解決這些趣題是充滿樂趣的。
圖靈：還有相當一部分人學習算法的時候，主要靠“背算法”。實際工作中，無法把問題很好地抽象到算法層面。該如何訓練這種算法思維呢？
劉新宇：有很多程序員標榜自己是完美主義者，是代碼潔癖。我覺得這很好，但是我們不能僅僅把潔癖停留在縮進、括號、和空格上；也不能僅僅停留在final和const這些關鍵字的使用上。當看到代碼不美，不簡潔，有重複時，通過抽象、改進，會慢慢發展算法思維。我以前曾經開發過這樣一個程序，在社交app的列表中要顯示用戶的好友，產品上設計了很複雜的業務邏輯。比如，在線的好友在前面顯示，離線的在後面顯示，VIP在前面顯示，最近聊過天的在前面顯示，等等。代碼中有很多if-else來實現這些複雜的邏輯。經過思考，最終把這些複雜的業務邏輯抽象成了當給定好友A和好友B時，如何決定A在B之前的比較。這樣整個程序就化簡成了一個排序算法。只要不斷追求簡潔優美的代碼，就會自然而然產生算法的思想。對比前面的問題，我們談的主要是如何求真，而這個問題，我們需要的是求美。
圖靈：算法無處不在，它可以讓我們的生活更輕鬆，但如果完全把我們的生活外包給計算機，會產生什麼樣的後果？
劉新宇：我在小學的時候，非常喜歡完井字棋遊戲。就是在九宮格里，一人劃叉，一人劃圈，看誰先連成一條直線的遊戲。我對此很是痴迷。後來學習計算機時，講到人工智能和博弈，才瞭解到井字棋並不存在必勝的策略。理性的玩家總是打成平手。可是這並不妨礙我繼續玩井字棋，我現在也和自己的孩子玩，而且偶爾還會輸給他。我想說，我們人類能解決的問題，僅僅佔到了全部問題的一小部分。如果計算機、人工智能和算法的進步能幫助我們爭取時間，解決更重要的問題，那就太好了。
《算法新解》，劉新宇 著
本書同時用函數式方法和傳統方法介紹了主要的基本算法和數據結構，數據結構部分包括二叉樹、紅黑樹、AVL樹、Trie、Patricia、後綴樹、B樹、二叉堆、二項式堆、斐波那契堆、Pairing堆、隊列、序列等；基本算法部分包括各種排序算法、序列搜索算法，字符串匹配算法（KMP等），深度優先、廣度有限搜索算法、貪心算法以及動態規劃。
閱讀更多 人民郵電出版社 的文章
