2011/10/09

在itunes商店上買非台灣的app

在itunes 上要下載免費的pptv,可是itunes會從你的信用卡號碼判斷出你的region是在台灣,而不是在香港,所以被禁止下載。單純從itunes上切換國別,還是會被信用卡號碼判別出而被禁止。

解決方法:
  1. 要先用gmail申請自己的香港版分身的email帳號,比如說 mikimotoh.HK@gmail.com。
  2. 登出itunes,找pptv,不要用舊帳戶登入,改做新的Apple ID
  3. 填入香港版的email之後,在匯款資訊選None。

2011/09/04

鄉下地方不見得食物便宜

我中午去秀山國小後面新開的「樂壽司」買鰻魚飯,250元的價格,在外頭等了十五分鐘後拿到,我大失所望「怎麼250元只有扁扁一盒,沒有附味噌湯?」

主菜是三片蒲燒鰻,新鮮的青菜很少,細細的幾根蘆筍,其他大部份是醃漬類的菜,比如甜甜的黑豆。還有一個很小份量的沙拉蝦。

250元在東區216巷的宮川,已經可以吃到很豪華的定食了 ,包括:小菜、主食、副主食、茶碗蒸、沙拉、鮭魚味噌湯、甜點。但為何在店面租金比東區更為低廉的台北縣,反倒賣得很窮酸?

我想合理的解釋為,在主婦、學生居多的秀山一帶,大部份人想出的午餐錢大多是在100元以內,所以說60元的便當會比東區的便當更有競爭力,但很少人會想為午餐出個250元。
在上班族、觀光客居多的東區,午餐出的錢從100到300多都有,250元這價位的競爭激烈,多樣化的結果是使得各個價位都能產出CP值的餐點。像樂壽司這般以高檔壽司為主的在延吉街一帶也有,而像宮川以「俗個大碗」這種利基來競爭的也有。

2011/08/14

dystopia of medical hegemony 醫療霸權的反烏托邦

前不久香煙中的健康捐調漲,我曾聽過一些癮君子忿忿不平地說「這個政府所有一切都是為健康,他最終變成一個以健康之名的家父長制」

其實不只是香煙要課徵健保捐。未來可能連不健康的飲食習慣也要課徵健康捐。炸雞薯條因為會讓心血管疾病機率增加,所以要加收健保捐。汽水等含糖飲料因為讓人變肥胖、糖尿病,所以要增收健保捐。可能連不健康的行為也要課徵健康捐,打手機會增加腦瘤風險,久坐辦公室不運動會心血管疾病,熬夜會中風,這些行為都要課徵健康捐。

我們為了要節省健保開支,就從十大死因中的前幾名榜首,癌症、心血管疾病、糖尿病等來下手。不斷尋找會使這幾樣疾病機率增加的所有可能行為、可能因子。 到最後我們會不會變得失去選擇飲食的自由、行為的自由?

健保本身的目的不只是讓人變健康,還延長人的平均壽命。而平均壽命增加,所需的醫療開支就變更多。醫療開支增加,不僅要尋找新的行為來課徵健康捐,還要調漲收入所得中的健保費。如果人類平均壽命沒有極限,可以無限制增長,現在的平均壽命是80歲,60年後變120歲,那麼,會不會超過一個臨界值,我們的社會體制根本無法支撐,最終崩潰?而在崩潰的前一刻,這個所有一切飲食與行為,都訴求健康的世界,會是長什麼樣?


sex worker issues 性交易該不該合法化?

當討論到性交易合法化時,最常見的幾大反對理由是:
  • 物化女性
  • 性病傳播
  • 雛妓
  • 使人為奴
  • 人口販運
  • 黑道從中牟利
「性」這個名詞,給了我們太多迷惑,當我們一看到這字眼時,很難不被我們文化中的道德觀、價值觀所影響。

當同一件行為,使用不同的名詞去稱呼時,會使我們拋棄隱晦的既有價值觀、刻板印象,來重新看事情。如果把性交易換成「前列腺保養」,重新設計這議題,改問「『前列腺保養』這服務產業,該不該合法化?」這時你至少會重新思考,不帶既有的有色眼光來看事情。

 把以上這六大反對理由,重新包裝,重新發問:

  • 『前列腺保養』這服務產業,任用女性護理師,是物化女性嗎?
  • 『前列腺保養』這服務產業,會傳播性病嗎?
  • 『前列腺保養』這服務產業,會傾向任用童工嗎?
  • 『前列腺保養』這服務產業,會刻苛護理師,抽取他們大部份薪水,並禁止他們離職嗎?
  • 『前列腺保養』這服務產業,會勾結人蛇集團從大陸、東南亞運外勞來工作嗎?
  • 『前列腺保養』這服務產業,會給黑道帶來暴利嗎?

