Last Friends

由長澤雅美以及上野樹里主演的日劇 Last Friends是一部像女王教室那樣，那種讓正常人看了之後會有點受不了的日劇。不過沒有女王教室那麼誇張就是了。劇中的主題是家庭暴力以及心理精神上的問題。

長澤雅美飾演的美知留是家庭暴力的受害者。很標準的，這個角色會讓人從一開始的同情，漸漸因為她不斷原諒施暴者，變成讓人覺得有點不值得同情。而施暴者（美知留男友）宗佑的職業竟然還是在兒童福利課服務的公務員呢，這更讓人有種知法犯法的反差。

這樣的安排，如上所述，很標準。讓人覺得很寫實。如果只是這樣，也不過就是寫實而已。對我來說，Last Friends 讓我可以有點了解宗佑以及美知留這種典型的立場。

宗佑生病了。他的心生病了。由於幼年時他媽媽拋下他跟別的男人跑了，所以他從小都很孤單。有些有類似遭遇的人可以自我調適，但很不幸的，他沒能辦到這點。因此，他一直處於痛苦中，想要逃離這種孤單的狀況。他應該是一直幻想能夠找到一個適當的對象，組成一個家庭，生下小孩，然後讓小孩能有他過去沒有過的童年生活。

他找到的對象是美知留。但又由於從小缺少模仿及練習的對象，他與人相處的技巧和成熟度其實很有問題。跟美知留在一起他是幸福的，因為美知留了解他。即使他缺乏愛人的技術，他還是盡量模仿癡情男該有的動作。也許是看電影學的，有點戲劇化，但還有模有樣的。

由於極為害怕孤單，又由於小時候媽媽拋棄他，所以他極為害怕美知留拋下他跑掉。害怕的程度已經到達病態了。更大的問題是，由於他從小缺少學習相處技巧的機會，他不知道怎麼解決這個問題。他只有最本能最原始的方式，暴力。

他想要改善這個世界，他想要靠他的力量來辦到這件事情。這也就是他努力考上公務員，然後從事兒童福利工作的原因。他很聰明，知道很多手段。但是與人相處這種事情太難了，沒有經年累月的練習是不行的。由於他夠聰明，可以靠其他方法來彌補人際處理能力的短處，所以也活過這麼多年。但也因為這樣，造成他的人際處理能力更為弱化。這也就是為什麼他用了許多有「創意」的方式來處理溝通問題的原因(黑函、剪耳朵、站崗)。

Read More

到葉門釣鮭魚、鬱林湖失蹤紀事、Hyperion

