冒號和他的學生們(連載9)——泛型范式

          冒號和他的學生們

          ——程序員提高班紀事

          1. 泛型范式

          算法是脊,數據是肉思想是雞,結論是蛋                                      ——題記


          冒號重新開講:“你們會不會經常遇到這種情景:一遍又一遍地寫著相似的代碼,有心將其歸并,卻因種種原因無法踐行。”

          逗號心有戚戚焉道:“是啊,有時明明兩個函數的實現幾乎一模一樣的,就因為某些參數不匹配,無法合而為一。”

          “有一種編程范式可以解決這個問題,它打破了不同數據結構之間的壁壘,讓你的代碼不再臃腫,這——就是泛型編程。”冒號的語調和說辭不免令人聯想到電視上的減肥廣告,“Generic Programming,簡稱GP,其基本思想是:將算法與其作用的數據結構分離,并將后者盡可能泛化,最大限度地實現算法重用。這種泛化是基于模板的參數多態(parametric polymorphism),相比OOP基于繼承的子類型多態(subtype polymorphism),不僅普適性更強,而且效率也更高。這不能不說是一種異數——我們知道,普適性往往是以效率為代價的。GP最著名的代表是C++中的STL,其后亦為JavaC#等所吸納。此外,一些函數式語言如OcamlStandard MLGeneric Haskell等也支持GP。”

          冒號寫下兩段代碼——

          C++(泛型編程):

          template <typename T>

          T max(T a, T b)       // 求出兩個數中的較大者

          {

                return  (a > b) ? a : b;

          }

          C(宏定義):

          #define max(a,b) ((a) > (b) ? (a) : (b))

          “求兩個數中的較大值是經常遇到的問題。”冒號解說著,“對于靜態類型語言來說,若參數類型不同,即使函數體相同也不能合為一體。如果語言不支持重載(overload),還可能出現maxIntmaxLongmaxFloat maxDouble之類的函數名,冗贅而丑陋。盡管在C中可用宏定義來實現,但無法保證類型安全,而C++模板則兼顧類型安全和代碼重用,并且由于是在編譯期間展開的,效率上也不損失。不止于此,C++支持運算符重載,除數值類型外,一切定義了‘> 運算的數據類型均可調用max函數,真是一舉N得,N趨向無窮大啊!”

          冒號邊說邊比劃,夸張的語氣和手勢逗得大家都笑了。

          引號提出疑問:“Java的一切對象都是Object,將所有參數都換成Object類型,豈不也是一種泛化?”

          冒號答道:“首先,基本類型如intfloat等不是Object的子類,雖然Java 新增了自動裝拆箱(autoboxing/unboxing)的功能,但要付出性能的代價。更重要的是,這將不可避免地需要類型強制轉換,喪失了靜態類型語言的優勢,為Bug大開方便之門。這也是Java最終引入模板的原因,雖然有些姍姍來遲。類似地,C/C++中的通用指針void *也有類型安全問題。”

          句號發表他的看法:“泛型雖好,似乎只是某些局部才用到的技術,不具有前面幾種范式的滲透性。”

          冒號聽罷不語,返身在黑板上寫下幾道題——

          1.從一個整數數組中隨機抽取十個數,對其中的素數求和

          2.將一個無序整數集中所有的完全平方數換成其平方根

          3.從學生成績表中,列出門門都及格且平均分在70分以上的學生名單

          4.在一個著色二元樹中,將所有的紅色結點涂成藍色

          5.將一個字符串從倒數第三個字符開始反向拷貝到另一個字符串中

          6.每從標準輸入讀取一個非數字的字符,于標準輸出打印‘請輸入數字’

           

          句號暗忖,不過是些常規題嘛。不料冒號的問題卻出人意表:“請問它們之間有何共同之處?能否共享一段代碼?”

          見眾人緘默已久,冒號接著投影出一段代碼——

          template <class Iterator, class Act, class Test>

          void process(Iterator begin, Iterator end, Act act, Test test)

          // 對容器中在給定范圍內(即起于begin止于end)所有滿足給定條件的元

          //素(即test(元素)==true)進行處理(即act(元素))

          {

              for ( ; begin != end; ++begin)    // 從頭至尾遍歷容器內元素

                  if (test(*begin)) act(*begin); // 若當前元素滿足條件,則對其采取行動

          }

          STL有三要素:算法(algorithm)、容器(container)和迭代器(iterator)。容器是數據的集合,可理解為抽象的數組;迭代器是算法與容器之間的接口,可理解為抽象的指針或者游標。”冒號講述道,“算法串聯數據,如脊貫肉;數據實化算法,如肉附脊。只有抽象出表面的數據,算法的脊梁才能顯現。以上幾題看似風馬牛不相及,若運用泛型思維,便可發現它們的共性:對指定集合中滿足指定條件的元素進行指定處理。用模板語言,寥寥數行即勾勒完畢。”

          問號詫異道:“相比前面的max模板,這里連元素的數據類型T都不見了?”

          冒號回答:“元素被容器封裝了。”

          問號追問:“可這里連容器也看不到啊?”

          冒號料有此問:“容器通過它的迭代器參與算法。”

          句號豁然開朗:“通過模板,泛化了容器——可以是數組、列表、集合、映射、隊列、棧、字符串等等;泛化了元素——可以是任何數據類型;泛化了處理方法和限定條件——可以是任何函數。”

          冒號提醒道:“補充兩點:處理方法和限定條件不限于函數,還可以是函子Functor)——自帶狀態的函數對象;另外還有一個隱蔽的泛化:迭代器——可以從前往后移動,可以從后往前移動,可以隨機移動,也可以按任意預先定義的規律移動。”

          嘆號由衷感嘆:“果然強悍啊!”

          逗號倒也心細:“最后一題中標準輸入也算容器嗎?”

          “為什么不呢?只要一個對象配備了迭代器,它就算容器。I/O流上就有現成的迭代器,當然你也可以自行定制。”冒號目光轉向句號,“現在還有人說泛型編程滲透性不強嗎?”

          句號腆然一笑。

          “這只是泛型編程的冰山一角。重要的是,我們不是在玩弄花哨的技巧,而是在用一種新的視角去審視問題。”冒號總結道,“泛型編程是算法導向Algorithm-Oriented)的,即以算法為起點和中心點,逐漸將其所涉及的數據結構內涵模糊化、外延擴大化,從而擴展算法的適用范圍。這非常類似數學思維——當數學家證明完一個定理后,總會試圖在保持核心思想的前提下,盡可能地放寬題設,增強結論,從而推廣定理。外行人以為數學定理最重要,其實數學思想才是數學的精髓,在數學家眼里,思想是雞,結論是蛋。這也無怪乎STL會出自一位學數學的人之手了。”


          新版請見冒號課堂§3.1:泛型范式

          posted on 2008-05-09 00:09 鄭暉 閱讀(4693) 評論(4)  編輯  收藏 所屬分類: 冒號和他的學生們

          評論

          # re: 冒號和他的學生們(連載9)——泛型范式 2008-05-09 08:45 yanhuaking

          寫得很好,拜讀了!感謝!  回復  更多評論   

          # re: 冒號和他的學生們(連載9)——泛型范式 2008-05-09 09:44 herowzz

          繼續支持~~~  回復  更多評論   

          # re: 冒號和他的學生們(連載9)——泛型范式 2008-05-13 15:33 支持支持!

          例子可以再多些,簡明是好,我也貪心多學一些,哈哈!!1  回復  更多評論   

          # re: 冒號和他的學生們(連載9)——泛型范式 2008-12-24 19:38 杜飛

          泛化。。。好  回復  更多評論   

          導航

          統計

          公告

          博客搬家:http://blog.zhenghui.org
          《冒號課堂》一書于2009年10月上市,詳情請見
          冒號課堂

          留言簿(17)

          隨筆分類(61)

          隨筆檔案(61)

          文章分類(1)

          文章檔案(1)

          最新隨筆

          積分與排名

          最新評論

          閱讀排行榜

          評論排行榜

          主站蜘蛛池模板: 盐池县| 涪陵区| 高陵县| 长汀县| 锦屏县| 六安市| 安国市| 平果县| 保德县| 凤凰县| 盐边县| 雷山县| 雅安市| 灵山县| 英德市| 城口县| 遂川县| 克东县| 深泽县| 高尔夫| 平泉县| 会东县| 阜南县| 涞水县| 湘乡市| 黎城县| 宜春市| 元谋县| 滁州市| 张掖市| 沈阳市| 永福县| 时尚| 商水县| 凉山| 长治县| 杨浦区| 光泽县| 什邡市| 钦州市| 株洲市|