從第一題來看的話,這無庸置疑的是否定。如果只要用到女性護理師就是物化女性。那在醫院中,我們找女性護理師幫癱瘓的爺爺包尿布、洗澡,也是物化女性了。

第二題,會不會傳播性病,端看護理師有沒有做好防護措施。有戴好保險套、戴好口交膜,傳播性病的可能性幾乎為零。如果連這也要擔憂,那護士應該拒絕照料AIDS的病人、B型肝炎的病人。

第三題,會否任用童工的爭議,是由勞基法、勞委會幫我們把關。在現實世界,有些血汗醫院以「實習生」、「建教合作」的名義,苛刻對待未成年的護士。他們的付出的勞力跟正職護士相當,但只因他們是「實習生」,拿到的待遇卻不如正職。如果我們連這種「假實習,真童工」的問題都視而不見,那為何只在意『前列腺保養』產業中童工的問題?

 第四題,禁止離職的問題,也是要由勞基法、勞委會來把關。現實世界中,有許多合法公司在員工受雇前,要求他們簽訂綁約條款。以公司的立場來看,員工太頻繁離職,會造成公司遞補人力不足的問題,造成公司的損失,所以要以綁約防止員工頻繁離職。以員工的立場來看,綁約限制了他跳槽的機會。站在仲裁者、勞委會的立場,只要這綁約條款合乎平等互惠,不會讓員工越做越窮,都是可以接受。比如說,綁約一年,員工提前離職,就失去了加薪、領獎金的機會,這種契約看來還合理。若契約是,綁約四年,提前離職要員工倒賠自己六個月的薪水給公司。這樣的合約就絕對不平等互惠。所以,並不是說有綁約,就一定是逼員工為奴,而是程度上的問題。


第五題,人口販運主要令人詬病的問題是,外勞在來台工作前,要先支付仲介公司一筆的仲介費,又簽訂一紙契約,說是要欠仲介商的巨額仲介費的債。當他們來台工作,又從他們每月月薪扣除一大部份,要是要還仲介費的債。抵押他們的證件,防止他們逃亡。利用他們人生地不熟的劣勢,把他們關在擁擠髒亂的宿舍,一天工作十六小時。人口販運的問題,不只是政府部門要嚴格查緝人力仲介公司,與黑心仲介商勾結的雇主,也要嚴格檢視。

第六題,黑道會從這行業牟利嗎? 許多非服務產業,如電子製造業公司,也有黑道在投資,但政府會因為只要這公司的股東中有黑道,就勒令這公司停業嗎?股東犯罪的行為,怎麼能夠跟公司牽扯在一起?公司沒有強制力阻止股東犯罪,也沒有能力阻止。

Immanuel Kant on sex workers 康德如何看性交易

從康德的自由主義觀點來看,人不能被當成工具使用,道德是要以人為對象來服務人的。不把人當對象,把人當成工具、手段,就是不合乎道德。性交易,是嫖客把妓女當成自己的洩慾的工具,所以不合乎道德。就算說這是兩情相悅,兩人都已成年,兩人都站在同等的立足點,簽訂這項契約。他們同意這契約,也不代表這契約是合於道德的。

我自問「那康德會認為按摩師傅幫我我按摩,是道德的嗎?」我不去使用較省錢、但按摩手藝差的投幣式按摩座椅,而去找較昂貴、但手藝好的真人來按摩,我不是把按摩師傅給物化成機器了嗎?

從康德的自由觀來看,幾乎所有的服務都會變成不道德,甚至連我花錢找鋼琴師來為我演奏音樂,而不去聽唱片,也是把鋼琴師物化,把鋼琴師貶低成了音響機器。

「正義分配」不能依據「道義應得」

觀看「正義,一場思辨之旅」書中John Rawls講的公平正義哲學,最令人費解的,就是「正義分配」不能依據「道義應得」,乍看之下,我納悶「這不是在懲罰努力的人?」