這是我最近讀的三本小說。三本小說之間沒有直接的關聯，甚至可以說毫不相干，但在某種程度上又有微妙的相似之處。 「到葉門釣鮭魚」的故事主軸是英國政府的一個企圖在沙漠國家葉門中培育鮭魚的計畫。該書的賣點在於用會議記錄、公文、電子郵件、日記等等來構成內容。藉由這些在日常生活中出現應用文體，刻劃出背後的事件。比較文字與真實世界之間的異同，產生出趣味。比方同一場談判，從甲的日記是自己掌握全局，但從乙對上級的報告來說，又完全是另一回事。而看嚴肅的公文，其實是用來包裝「在沙漠中釣鮭魚」這樣瘋狂的計畫。而這個釣鮭魚的計畫再怎麼瘋狂，其荒謬程度也只是背後的利益分配與權謀鬥爭的冰山一角罷了。 但全書使用日記、電子郵件等等還是有局限性的。因為很多事情是不會被文字紀錄下來的。因此，作者只好讓書中的角色寫一些非常詳實的心情日記，寫一些寄不出去的信來補充人物的內心世界。這樣其實是有點遺憾的，因為難免會降低了書中偽文件的真實感。 不過使用文件紀錄這種文體來構成小說不是新鮮事。比方「鬱林湖失蹤紀事」也有約一半的篇幅是用偵訊調查報告的形式構成的。和「釣鮭魚」不同，「鬱林湖」用這種寫法的目的是要凸顯事實的不確定性。「鬱林湖」也描寫了一些政治生態，而它的主軸則是真實與謊言的界線。所以主角的魔術師與政客雙重身份也順理成章了。當世界充斥著巨大謊言，一些小謊話真的有那麼邪惡嗎？主角一生與謊言糾纏，最後終於逃脫了，從這個充滿謊言的世界中失蹤。但這個逃脫本身，似乎也是個謊言。 Hyperion 是科幻小說，雖然不是用應用文體構成的，但是書中以六個中篇故事組成，所以同樣的，可以從不同的觀點來說故事。 這六篇是六個聖徒為了打發旅程的無聊，講述各自的故事。可以拆開來看，每篇都自成一格，作者講故事講得很動人。但神奇的是六篇又相輔相成，合起來看後，就像把許多瞎子摸的象又組合在一起了。這六篇內容包含不同的科幻類型，神秘不可解的異星種族、高科技星際戰爭、地球末日詩篇、時光倒流的奇特科幻病、cyberpunk 類型的未來偵探、星際旅程有關的愛情浪漫傳奇。作者並不是在炫技，至少不完全是炫技。與「六個故事」「六個觀點」這個調性相呼應的，作者是要用不同面向來描述一個世界。有許多不同的科幻類型來描述未來，有些黑暗有些光明，有烏托邦有地獄，有些著重於網路虛擬世界，有些則著重於星際旅行。但未來到底是哪一種科幻類型所描述的？ Hyperion 提出一個浪漫的答案：「都是，看你從什麼角度去看」同一個世界中，有電腦駭客和虛擬世界，也有未來的星際戰士、遨遊星際的商旅。對有些人來說，生活是地獄，對另一些人來說，可能是天堂。 武俠小說的是世界其實也有點類似，電影臥虎藏龍在某個程度上，也是用類似的方法帶我們進入一個武俠世界。你可以從保鑣武夫的角度來看草莽的江湖，可以看到煉氣化神、鍊神還虛的修道劍客江湖，可以看到塞外盜賊刀的的江湖，可以看到朝廷官府的江湖。 在「釣鮭魚」裡面來說，科學家眼中毫無價值得計畫，也許在政治外交上有實質的意義。從商人眼裡來看，這些也許都無關，現實收益才是唯一需要考慮的。「鬱林湖」中，客觀的現實事實有時並不存在，有的只是個人眼中不同的真實。 不約而同的，三本小說都沒有非常明確的結局。「釣鮭魚」的結局還算明確，不過太跳脫而突兀，有種不真實的感覺。曾經看似極為關鍵的計畫與人物，到頭來其實也可有可無。「鬱林湖」留下一個撲朔迷離的結局，讓人自行解讀。Hyperion 還有續集，不過以第一本單獨來看，故事動人就好，結局到底如何，誰在乎呢？

Read More

Project Euler 198 題

Project Euler 的 198 題。簡單的說，要算出分母在 10^8 以內，大小在 0~0.01 之間的「混淆數」總共有幾個 。而所謂的混淆數 x，是指如果對於某個 m，分母不超過 m 的「最近似 x 的分數」不只一個時，就稱 x 為混淆數。比方對於 x=9/40 來說，m=6 時， 1/5 和 1/4 都是分母不超過 6 最近似 x 的分數。
這個題目其實如果沒有任何基礎知識的話，還不太容易，所以解出的人不多。但站在一些基礎知識之上， 10^8 這種數量級是很容易用程式來秒殺的。據說 Knuth 的 The Art of Computer Programming 裡面就有提供相關的演算法。
不過使用 Haskell，可以很直接的用遞迴解出：

f a b l m | a*b>l || (a==1 && b > m)  = 0
         | otherwise = (f a c l m)+1+(f c b l m) where c=a+b
