Benoît Mandelbrot 與碎形
雲、山、海岸線、閃電等都是自然界可看到的碎型,複雜而不規則。然而這是自然之所以美的原因。如果雲是圓形的,那多無聊。而如果數學不能捕捉自然之美,那是多麼可惜的事情。碎型理論揭去了這層神秘的面紗,告訴我們,這些自然事物的「規則」其實隱藏在另一個維度中。
雲、山、海岸線、閃電等都是自然界可看到的碎型,複雜而不規則。然而這是自然之所以美的原因。如果雲是圓形的,那多無聊。而如果數學不能捕捉自然之美,那是多麼可惜的事情。碎型理論揭去了這層神秘的面紗,告訴我們,這些自然事物的「規則」其實隱藏在另一個維度中。
為什麼這麼慢呢?Bentley 和 McIlroy 認為問題出在我們花了太多工夫把兩個白色元素一步步挪到中間。與其如此,不如先把白色元素放到兩邊去,把陣列排成「白、紅、藍、白」。等排序完成,再把白色換回中間就可以了!
這是一個 O(N-M) 的程式。如果三色數量相同,我們平均需要大約 2(N-M)/3 次交換。如果我們當初選擇從檢查 a[b-1]
開始,平均需要的交換次數則是 N-M 次。
陣列裡頭每個元素都是紅、白、藍三色之一。如何把它們由左至右依紅、白、藍的順序排好呢?Dijkstra 希望採用三向分割法後能更容易表達紅(小於 pivot)和藍色(大於 pivot)的區塊絕對比原陣列短的性質。然而,在 Peter 的印象中 Dijkstra 從沒把這層考量寫下來。「我們如果不告訴學生,以後就沒人知道了呢!」他說。
令 Gordon 感興趣的是,稿子上方手寫著「投稿給 JACM, 1971 年九月」。但大家知道這篇論文一直都是技術報告。難道 JACM 把它退件了嗎?
從 2006 年開始,每次的 International Conference on Functional Programming (ICFP) 回顧十年前發表的論文,看看哪篇最經得起歲月的考驗,在十年中發揮了最大的影響力。ICFP 2010 剛在上個月底落幕,而這是 ICFP 2000 的論文列表。如果您是評審,會頒獎給誰呢?