???? 本以為英漢字典的程序已經沒有什么大問題了，沒想到今天段伏櫪想查一個單詞，卻發現事情根本就不是自己所料想的那么順利：單詞的查找速度太慢！這就奇怪了，之前為什么沒有發現呢？說起來也讓人啼笑皆非。之前之所以沒發現這問題，是因為測試的時候，輸入的單詞都是以“a”開頭的，而今天碰巧要查找的單詞，卻是以“x”開頭！就這么一個小差別，導致搜索所花的時間居然要比“a”開頭的字母多兩分鐘！ ??? ??? 這也是沒有辦法的事，因為段伏櫪的查找算法，是最最最原始的：從“a”開始，一個一個進行對比，看看哪個單詞最符合。換句話來說，如果單詞不存在，或是位于字庫的后半部分，那么搜索所花費的時間絕對是讓人咋舌的。其實一開始寫查找算法的時候，段伏櫪也擔心過這個問題，但沒想到的是，當自己將程序寫完之后，居然把這碼子事給忘了；并且測試的時候，都是以“a”開頭，那搜索的速度自然是超快，更讓段伏櫪完全淡忘了這問題。 ??? ??? 怎么辦？這樣的效率，擱誰身上都受不了啊。總不能查一個“a”開頭的單詞不到十秒鐘，但找個“z”開頭的，撒了泡尿回來泡了杯茶后還沒結束吧？沒轍，修改算法唄。算法？段伏櫪一想到這兩個詞，腦袋就變成兩個大。對于高考150分滿分只考了60分，看到傅里葉變化就兩眼冒金星的段伏櫪來說，讓他去折騰算法無異于慢性折磨。 ??? ??? 這帶來一個很有意思的話題：程序員究竟要不要研究算法？其實這在業界中也是一直爭論不休。正方的意見是，不懂得算法，那么就不能更好的理解計算機，寫出的軟件效率就會非常低，因為程序就是代碼+算法的結合；而反方的意見呢，無非就是說現在有很多算法庫，可以直接拿來就用，根本就不必要去深究，不必要再花費心思去研究輪子如何工作。關于是否需要專研算法的問題，段伏櫪沒有絲毫的猶豫，義不容辭直接選擇反方，這倒不是因為他多么的高瞻遠矚，或是有什么堅定的信仰之類，純粹是因為他先天不足：從小對數學就不感冒，看著這變化來變化去的公式就頭暈，這模樣還怎能研究算法？ ??? ??? 話又說回來，程序員要不要學算法，這的確要分開兩個方面來看，不能一概而論。比如說，如果要到谷歌或百度這樣的公司，因為他們是以算法優勢起家的，如果你不研究算法，對算法一竅不通，那么進去最多就是打打醬油，說不定哪天主管心情不好了，還會請吃魷魚。但如果是到一些主要是做產品的公司，你天天研究算法也不行啊：產品的界面，客戶的體驗等等雜七雜八都需要你去完善，可你偏偏在研究什么樣的算法效率會高一點點，而這些卻偏偏是客戶無法直觀感受到的，那么估計炒魷魚這道菜還是免不了的。 ??? ??? 盲目崇拜，或是盲目鄙視算法，這兩種態度都是不可取的，關鍵是看自己用算法來做什么。就像一輛法拉利跑車，估計沒有人會說它差，開著它在路上狂奔，估計是一個非常愜意的享受。可是如果任務是要從大陸到日本，需要越過海洋，那么這法拉利的價值估計還不如一艘破船。可是這時候，你能說法拉利一無是處嗎？一無是處的是使用者，因為他沒有將法拉利用在最恰當的場合。算法也是如此，它是否有用，能發揮多大的作用，關鍵是看用它的人，看用它的場合。 ??? ??? 根據對算法的掌握程度，大體上可以將程序員分為三類：第一種是對算法非常精通的，第二種是知道有哪么些算法概念知道相應的算法庫該如何使用的，最后一種是對算法一竅不通甚至連算法庫都不知道的。這三種人之中，第一種是神一樣的人物，適合于從事提升產品競爭力的工作；第二種便是大多數程序員所處的范圍，適合產品的應用開發；最后一種嘛，便是菜鳥級別的，遇到和算法有關的問題只能撞得頭破血流。很不幸，段伏櫪就屬于最后一種。 ??? ??? 當然，現在是菜鳥，并不代表一無是處，高手嘛，不也是從雛鳥開始的？俺就不信，那些算法高手，在娘胎的時候就懂得傅里葉變換？只聽過用柔和的音樂來進行胎教的，可還真沒聽過念數學公式來進行的。絕對不向困難低頭，是段伏櫪一貫堅持的信念，也是一直能夠進步的原因之一。不就個算法嘛？這還難得了俺？拿本算法書看看不就好了。確實是拿本算法書看看，很多不明白的東西都清晰了，可這也要能看得懂啊。沒翻幾頁，段伏櫪就翻白眼了：這是哪門子的邪門歪道？中文每個文字都能看懂，字母才26個字母，可組合起來，咋就跟天書一樣了呢？還有還有，這算法的評判標準也太麻煩了吧？不同情況下的表現形式還不同啊？這不折騰老子嗎？ ??? ??? 算了，管它那么多，還什么算法優劣呢！以自己現在的水平，等研究出來，估計到時候公司在不在還不好說。不用去想那么復雜了，那是不是自己這個水平檔次的人所能干的事。自己只要算法比以前的那個逐個逐個比較要快，每個單詞查找的時間差不多就行了。 ??? ??? 只是，要選哪個呢？這些英文在的排列是按順序的，如果以二分法的話，直覺上應該可以快很多；并且這二分法的特性，對于已經排序的單詞來說，查找的頻度應該相差無幾。好，那就是它了！就是二分法！其實，如果不選二分法，那也沒有其它的選擇了，因為對于段伏櫪來說，只有這二分法他還能看得懂，還能夠比較容易地轉化為代碼。 ??? ??? 因為之前的單詞搜索是在DLL文件中，所以要更改算法的話，只需要更改DLL的源文件即可。不僅如此，之前的算法暴露的是一個函數接口，現在只需要更改函數體的內容，而不必重新書寫代碼。雖然當時段伏櫪寫程序的時候，并沒有考慮到后續可能需要更改算法的狀況，但憑借著直覺，覺得有一些東西應該以函數形式封裝起來，沒想到這給后續的修改省去了不少麻煩。 ??? ??? 英文單詞是以數組來存儲的，如果要更改算法，只需要增加三個指針，分別指向開頭，末尾，和中間的序號，然后再和所要查找的單詞做比較即可。算法轉換為代碼，并不是很困難的事，但有一些小細節卻需要注意，所以段伏櫪花了整整一天時間，才讓這算法正常工作。過程是曲折的，但結果是喜人的，這么一更改之后，搜索后半部單詞的速度確實比之前要快很多，簡直完全是天壤之別。看著改善后的英漢字典程序，段伏櫪不禁手舞足蹈：自己終于也能寫字典程序了！當年老章所做的事情，自己也能做了！更為重要的是，一向對算法白癡的自己，居然還懂得寫了個二分法算法！還有什么能比這更高興的嗎？ ??? ??? 只不過當時的段伏櫪不知道，如果要寫像他現在這種檔次要求的字典程序，完全可以不用這么麻煩：不用去考慮如何存儲字典數據，不用考慮如何根據返回值查找注釋，不用花費心思去考慮查找算法——因為這一切，只需要使用STL的multimap即可解決。multimap的結構很簡單，是以key-value的方式存儲。如果應用到英漢字典，那么key存儲的就是英文單詞，而value自然就是注釋了。一旦需要查詢的時候，那也是非常簡單，直接調用find函數即可。那么這STL的效率如何呢？只能說，STL的算法可能并不是最佳的，但絕對不是最差的，不過對于段伏櫪的應用而言，完全是綽綽有余。 ??? ??? 雖然段伏櫪在《C++ primer》見過multimap的身影，但該書對于應用卻惜字如金，并沒有很好詮釋用法。所以段伏櫪對此的印象也不是很深，在編寫程序的時候自然沒有想到使用該容器。如果在此之前段伏櫪看過《C++ 標準程序庫》的話，可能情形截然不同。該書從最基礎開始，給讀者介紹了STL的使用，特別是其中的一章，更是以字典為例來進行講解如何使用multimap，恰好和段伏櫪的程序要求不謀而合。 ??? ??? 這不能不說，多看書，對于程序員而言，是多么重要。也許看的時候確實一竅不通，但只要你對此有了那么點印象，知道有那么一回事，說不定就這么一個靈感，會讓以后的工作省掉很多的麻煩。