main = putStrLn $ show result
      where result= (f 1 100 l2 m) + 49+l2-m
      l = 10^8
      l2 = l `div` 2
      m = floor (sqrt (fromIntegral l2)

七行就簡單解決了。如果你知道背後的數學，上面的程式碼其實是很直接的。但用 Python 解就麻煩了，因為上面這個遞迴解超出 Python 的遞迴深度。可以用迴圈來取代遞迴，如下面的演算法：

def p198(M=10**8, z=100, cnt=0):
 M2=M/2
 a=m=int(M2**0.5)
 stack=range(z,m)
 while stack:
     b=stack[-1]
     if a*b>M2:
         a=stack.pop()
     else:
         cnt+=1
         stack.append(a+b)
 return cnt+M2-z/2

(程式碼我從 Project Euler 直接貼過來，排版有點亂掉）
這個演算法是我參考別人的解答後寫出的，配上 psyco 後，其實還挺巧妙也挺快的，但不太容易讀懂，要跟蹤一下堆疊是怎麼跑的。
但有些簡單的工作， Haskell 寫起來又很累贅。比方有一個整數 n，想找出它的根號的整數部份，如後印出來，在 python 來說再簡單不過的

print int(x**0.5).

Haskell 的作法要先將整數轉成浮點數，開根號，然後再用 floor 轉成整數，最後再用 show 轉成字串才能印出。所以是

putStrLn.show $ (floor . sqrt) (fromIntegral n)

如果有許多浮點數與整數，那更複雜一點的運算就要轉來轉去。雖說這樣可以強迫正確的設計風格，但有時只是簡單的小計算，這樣也未免太累了。
果然 Haskell 能將複雜工作簡單化，簡單工作複雜化。

Read More

程式設計語錄

圖片來源: wikipedia

(選自 DevTopics 整理的語錄)
(用來讓自己看起有學問的)

• "Simplicity, carried to the extreme, becomes elegance."  簡單到極致即為優雅。
  – Jon Franklin
• "The best way to predict the future is to implement it."  預測未來的最佳方式就是實做它。
  – David Heinemeier Hansson
• "Make everything as simple as possible, but not simpler."   儘量讓事情簡化，但別太簡化。
  – Albert Einstein
• "The difference between theory and practice is that in theory, there is no difference between theory and practice."  理論和實務的差別在於，理論上，理論和實務沒有分別。
  – Richard Moore
• "The greatest enemy of knowledge is not ignorance, it is the illusion of knowledge."  知識的的敵人不是無知，而是知識的假象。
  – Stephen Hawking
• "密碼就像內褲一樣： 不要讓別人看到，要常常更換，而且，別和陌生人共用."
  – Chris Pirillo
• "Computers are like bikinis. They save people a lot of guesswork." 電腦就像比基尼，幫我們省下許多猜測的麻煩。
  (Sam Ewing)
• "Come to think of it, there are already a million monkeys on a million typewriters, and Usenet is nothing like Shakespeare."  其實想想，現在已經有上百萬隻猴子坐在上百萬台打字機前了，但網路論壇一點也不像莎士比亞。(現在可用來描寫部落格)
  (Blair Houghton)
• "Hardware: The parts of a computer system that can be kicked." 
  (Jeff Pesis)
• "Web Services are like teenage sex. Everyone is talking about doing it, and those who are actually doing it are doing it badly." (網路服務) 
  – Michelle Bustamante
• "The best way to get accurate information on Usenet is to post something wrong and wait for corrections."
  – Matthew Austern

程式師的幽默

• 問：為什麼程式設計師是分不清萬聖節和聖誕節？
  答：因為 Oct 31 = Dec 25.
• 一個男人在吸煙，他的女朋友很生氣的說："Can't you see the warning on the cigarette pack? Smoking is hazardous to your health!" 男人回答說： "I am a programmer. We don't worry about warnings; we only worry about errors."
  
• "I think Microsoft named .Net so it wouldn't show up in a Unix directory listing."
  (Oktal)
• "C++ : Where friends have access to your private members."
  (Gavin Russell Baker)
• "Computers are getting smarter all the time. Scientists tell us that soon they will be able to talk to us. (And by 'they', I mean 'computers'. I doubt scientists will ever be able to talk to us.)"
  (Dave Barry)
• "I've noticed lately that the paranoid fear of computers becoming intelligent and taking over the world has almost entirely disappeared from the common culture. Near as I can tell, this coincides with the release of MS-DOS."
  (Larry DeLuca)
• "It was a joke, okay? If we thought it would actually be used, we wouldn't have written it!"
  – Mark Andreesen, 談 HTML 的 BLINK 標籤

程式師與使用者

• The three most dangerous things in the world are a programmer with a soldering iron, a hardware engineer with a software patch, and a user with an idea. - The Wizardry Compiled by Rick Cook
• "If you think your users are idiots, only idiots will use it."
  – Linus Torvalds
• "From a programmer's point of view, the user is a peripheral that types when you issue a read request."
  – P. Williams
• "Computers are good at following instructions, but not at reading your mind."
  – Donald Knuth
• "There is only one problem with common sense; it's not very common."
  – Milt Bryce
• "Your most unhappy customers are your greatest source of learning."
  – Bill Gates
• "There are only two industries that refer to their customers as 'users'."(販毒業與軟體業)
  (Edward Tufte)
• 
  "Any fool can use a computer. Many do."
  (Ted Nelson)
• "That's the thing about people who think they hate computers. What they really hate is lousy programmers."
  (Larry Niven)
• "Just remember: you're not a 'dummy,' no matter what those computer books claim. The real dummies are the people who–though technically expert–couldn't design hardware and software that's usable by normal consumers if their lives depended upon it."
  (Walter Mossberg)
• "Software suppliers are trying to make their software packages more 'user-friendly'… Their best approach so far has been to take all the old brochures and stamp the words 'user-friendly' on the cover."
  (Bill Gates)
• "There's an old story about the person who wished his computer were as easy to use as his telephone. That wish has come true, since I no longer know how to use my telephone."
  (Bjarne Stroustrup)

程式設計

• (程式註解)"Commenting your code is like cleaning your bathroom — you never want to do it, but it really does create a more pleasant experience for you and your guests."
  – Ryan Campbell
• "Low-level programming is good for the programmer's soul."
  – John Carmack
• "A program is never less than 90% complete, and never more than 95% complete."
  – Terry Baker
• "Manually managing blocks of memory in C is like juggling bars of soap in a prison shower: It's all fun and games until you forget about one of them."
  – anonymous Usenet use"
• "Standards are always out of date. That's what makes them standards."
  – Alan Bennett
• "There's no obfuscated Perl contest because it's pointless."
  – Jeff Polk
• "Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems."
  – Jamie Zawinski
• "You can't have great software without a great team, and most software teams behave like dysfunctional families."
  (Jim McCarthy)
• "There are only two kinds of programming languages: those people always bitch about and those nobody uses."
  (Bjarne Stroustrup)

Read More

zhpy 的另類用法

配合上 zhpy ，我們可以寫出下面這樣的 python 程式:

# encoding: zhpy_utf8
from math import *
from operator import *
print Σ(range(100))
print sin(π/4) ≠ √(2)/2
print ㏒(100), ㏑(e)
print 5 × 30 ÷ 2 ≦ tan(√(5)*π/4)
Π=λ f:reduce(mul, f, 1)
print Π(range(1,6))
print set([1, 2, 3, 4, 5]) ∩ set([1, 3, 5, 7, 9])

(第一行是 MagicCodec 語法，普通的 zhpy 請去掉第一行)
不管實不實用，至少增加了一點可讀性。既然是λ，為什麼要寫成 lambda?
以上的程式碼只需要下面的 zhpy .ini 檔案（可以叫做 math.ini，放在執行的目錄下)

[math]
λ=lambda
π=pi
Σ=sum
≠=!=
÷=/
×=*
㏒=log10
㏑=log
√=sqrt
≧=>=
≦=<= ∩=& ∪=l

for 和 in 可以換成相對應的符號, set 的 <, <= 也可以換成 set 符號。
Haskell 的 ide Lesksah 就能做到這件事情。 如果能夠把 lyx 修改成 python, haskell 或者其他程式語言的編輯器，應該也挺有趣的。
相關的東西是 TeXmacs 的 python plugin tmPython，

Read More

根號 2 到兩百萬位的挑戰

Sphere Online Judge 有一個題目是在 20 秒內計算根號 2，越多位越好（上限是兩百萬位）。有不少人能達到這個目標，但都是使用 C 或者 C++。我想試試看 python 這種以速度慢聞名的語言，能達到什麼程度。試驗的結果是十五萬位。雖然不太多，但是也擠進了排行榜裡面前二十名。而目前 python 語言的第二名還不到五萬位。

我的程式沒有用什麼特殊的技巧。事實上， python 的乘法不算太慢，現在 python 已經使用了 Karatsuba 演算法來做乘法，在一萬位以內的效能都還不錯，算到十幾萬位也都還能接受。但再上去就有點吃力了。而最主要的瓶頸在於 long 到 str 的轉換速度。光是將一個兩百萬位的數字轉成字串，就會花上非常久的時間。

改用 gmpy 會快很多，應該能夠算到百萬位以上，雖然我沒試過，但 spoj 應該不能使用 gmpy。

所以，也許應該直接寫個簡單的 FFT 乘法模組。事實上，我找到了一個叫做 DecInt 的 Pure python 套件，裡面實現了幾種快速的乘法及除法演算法，而且因為基本上資料是用十進位表示，數字轉字串非常快。他的乘法也許不是最快的，但是如果要我自己寫，大概也會是類似的東西，所以相當適合先拿來測試一下效能。

果然，大致上可以讓算十五萬位的速度快兩三倍。如果自己再強化改進，也許能再快個兩倍，但估計最多只能勉強上到百萬位，而且需要相當長時間的測試和實驗，所以我放棄。

於是我改用 Haskell 來寫。我沒有寫過 Haskell 程式（現在也還不會），而且連 Tutorial 都沒有讀完，就抓了 ghc 用最笨的方式把程式寫出來了。我只需要知道怎麼用 = 來定義函數能寫了。結果算到了一百六十萬位，足足比 python 多了十倍(Haskell 現在第二名約一百二十萬位)。如果再多加微調，或者我如果對 Haskell 再多熟悉一點，也許還能多個不少位，甚至到兩百萬位也不無可能。

其實我只要算到五十萬位，然後再用個 4-way Toom Cook 就行了，而算到四十萬位不用三秒。不過問題是，就像前面說得，其實我還不會寫 Haskell。

演算法基本上和 python 版本的相同，不過改以 recursive 的寫法。 Python 雖然完全支援 recursive 函數，但是 Python 的函數呼叫很慢，又限制層數（內定1000，最多 5000)，所以，其實有點降低我把東西寫成遞迴的誘因。反之，Haskell 是 functional language，所以其實是獎勵這種寫法。