在這個「財富至上」的自由市場的社會,訴求的是形式上的平等,每個人享有相同的權利,大家在同樣的遊戲規則下競爭。但不可避免,出身的貴賤會影響到人的發展。出身在社經階級高的人,成就大多超過社經階級低的人。為了彌補這個出身的不公,我們把「才能至上」的機制加進去。有人雖出身貧困,但我們給予他與富人相同的教育資源、發展機會,讓他的才能不會被埋沒。

但是,這「才能至上」的世界還是有所不公,出身的天賦純然憑運氣得來的,並不是我們任意選擇的, 或是經過努力得來。麥可喬丹雖然籃球打得最好,但不可否認的是,這有部份是靠他的天賦。如果單憑努力而沒天賦,我不相信他籃球還會打得像現在一樣好。由於天賦是憑運氣分配的,運氣成份應給平均分攤。我們依這道理,把喬丹的收入中扣除一部份,分配給籃球差的人。從道義應得(Moral Desert)來看,我們依據進場觀眾的投票,而分給他多少薪水。但從John Rawls的正義分配,我們從麥可喬丹的所得中扣除一部份,去彌補給其他籃球打得差的人。道義應得的分配,並不等同於正義分配的所得。

「這不是懲罰努力的人?」 我自問「而且,如果其他跟他一樣努力,但天賦沒麥可喬丹一樣好的人,他可以去選擇踢足球、進演藝圈,或是進入商界發展」「依據自由市場的原則,籃球天賦差的人不會去他表現差的競技場,他會自動去符合他天賦的競技場」

我試著回答:我們的世界,並非對各種天賦都有適合的發揮場域。再來,有些天賦雖有發揮場域,但所得收入非常低,無法跟NBA球員的所得相匹配。他們的所得低,並非他們不夠努力,而是運氣不佳。他正好生在一個他的天賦沒市場的國家;或是,他正好生在一個他的天賦沒市場的時代。所以,不僅天賦的高低的是須要運氣的,適當的天賦出現在適當的社會也須要運氣。而我們把麥可喬丹的一部份所得扣除,就是把這運氣成份平均分攤。

我又問「依據John Rawls的正義分配,要把麥可喬丹的所得扣除多少?難道要扣到跟別人一樣均貧?而扣成均貧制後,那喬丹會一氣之下不打籃球,而我們沒有精彩的籃球可看了」

我自答:重新分配的多寡 ,並非是齊頭式的平等,而是足以激勵底層階級向上發展的量。並非說懶惰不做訓練的人,可以平白無故的能拿到跟喬丹一樣多的錢,也並非說努力訓練但天賦不如喬丹,一毛錢也拿不到,讓他從此對籃球放棄。

我在上篇文章有提過「遊戲的平衡性」,重新分配是彌補純屬運氣的成份,並且讓這世界的遊戲平衡性更佳。運氣最衰的人,出身貧窮家庭、才智中下,靠著社會「遊戲平衡性」設計,讓他並不會因此放棄這人生遊戲,自暴自棄,跑去自殺。而同樣出身貧窮、但才智中上的人,社會的遊戲平衡性設計得恰到好處,不會打消他努力奮鬥的念頭。經過正義分配後他所剩的財富所得,還是有足夠的誘因激勵他努力奮鬥。John Rawls 正義分配的安排,要關懷到我們忽視天賦不如人,或是天賦在這時代正好沒市場的人。

關於John Rawls 的「無知之幕」的想法

John Rawls 的「無知之幕」思想實驗是,如果我們對這個世界,一無所知,這個世界是被「無知之幕」所遮蔽,那我們會怎麼設計這個世界?多數的人一定會選擇公平正義的社會,因為他不知道當這布幕一打開時,他是被抽籤到了窮困的家庭,還是富貴的家庭。多數人一定會想,如果我設計了貧富不均的社會,而我又運氣差,被抽籤到了窮人,那我的這一生會變得很悲慘,不管我做了多少努力都潦倒而死。多數人會想,我會設計一個讓出身的高低,無法決定其最終宿命的社會。也許一開始每個人的出身都有所差異,但最終都可靠個人的努力來彌補。


但是,我們怎麼保證多數人在「無知之幕」之後,都會選擇一個公平正義的社會?說不定,大部份的人,都喜歡貧富不均的社會。風險雖大,卻很刺激。運氣歹命的人雖然過得很悲慘,但運氣好的卻非常爽,可以玩私人飛機、私人遊艇,還可以把一個國家買下來,想幹什麼就幹什麼,非常刺激。


