秘書演算法 (Secretary Algorithm)

這個演算法的故事背景聽起來就比推銷員演算法 (traveling salesman) 有趣多了. 傻傻的推銷員只會走來走去, 秘書演算法卻可以讓大家過老闆的癮呢! 可惜我以前念書的時候, 只有推銷員問題, 老師或書本上都沒有祕書問題. 上次看到有位小朋友研究這個問題得了獎, 因此我才有機會試著了解一下! (這位小朋友研究的是: 有競爭者的時候, 應該錄取第幾位秘書.)

假設有一個大老闆在挑選秘書, 又有很多的準秘書來應徵, 老闆如何在最短的時間內, 挑到最好的人才呢? 這就是秘書演算法討論的問題. 如果真的把每一位秘書都 interview 過一輪, 而且大家都願意等 offer (這是 off-line algorithm), 我們當然 100% 會挑到最好的, 但若是時間有限, 好秘書不等人, 我們怎樣在 95% 信心度之下, 挑出最好的那一位, 又不用面試完所有的人呢? (這樣好像在解計量考題…)

只選一位秘書的狀況下, 假使我們從 n 位應徵者中, 隨機面談了 k 位,  k = 1,2,3…, 每面談一位, 老闆就要決定是否發 offer. 此時大家應該可以感受, 發 offer 與不發都需要智慧. 因為 offer 發出去就沒有了, 一不小心就錯過了最好的那位候選人 (這是 on-line algorithm).

on-line performance 對 off-line performance 的比值叫做 competitive ratio, 用來評估演算法好不好.有個 1/3 – competitive ratio 的演算法可以改進上面的狀況. 我們先從 n 位應徵者中面談一半的人, 然後挑出裡面最好的那一個, 假設他 (她) 的面談分數是 max v 分. 然後呢, 對於後一半的應徵者, 只要分數高過於 max v 分, 馬上就錄取他 (她), 後面的人就完全不用考慮了.

如果有 k 個 offer 要發, 我們優化的目標就變成有多樣選擇: (1) 在最少的面談次數找到最佳候選人, (2) 最小化 k 個錄取者的排名總和, (3) 最大化 k 個錄取者的評分總和. 因為要挑到最好的人的機率 (probability), 以及選擇最少的面談次數, 兩者是互斥的.

要從 n 個應徵者當中挑出 k 個人進公司時, 可以從 n 當中隨機挑出約一半的 m 個人, 並且發出 k 個名額當中約一半的 l 個 offer. 因此, n 選 k 的問題就縮減成了 m 選 l 的問題.

由第 m+1 個人開始, 如果這個人比我們已經發出 offer 的人都還要高分, 我們就錄取他/她. 不知道理解得對不對, 這個演算法是 divide and conquer. 據說這個演算法的 competitive ratio 為 1-O((1/k)1/2). 

1966 年, Chow 等人證明在應徵者無限多, 只發一個 offer 時, 理論上選第 3.8695 的人最好, 也就是錄取第四個人吧! (我理解錯了的話, 還請網友糾正, 謝謝!)

我以前的老闆跟我說: “你面談的時候, 至少要談 3 個人才能能發 offer." 所以經驗法則和上面的證明也差不了多少. 事實上, 如果是以前熱門的國防役, 大概要談 10 個人才會錄取一個人. 2004 年, 我手上有 4 個國防役名額的時候, 就花了好多的時間在面談. 後來更是發了幾十個 offer 給軟體和韌體工程師, 一整年幾乎都荒廢了.

附帶一提, 數學上講究的是最佳化, 也就是談最少的人, 達到最滿意的結果. 然而, 在現實生活中, 考慮的層面就不是這麼單純, 我們不需要最佳化面談的時間, 因為人才是公司最重要的資產. 如果只是為了省主管的時間,  而找到次佳的人進來, 若他/她已經落入不佳的等級, 可能是公司莫大的災難.

K 個 offer (choice) 這個題目好像很多人都做過研究了, 我覺得考慮競爭者 (別的公司也在面談) 和錄取者彼此互補性都是很有趣的題目. 比方說, 過去的研究都是假設每個人只有一分數, 但若是錄取 A,B,C 3 人, A 的表現會受 B,C 的影響, 那麼這樣會更加地有趣.