而 Haskell 之所以算得這麼快，其實有點勝之不武，因為 ghc 內建用 gmp 來做計算。

讓人疑惑的反而是，為什麼 python 不用 gmp 來做計算？

當演算法夠好，時間夠長， python 的速度劣勢就能被彌補，但 online judge 的時間限制都不太長，二十秒已經算是超級長的了，但這二十秒差不多只等於我電腦上的五、六秒，典型的時間限制是兩秒。用 pure python 實現很好的乘法演算法，也要到上萬位才能擊敗 python 內建的長整數乘法。所以，現在想用純 python（而且程式碼在4kb以內）上兩百萬位，還挺困難的，不過，也許還是有人能辦到也說不定。

(Update 2008-06-11) Haskell 達成兩百萬位。當然我 Haskell 的能力比兩天前進步一點，但主要還是用笨方法寫 recursive function。程式碼總共 11 行，而且其中有 3 行是用來定義一個函數，來達到 python 的 zfill 功能。

Read More

Euler 計畫和其他

前一陣註冊了 Project Euler，然後玩了一下裡面的題目。
Project Euler 蒐集了一系列的挑戰問題，這些問題的答案都是一個數字或者一組數字。每當你破解一個問題後，你就能與其他同樣破解這個問題的人，討論答案與心得。通常解決這問題需要一點程式設計技巧和數學知識。