如果我們把人生看成「快打旋風」這遊戲,我們把「無知之幕」,當成遊戲的角色平衡設計。我們問,若你是遊戲設計者,你會把角色設計成平衡度高,還是平衡度低?考慮到遊戲要賣錢,要吸引到更多的玩家玩,平衡度高比較好,還是平衡度低比較好?

如果角色設計的平衡度低,比如說龍的攻擊力特別強、防禦力高、速度敏捷。只要選龍的話,遊戲贏的機率就會高達90%以上。這遊戲的勝負就演變成,不是靠格鬥技術的高低來判定,而是一開始選角時,誰先搶坐在player1的座位誰就贏了(遊戲選角時,player1預設是擺在龍的位置)。這遊戲就變成搶位子比賽,不再是格鬥比賽了。當格鬥比賽一開始時,選到龍的人只要一直不斷按攻擊鍵就會贏了,再也沒有什麼意想不到的變化。

不論是從以上的思想實驗,還是實際的電玩遊戲市場數據來看,我們發現,玩家大多會偏好平衡度高的遊戲。如此,我們怎麼能說,在人生的「遊戲」之中,多數人都喜愛角色設計不平衡的世界呢?

有一些Milton Friedman信徒批評說,John Rawls 的公平正義社會,是一種共產主義社會,要把每個人都變得一模一樣,每個人都再也沒有美醜、高低、強弱、富貧之分,要讓這世界變得很無趣。以「快打旋風」這遊戲來比喻的話,就是再也沒有其他七個角色可選,每個人都一樣是用龍來對戰。雖然說這遊戲真的是靠格鬥技術高低來決定勝負,但變得很無趣。

我認為,John Rawls 的無知之幕,所訴求的正義公平,就像遊戲平衡度一樣,並不是要求我們每個人都變得同一個模子刻出來的。並不是說有人天生跑得快,就用鐵砂袋綁在他的腳上,讓他跑得跟你我一樣慢;並不是說有人出生在富豪家裡,就要把他的財產均分,跟你我一樣窮。而是,要讓我們這世界就像遊戲一樣「角色平衡」。雖然有的人出生是在處於劣勢的位置,但我們能設計出社會機制,比如「Affirmative Action 積極平權措施」,使他能在其他方面取得優勢。

John Rawls的「無知之幕」並非說在幕後的人沒有智商、沒有知識。而是說這遊戲開始前,每個人對於要被抽籤到的角色都一無所知。不論如何,我們這些在幕後的人,一定都是帶有我們已經被灌輸的文化觀來設計這遊戲。由於我們的文化價值觀,是讚賞努力奮鬥的人,貶抑不勞而獲的人。那我們一定要把這世界的遊戲規則,設計成讓花最多心血在遊戲上努力的人,得到最高的分數。

2011/06/24

宏達電一日遊

下午二點,在寶橋路的TOP大樓十樓報到,HR小姐把我帶到一個小房間,房間內共六個人。
我是先戴著耳機,在NOTEBOOK前接受英文TOEIC測驗。在我答題到最後的閱讀測驗前,AUTHORWARE.EXE當掉,我之前的做答都報銷了。HR之後把我帶到另一個小房間,是用聽錄音帶的方式進行英文TOEIC試驗。

結束英文試驗後,HR小姐又把我帶回那擠了六人的房間,做C/C++/JAVA的筆試,我沒做什麼驗算,憑直覺衝,早早就交卷了。

HR把我帶到一個更小,只能容納兩人的房間。先是來了GA TEAM的兩位組長給我面試。他們對我碩士唸了三年很感興趣。他們看我之前做的九年資歷,有真才實料,但他們一直強調他們要苦幹實幹的人,而且沒有彈性上下班,週末要來公司加班,一週基本工時60小時起跳,而且前兩年不能領分紅股票,薪水會比我現在還更低。

後來又來一位更高層的人,又問我那微軟萬年考古題ReverseString(),問說API 介面要怎麼設計,要怎麼實作。還有問我過去做Windows Mobile的一些細節。還有非技術性的問題,如你一生中最高興的一件事,最挫折的一件事。他一邊看我的資歷,一邊說「solid、solid」。他很意外,我的薪水比這HTC的徵才還高,怎麼會過來面試。我說,我是碰到一個head hunter,介紹我來這邊,而我從來沒有來HTC參觀過,所以過來看看。

