有時候大家會想去 print 一個 pointer 裡面的值, 這個在 assembly code 中相當直覺, 在 C code 中需要一點點的技巧. 比方說 printf 預設的參數型別是 long, 那麼 int pointer 就需要轉一下, 才能夠保證印出心中所想的值.
int *ptr;
int data[100];
ptr = data;
for (i = 0; i < 100; i++)
{
printf("index %d = %x\n", i, *((long*)ptr));
就比
printf("index %d = %x\n", i, *ptr);
來得保險.
ptr++;
}
這個演算法的故事背景聽起來就比推銷員演算法 (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
今天重開機的時候, 看到這個 Windows Live Writer 詢問是否要安裝的畫面, 所以就點下去試用. 如果好用的話, 就不需要使用 WordPress 後台的編輯器了.
乍看之下, Word 的功能好像都有? 除了 private publish 的選項找不到之外, 一切都相當完美. 可以插入地圖, 又可以和 server 同步!
[檔案遺失]
除此之外, 還有各種快捷鍵, 直接連到 comment, dashboard, preview, 甚至於也可加標籤. 在最上方的 memu bar 有一個 “部落格(B)” 的選項, 可以檢視、管理、發佈多個部落格, 想來也可以把一篇文章貼到很多不同的地方.
雖然有這樣一套工具可以用對我來說是一個利多, 但是我想不通為何 Microsoft 要做這件事? 背後的意義是什麼呢?
不管這個 bog 要發表在 Microsoft 或是 Google 家, 若是 blog 作者都用同一套工具來開發, 等於是找到了唯一的入口. 至於哪個傻蛋要花錢供別人放置 blog 那是他的事, 至少 Microsoft 已經可以保證 bing 可以 search 得到這些 content. 我低等的智慧就只能想到這麼多了, 至少我還是個受益者.
BTW, Microsoft 的搜尋網站叫做 bing, 實在是不買中國人的帳! 難道它可以向別家一樣打廣告, 讓主角們互相問: “你今天 bing (病) 了嗎 ?"
客戶的要求如土石流一樣地來, 既然不能遷村, 就要做好防災的準備, 免得不小心就滅村了. 這次的需求是 IMA4, priority 大概第 40 順位.
這個 IMA4 是什麼東西呢? 它是 Apple Quick Time 所支援的 ADPCM 格式. 一般是 1~2 聲道, 左聲道 block 放完才放右聲道 block, 然後反覆左右, 左右 的 blocks 直到檔尾. 每個 block 由 64 個 nibble 所組成, 1 nibble 也就是 1/2 bytes or 4 bits.
為何要選 nibble 為單位呢? 據說是為了要避免 endian 的問題, 只要把 data 以 4 bits 為單位組裝起來, 就可以依據平台來解釋它是 big endian 或是 little endian. Apple 號稱這個設計有 cross-platform 的功效.
[離題一下] 話說 nibble 很像另外一個單字 nipple (奶頭), 有位前同事就把這兩者搞混了, 也誤導了我一陣子. 不過人非聖賢, 孰能無過. 身為一個工程師, 程式沒錯就很偷笑了, 偶爾打印一些 FETAL ERROR, 或是程式裡面命名一些 Globle 變數也是難免的. 反正看久就習慣了, 見怪不怪真可以說是中華文化根深蒂固的一個部分. 哈哈!
| name | bits | structure | note |
| preamble | 16 | ppppppp piiiiiii |
p 代表 9 bits signed predictor, i 代表 7 bits initial step index. |
| block | 32×8 | n1n0 n3n2 …. | 左聲道, nibble 0 在 nibble 1 的後面, 但是要先解, 依此類推. |
| block | 32×8 | n1n0 n3n2 …. | 右聲道, 單聲道就沒有這部分, 換下一個左聲道的 block. |
欲了解 IMA4 的全貌, 最好參考 Apple 的網頁.
http://developer.apple.com/mac/library/technotes/tn/tn1081.html
今天有同事發信告訴大家, 他犯了一個 volatile 的錯誤, 希望大家不要重蹈覆轍. 內容大致是說, 平常大家習慣用 a = b = 10; 這樣的寫法, 但是若加上了 volatile 就不行了.
*(volatile unsigned int *) a =
*(volatile unsigned int *) b = xxx.
為啥子呢? 因為 volatile 告訴 compiler, 這個值每次用到的時候, 都要去 a 和 b 對應的 address 裡面重新讀出來.
Compiler 如果有預見的能力, 根本不會讓它通過的. 比方說 Visual C++ 2008 Express 版, 會給這樣的訊息:
1>c:\users\cash\documents\visual studio 2008\projects\source1.cpp(6) : error C2059: 語法錯誤 : ‘volatile’
關於 volatile 的原理, 有一篇文章寫得很好, 大家可以去看看:http://blog.csdn.net/c_bg44/archive/2007/03/23/1538235.aspx
Cash Chou's Blog 