偶然從 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 秒 啊!!
訂閱:
張貼留言 (Atom)
在 Fedora 下裝 id-utils
Fedora 似乎因為執行檔撞名,而沒有提供 id-utils 的套件 ,但這是使用 gj 的必要套件,只好自己編。從官網抓好 tarball ,解開來編譯 (./configure && make)就是了。 但編譯後會遇到錯誤: ./stdio.h:10...
-
find -uid 可以找目錄下特定使用者有的檔案, 反過來不知怎麼找。 今天靈機一動, 想到可以這麼搞, 不夠直接, 至少能用就是了: ls -lR DIR | grep "^[-rw]\{10\} " | grep -v USER 2011-01-...
-
昨天意外發現 rsync 有 -z 的參數, 可以壓縮再傳。好奇它的效果就試了一下, 結果得到出人意外的結論: 有時候直接全部重新複製還比較快........, 雖然是很明顯的事實, 用慣 rsync 後到沒想到這點。 簡易的測試環境如下: 原始檔案: 一堆目錄合起來 7G...
-
以使用 LevelDB 為例。 抓好並編好相關檔案,編譯方式見第三方函式庫附的說明: $ ls include/ # header files leveldb/ $ ls out-shared/libleveldb.so* # shared library out-sha...
Pretty interesting! "Sleep"ing contest XD!
回覆刪除