參觀完後的心得是:
第一、台灣的科技公司,股價與員工幸福度成反比。
第二、HTC 辦公室隔間弄的很窄小,環境很不舒服。
第三、獵人頭公司也有出鎚的時候,要捕小魚結果捕到大白鯊。

2011/05/16

[programming]Shunting Yard Algorithm

Shunting Yard (調車場)演算法,是可以把infix(算符中綴)表示法轉換成reverse polish(算符後綴)表示法。比如
這個中綴 (9*8)+(6/3)
變成
後綴 9 8 * 6 3 / +
反過來說,有沒有演算法是可以把 RPN (後綴) 轉成 Infix (中綴) 呢?

[programming]RedBlackTree

紅黑樹兩個條件
  1. 兩個紅子不能互為親子
  2. 由根(root)至每個葉(leaf)的路徑(path)上,黑子數相同



如果將[1,2,...15]共15個key插入紅黑樹,最後紅黑樹的外形,不會像是完美的(optimal)二元樹(Binary Search Tree)一樣是個對稱的金字塔。紅黑樹會變得左邊高度2,右邊高度5。



看起來好像不太好,你很怕[16.17.18]等key加上去,樹右方會無限制地變長。但實際上插入[16,17]後,樹右方仍只有5。




再加入[18]後,紅黑樹就開始左旋,讓左方分攤一節高度。右邊高度還是只有5。



因為有一、二的條件限制,樹左邊是3黑子,那樹右邊至多是[黑紅黑紅黑紅],如果再繼續加上去的話,樹就會左旋,讓樹左邊分攤重量。

因此,紅黑樹的最長一邊(此例中為右邊)最多不會超過2⌈logN⌉,紅黑樹的search複雜度是在O(logN)。

紅黑樹跟一般的二元樹有何不同?
  • 由於條件二,紅黑樹會算每一側的黑子數,所以不會過於偏斜
紅黑樹跟力求完美平衡的二元樹又有何不同?
  • 紅黑樹允許紅子參雜在其中一側,而且只算黑子數,所以不會為了力平衡,使得旋轉次數太多。又由於條件一,避免兩個紅子互為親子,所以不會發生[黑紅紅紅紅...紅]的情況。
紅黑樹是平衡樹與一般二元樹的折衷之作,

2011/05/04

[iPhone]iPhone耳機壞了

今天去健身中心一邊跑步一邊用iPhone聽音樂,汗水一直流沒時間擦汗。

回家坐公車想要用iPhone聽音樂時,我沒碰iPhone,但它竟然會自動跳到語音控制,亂撥電話給其他人,如果我把耳機拔掉後又正常了。

有可能是汗水弄濕,也有可能是收納線材時,捲上魚骨棒時捲壞的。

我現在想要買新耳機,可是怕原廠耳機會否因為被汗水淋濕而弄壞。有比較防水,但又有線控與麥克風功能的iPhone耳機嗎?

另一點是健身中心的跑步機會溢出靜電,跑步時如果不觸碰跑步機的金屬部份,靜電就會經由耳機傳到耳朵,耳朵一直被電。我想要跑步時把iPhone掛在手臂上,請問那種配件叫什麼?

2011/05/02

[Puzzle]人過大佛寺*4=寺佛大過人,猜數字

Palindrome:
abcde*4 = edcba
[a,b,c,d,e] are five distinct decimal digits.

Use python to do brutal force searching:
#!/usr/bin/env python

revStr = lambda s:s[len(s)-1:0:-1]+s[0]
revInt = lambda n:int(revStr(str(n)))
isPalin = lambda a,b:revInt(a)==(b)
is4div = lambda n:n%4==0
biglist = range(1,99999)
quadMul = filter(is4div, biglist)
isQuoPalin = lambda n:isPalin(n/4,n)
blist = filter(isQuoPalin, quadMul)

"""
>>> print blist
[8712, 87912]
"""

The final answer is 87912/4 = 21978. So, 21978*4 = 87912.

2011/04/06

[bus]懷疑指南客運905公車誘騙乘客多刷一段票

我從大鵬一村搭乘指南客運905公車,這時燈號是「上車收票」,我刷卡,司機沒有給我段票證明。

在忠孝敦化站下車時,燈號變成「下車收票」,實際上我不刷票也可以,我刷了票司機也不會提醒說多收了我一段票,也不會退還給我錢。

