2011年6月24日 星期五

運用 radix sort 的概念加速 sleep sort

偶然從 shakalaca 那看到《排序算法 Sleep Sort》, 剛看完程式碼我的第一印象是: 你在開玩笑嗎? 這在排什麼刁。再仔細看看, 查覺背後神祕的運作原理後, 心中的感覺和文中描述一模一樣: “我擦,真TMD排序了!”。原諒我直接貼上文中的粗話, 當時心中的震撼只能用這樣的字眼才能表達出來。

後來看到留言有人提到這其實是 radix sort 的變型。仔細想想, 確實是這麼一回事!! radix sort 原本是將數字對應到空間的位置, 而 sleep sort 是對到時間上的位置 (或照 sleepnova 的說法, 其實是轉交給 OS 的 task schedule 去排, 不過這樣想就不好玩啦)。所以, 可以套用 radix sort 的概念來加速 sleep sort。

於是憑著愚蠢熱血的餘韻, 用 python + thread 寫了一版程式貼在 github, 有興趣的人可以玩玩看, 排得又「快」又準!! 算時間複雜度不太有意義, 改算秒數比較實在。假設沒有調快執行速度 (即 FASTER_RATE = 1), 且計算時間遠小於 sleep 的時間, 那麼, 若最大允許的正整數是 2**32 - 1, 也就是一個十位數, 我目前的實作方式只需要 90 秒 (比原版快了47721858.83 倍!!)。這樣看來改用二進位會更快, worst case 只要 32 秒 啊!!

1 則留言:

在 Fedora 下裝 id-utils

Fedora 似乎因為執行檔撞名,而沒有提供 id-utils 的套件 ,但這是使用 gj 的必要套件,只好自己編。從官網抓好 tarball ,解開來編譯 (./configure && make)就是了。 但編譯後會遇到錯誤: ./stdio.h:10...