在 “小職員週記" 這套漫畫裡提到, 其實公司會交替地錄用聰明的人, 踏實的人等等. 因為新人進來一陣子之後就會看到他/她們的缺點, 因此會想要找一點不同的人來彌補那些缺點. 所以這個命題也並非無的放矢, 我們在真實世界的面談分數也是隨者資深者已經有幾人, 無經驗者可以有幾人而變動的.

 [Ref] http://paul.rutgers.edu/~mangesh/cs514/notes/pres8.pdf

Sumsung i8000 的使用心得

Sumsung i8000 是一隻規格相當好的手機, 在很多地方都可以看到介紹它的文章. Mobile 01 當然也少不了它的開箱文. 我想我可以貢獻的, 應該就是講些個人心得, 以及 "疑似缺點". 說是 "疑似", 那是因為某些功能在說明書沒寫, 我也試不出來的關係. 如果單純是因為我腦殘而產生誤解的話, 我會再更新本文來導正視聽~~~

優點:

1. 拍照飽和度高.

2. 語音輸入法相當準確, 只要多輸入一些常用名詞的話, 應該就足以寫日記用了.

3. 名片辨識效果超好. 以後客戶帶來的名片不夠發, 我可以借來拍一下再還他.

4. 3.7”的螢幕相當大, 看網頁比較方便.

5. 2G 的待機時間夠長, 不用像使用 HTC 一樣擔心它的電力.

缺點:

1. 開到 "效能高" 的話, 待機一個晚上就用掉 40% 的電力. 換算起來, 效能高的時候, 只能待機 20 小時. 當然, 在點選這個項目的時候, UI 已經出現警語了. 正常來說, 大家都不會和自己的電力開玩笑.

2. 藍芽不支援 PAN?

3. 中華電信的 push mail 不支援這隻手機?

4. 不支援 Magicall 等來電防火牆軟體?

5. 吊飾筆的線太硬, 有鬆脫的機會.

6. 開關機按鈕不是很靈敏.

7. 非常難建立捷徑. 坊間常用的 shortcut 軟體大多不相容, 可能是因為 today 被 Sumsung 改掉了? 唯一可以用的是 ShortcutCreater.

8. 支援 MicroSDHC 到 32GB, 可是 32GB 根本還沒有量產. 16GB class 6 MicroSDHC 就已經貴到 3,000 多 NTD, 要是支援 SD 卡就好了.

9. 導航軟體 McGuider 的輸入比 Papago 沒有彈性, 也無法以語音輸入. 但是顯然 McGuider 的地圖比較細, 連我家和隔壁鄰居中間的空地都畫得出來.

10. 背面的相機鏡頭突出, 平放時不適合用觸控筆. 點下去會先歪一邊. 

11. 收訊能力似乎比高通的晶片弱,  HTC 是 H 或 3G 的地方, i8000 可能會沒訊號.

雖然我列出的缺點比優點多, 但是我還是相當滿意這隻手機. 因為我想要的大螢幕 + 自動對焦相機 + GPS  + HSDPA/HSUPA 它都有.

[note] 講一下價錢: 神腦目前沒有折扣. 新竹 Nova 的首賣店, 就算續 Mpro 950 的門號, 也只能折 3,000 NTD. 光復路上的 "佳世達" 可以讓大家再多省幾千塊, 但不知現在有沒有貨? 我覺得通訊行應該很容易拿大家的門號去綁熱門的 Iphone 3GS 或是 HTC Hero 來轉賣才對, 不可能只有區區 3,000 的空間. 

[note2] i8000 有內建的來電防火牆, 功能雖然不強, 但是總算是有. 進入通訊錄後, 選最右邊的 icon (一隻直立有天線的手機, 右下方有個方塊上面打 X 的那個),   選 "新增" 可以建立規則, 不過這裡可以用的規則就只有接或不接電話, 要不要傳簡訊給對方而已, 和 MagiCall 的能力真是天差地別.

[note3] 我一直找不到的電子字典在 Smart Reader 裡面, 它的功能真是太強了. 在名片辨識的部份, 我本來覺得做得很不錯. 不過最近卻發現所有的名片都不認得了?? 不管怎麼設定都沒用! 上了三星樂園網站去看討論區, 才知道這是他們自己的 bug. 只要暫時把手機日期調回 9 月就 OK 了. 因此三星會另外出一版 patch 放在網路上.