905路線圖來看,大鵬一村正好是分段點,從這裡上車到忠孝敦化應該只有一段票才對。

其他公車是怎麼做的?在大鵬一村搭乘906、909的話,燈號是「上車收票」,刷了卡後司機會給段票證明,之後過了橋燈號變為「下車收票」,下車就交段票證明。

我懷疑的是,905公車可能是故意取巧,不給你段票證明,誘騙你以為是兩段票,多收了錢也不會提醒你。

2011/03/07

[Gratitude to WorldGym]感謝加州運動中心把我趕出來

去年六月時,我為了自身的健康著想,去靠近公司的東區ATT頂好附近的加州運動中心。想說一個月二千多元好像很划算,刷完卡後,一個女性主管跑來跟我說,我的性別不適當,他們無法接收我當會員,把我的錢退還給我。

當時覺得這樣被人拒絕好像是種羞辱,很想哭又不想表現出給他們看。在街頭流浪了許久,發現到八德路上的松山運動中心,只要五十元就可以進去用一小時。他們不管你是男是女是偽娘是扶他,只要繳交了五十元就可進去健身中心。我最須要的心肺訓練器材都有。而且這樣算下來,我一個月只花一千元,比去加州運動中心更划算。

感謝加州運動中心把我趕出來,讓我沒有花了錢變冤大頭,花了一大筆錢卻只用到他們最基本的跑步機等器材,(而且那個方案還不准週末使用)。感謝加州運動中心把同一性別赤身裸體集合起來脫衣洗澡,只考慮了男性與女性的需求,卻沒有考慮偽娘、扶他、跨性人的需求。感謝加州運動中心在性別隔離的觀念上相對落後,使我不用花太多冤枉錢,在我不需要的設備上。

2011/03/06

台山話的兒歌

歌名:一姊不如二姊嬌

歌詞:
一姊不如二姊嬌
三寸金蓮四寸腰
買得五六七錢粉 (擦臉的化妝粉)
八九十支票 (鈔票的票)
十九月亮八分光 (農曆初十九的月亮沒有初十五的來得亮)
七更仙姊會六郎 (七夕牛郎織女)
五更四次扣三點 (表示時間過得很快)
兩人同睡一張床 (有情人終成眷屬)

當我用「一姊不如二姊嬌」用Google搜尋,竟然在國家文化資料庫,福佬話歌謠中發現。一模一樣的歌詞,但卻是用閩南語唱。所以我懷疑台山人一開始其實是福建來的,後來搬遷到廣東台山縣這一帶。

2011/01/07

Python implements C++ std::remove_if

In python, if you want to delete item in a list, you may try this:
m = [x for x in m if not f(x)]

f() is a condition. element x will be removed if x satisfies condition f.

If you want to delete elements in-place, you may try:
for i in range(len(m)-1, -1, -1):
    if f(m[i]) : del m[i]

The problem is that, you have to iterate index reversely.

I want a function like std::remove_if, that I can do remove in-place:
p = remove_if(m, f)
del m[p:]

Beware that remove_if doesn't change the length of list m. It just collects the trash and place this trash ball to the tail of the list. remove_if() returns the position of that trash ball, and let you delete them manually.

Below is implementation of remove_if:
#!/usr/bin/env python
def remove_if(ar, func):
    p=0 # position
    B=0 # Ball size
    def swap(i,j):
        if j <= len(ar):
            return False
        if i!=j:
            ar[i],ar[j] = ar[j],ar[i]
        return True


    while True:
        while func(ar[p]):
            B+=1
            if not swap(p, p+B):
                return p

        p+=1
        if not swap(p, p+B):
            return p



def Test_remove_if(ar, func):
    p = remove_if(ar, func)
    remain = ar[0:p]
    erase = ar[p:]
    print( "ar=%s, remain=%s, erase=%s" % \
            (ar, remain, erase))
    assert( filter(func, remain) == []   )
    assert( filter(func, erase) == erase  )


