演算法性能大躍進
電腦性能的快速進步,往往顯而易見,摩爾定律(Moore’s law)就是典型的代表。由英特爾(Intel)創始人之一葛登‧摩爾所提出的摩爾定律,自1975年就預示,大約每隔18個月,在積體電路上可容納的電晶體數目便會增加一倍;換言之,每隔一年半,晶片的工作效能就會提高一倍。這麼多年來,硬體是如此快速地發展,然而對於軟體的演算法來說,是否也如硬體一般,成長速度如此地飛快?
德國布倫瑞克工業大學(The Technische Universität Braunschweig)的數學教授賽巴斯提安・史帝樂(Sebastian Stiller)在其出版的《演算法星球:七天導覽行程,一次弄懂演算法》(Planet der Algorithmen)一書中,曾經用了一個故事來進行比較。
他的故事是這樣說的,時間回到1990年,有A、B兩個團隊必須透過電腦與演算法,解開一個程式任務。而兩隊都可以透過時空旅行,前往2014年。其中,A團隊從2014年帶回一台性能最新的電腦,來跑1990年的程式(演算法);B團隊則帶回來2014年最新的程式(演算法),並用1990年的電腦來跑。現在,請您來猜猜,哪一隊會比較快得出任務結果?
答案揭曉,A團隊用2014年最新的電腦來跑舊程式,比1990年的電腦快上6500倍(大致符合摩爾定律);B團隊用舊電腦跑2014年的新程式,比跑1990年的舊程式快了87萬倍,A、B團隊兩者相差130多倍,如圖1所示。
從上面的故事,可以發現,我們經常低估了演算法性能的高速進步。
其實,依據維基百科的定義,演算法(algorithm)是一個已被定義好的、且電腦可施行指示的有限步驟或次序,它經常被用來計算、處理資料和自動推理。例如,在許多購物網站上,消費者可以選擇使用關鍵字的「精準度」或「價錢由低到高」來排序,這些都是人們藉以實現省時省力目標的高效演算法。
值得注意的是,要讓演算法性能能夠有效提升,並不需要用到什麼特殊的材料,或者是更多的能源。它的功力升級,純粹是一種找到更簡單、更省事的解決方法。因此,史帝樂教授認為,能夠設計出更省力的演算法,就是一種「懶惰的藝術」。
他在書中提到:「高超的懶惰,需要知識、心智的敏銳,還有決心,並在必要的時刻全力以赴。運用毫無瑕疵的懶惰,來完成任務,則是演算法之中,最燦爛的時刻。」(引用自,Sebastian Stiller著,張璧譯,《演算法星球》 (Planet der Algorithmen),八旗文化,2016,第18頁。)
這就是演算法思維的真諦。
作者:羅凱揚(台科大企管系博士)、蘇宇暉(台科大管研所博士候選人)
繪圖者:謝瑜倩