網站裡面也會對於不同國家或者程式語言的解題者做統計和排名。比方說這是台灣的統計，而這是 Python 語言的統計。和「點點點」相比，台灣的表現很爛。
一般所謂的 online judge 系統其實很多，ACM 風格的 online judge 是主流。 UVa online judge 是其中的代表。其他還有如ZeroJudge。
和 Project Euler 不同， Project Euler 上傳的是答案，而這類 online judge 要你上傳的是「程式」。所以有限定使用的程式語言。標準的語言是 C,C++,Java。雖然我也寫 C++和C，但我還是比較喜歡能自由選擇工具。這點到不是根本性的問題，像是 Sphere Online Judge 就能讓你使用許多不同的程式語言，包含 perl, ruby, python。
另外一個不同點是時間限制，雖然 Project Euler 也有所謂的「一分鐘法則」，就是程式應該要能在一分鐘跑完，但這不是硬性規定，真正的裁判是你自己。事實上，如果你喜歡（而且可以的話），你甚至可以 用google 找答案。真正的裁判是你自己。我喜歡這種風格。
一般的 online judge，有些題目有時間限制。就比賽而言，這提供競賽公平性的基準。但這個時間限制沒有「理論上的定義」，端看裁判主機端執行的時間而定。這缺乏了一點美感。
另外就是題目取向，Project Euler 的題目有時會需要一點數學知識，而一般程式競賽有時則是要一點演算法上的知識。而 Project Euler 容許的執行時間往往比較長一點。
總之，雖然都是程式挑戰題，但是風格和取向各有不同。
另外一種類型是 Code Golf，著重在用最短短的程式碼達成指定的功能，就像是打高爾夫一樣，你想要用最少的桿數完成比賽。雖然也是程式解題競賽，但又另有一番風格。
當然，寫程式的目的在於寫出「真正有用」的東西，而不是解答這些問題來炫耀自己有多強。但是，不管是哪一種風格的程式解題競賽，在你解題的過程，都能增進自己的程式設計能力。比方 Code Golf 裡面，有些解答是不可思議的短，在你追求這個目標的同時，才發現原來有些語言特性是自己之前忽略的，某種問題原來還有這種寫法。
(對 Project Euler 有興趣的朋友，可能也會對 IBM 的 Ponder This 有興趣。)

Read More