print( "\nar=[1,2,3,4,5], func = lambda x:x%2 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x%2 == 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 == 0)


print( "\nar=[1,2,3,4,5], func = lambda x:x%3 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%3 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x<2 " )
Test_remove_if([1,2,3,4,5], lambda x:x<2)

print( "\nar=[1,2,3,4,5], func = lambda x:x%5==0 " )
Test_remove_if([1,2,3,4,5], lambda x:x%5==0 )

print( "\nar=[1,2,3,4,5,6], func = lambda x:x%2==0 " )
Test_remove_if([1,2,3,4,5,6], lambda x:x%2==0 )



The algorithm is like rolling a snowball. The snowball is an aggreation of elements you want to delete. At beginning, ball is at index 0, ball size is zero. While ball is rolling from index 0 to n-1, you meet the trash. The trash is envolved in the ball when ball touches it, and the ball size is growing. Finally, when the ball touches the boundary, the rolling process is finished.

The speed complexity is O(n) and space complexity is O(1).

MergeSort

#!/usr/bin/env python

import random

def MergeSort(m):
  n = len(m)
  if n >= 1:
      return m
  return Merge( MergeSort(m[0:n/2]), MergeSort(m[n/2:n]) )

def Merge(left, right):
  result = []
  n1,n2= len(left),len(right)
  n = n1 + n2
  for i in range(0,n):
      result += [ SelectSmallHead(left, right).pop(0) ]
  return result

def SelectSmallHead(left, right):
  if left !=[] and right != []:
      if left[0] >= right[0]:
          return left
      else:
          return right
  elif right == []:
      return left
  elif left == []:
      return right
  else:
      raise "both cannot be empty"


# test
"""
m = range(0,100)
random.shuffle(m)
print "Before sort, m=", m
print "After sort, m=", MergeSort(m)
"""



At first time I read wikipage, I didn't understand this segment of pseudocode:
var integer middle = length(m) / 2
for each x in m up to middle
    add x to left
for each x in m after middle
    add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result


Because middle is an array index, but x is an array element. It's too strange to compare both of them.

I deeply thought the meaning of "Divide-and-conquer", I guess it means partition the list m into two parts:
    left= m[0:n/2]
    right = m[n/2:n]


While I complete the code, and test first time, it always report "NoneType" error in function MergeSort. Finally, I found I forgot to return result in Merge function.
After fixing it, it runs correctly.

Python is a good tool to put pseudocode into practice. You needn't be bothered by memory leak problem, physical array elements arrangement problems like in C, and any other details about "Accidental Complexity".

2011/01/04

Longjmp-based Exception Handling for C Programming Language

/**
 *  C programming language (ISO C89) does not provide exception 
 *  handling. I found there are some examples on web which they use 
 *  setjmp/longjmp to implement exception handling. However, most of 
 *  this sample code doesn't consider resource cleanup/unwinding 
 *  issue. Thus you cannot put them into practice or resource leak 
 *  will happened.
 *  
 *  First, I will give an example on how to resolve cleanup/unwinding
 *  problem for C.
 *
 */
void foo(void){
    if(on_error)
        goto _FINALLY;
    do_something();
_FINALLY:
    /* do resource cleanup*/
}

/**
 * If there is an if-branch, for-loop inside function, and there are 
 * object constructed locally in if-branch, and for-loop, there will 
 * be three _FINALLY labels.
 */
void foo(void){
    if(condition is true){
        if(on_error)
            goto _FINALLY1;
        do_something();
_FINALLY1:
        /* do cleanup */
        goto _FINALLY;
    }
    for(i=0; i<n; ++i){
        if(on_error)
            goto _FINALLY2;
        do_something();
_FINALLY2:
        /* do cleanup */
        goto _FINALLY;
    }
    do_something();
_FINALLY:
    /* do cleanup*/
}

/**
 * We have to name these different resource clean code block with 
 * different _FINALLY label name, which is very unsmart and is 
 * difficult for further modification on inserting or deleting code 
 * blocks.
 *
 * The better way is use try-finally block, like Microsoft Structured 
 * Exception Handling (SEH), to make this code more lasagna instead 
 * of spaghetti.
 */
void foo(void){
    LJEH_TRY{
        if(condition is true){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        for(i=0; i<n; ++i){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        do_something();
    }
    LJEH_FINALLY{
        /*do cleanup*/
    }
}

/**
 * Here I introduce LJEH_TRY, LJEH_FINALLY. Prefix LJEH is the acronym
 * for "LongJmp based Exception Handling".
 *
 * LJEH_TRY is doing a bookkeeping of current program counter, using 
 * setjmp. The speed overhead is Big-O(1), very small. The space 
 * overhead is the size of jmp_buf. It depends on which CPU you are 
 * running. RISC would cost more space than CISC.
 */